On the Complexity of Master Problems

DOI10.1007/978-3-662-48054-0_47zbMath1465.68110MaRDI QIDQ2946425

Martijn van Ee, R. A. Sitters

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_47

zbMATH Keywords

computational complexity; polynomial hierarchy; universal optimization; unique optimal solutions

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R01: General topics of discrete mathematics in relation to computer science

90C27: Combinatorial optimization

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

The multi-stripe travelling salesman problem, A priori TSP in the scenario model, A priori TSP in the Scenario Model

Cites Work

• Unnamed Item
• Unnamed Item
• Algorithms for the universal and a priori TSP
• The complexity of facets (and some facets of complexity)
• NP is as easy as detecting unique solutions
• The complexity of optimization problems
• The polynomial-time hierarchy
• On the unique satisfiability problem
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• Oblivious network design
• Improved Lower Bounds for the Universal and a priori TSP
• On the complexity of unique solutions
• Sometimes Travelling is Easy: The Master Tour Problem