Optimization Online


A note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimization

Christoph Buchheim (christoph.buchheim***at***math.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
Entry Accepted: 10/19/2019
Entry Last Modified: 07/06/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society