  


A note on the nonexistence of oraclepolynomial algorithms for robust combinatorial optimization
Christoph Buchheim (christoph.buchheimmath.tudortmund.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 oraclebased 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. Download: Entry Submitted: 10/19/2019 Modify/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  