- 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: Download: [PDF]Entry Submitted: 10/19/2019Entry Accepted: 10/19/2019Entry Last Modified: 10/19/2019Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.