Optimization at the second level

Gerhard Woeginger

TU Eindhoven

Abstract

The talk surveys and discusses a number of algorithmic problems located at the second level of the polynomial hierarchy. Most of these problems are taken from geometry, graph theory, social choice, and robust optimization; some of them are genuinely intractable, and some of them only pretend to be intractable.