The trouble with the second quantifier

We survey optimization problems that allow natural simple formulations with one existential and one universal quantifier. We summarize the theoretical background from computational complexity theory, and we present a multitude of illustrating examples. We discuss the connections to robust optimization and to bilevel optimization, and we explain the reasons why the operational research community should be interested in the theoretical aspects of this area.

MoreLess

Year of publication:	2021
Authors:	Woeginger, Gerhard J.
Published in:	4OR. - Berlin, Heidelberg : Springer, ISSN 1614-2411. - Vol. 19.2021, 2, p. 157-181
Publisher:	Berlin, Heidelberg : Springer
Subject:	Combinatorial optimization \| Complexity theory \| Polynomial hierarchy \| Bilevel optimization

More details

Type of publication:	Article
Type of publication (narrower categories):	Article
Language:	English
Other identifiers:	10.1007/s10288-021-00477-y [DOI]
Source:	EconStor

Persistent link: https://www.econbiz.de/10014497617