A note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimization
Christoph Buchheim (christoph.buchheimmath.tu-dortmund.de)
Abstract: For many classical combinatorial optimization problems such as, e.g., the shortest path problem or the spanning tree problem, the robust counterpart under general discrete, polytopal, or ellipsoidal uncertainty is known to be intractable. This implies that any algorithm solving the robust counterpart that can access the underlying certain problem only by an optimization oracle has to call this oracle more than polynomially many times, unless P\,$=$\,NP. In this short note, we show by a simple construction that, in fact, such an algorithm needs exponentially many oracle calls in the worst case even without assuming P\,$\neq$\,NP. Moreover, we show that oracle-based pseudopolynomial or approximation algorithms cannot exist either.
Keywords: Robust Optimization; Complexity
Category 1: Robust Optimization
Category 2: Combinatorial Optimization
Citation: To appear in Discrete Applied Mathematics.
Entry Submitted: 10/19/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|