Journal
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH
Volume 19, Issue 2, Pages 157-181Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10288-021-00477-y
Keywords
Combinatorial optimization; Complexity theory; Polynomial hierarchy; Bilevel optimization
Categories
Funding
- Deutsche Forschungsgemeinschaft (DFG) [DFG RTG 2236]
- Projekt DEAL
Ask authors/readers for more resources
This paper explores optimization problems with natural formulations using existential and universal quantifiers. Theoretical background from computational complexity theory and numerous illustrating examples are presented. Connections to robust optimization and bilevel optimization are discussed, along with reasons for why the operational research community should be interested in the theoretical aspects of this field.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available