On the Complexity of Master Problems

DOI10.1007/978-3-662-48054-0_47zbMath1465.68110OpenAlexW2399795099MaRDI 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 complexitypolynomial hierarchyuniversal optimizationunique optimal solutions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics of discrete mathematics in relation to computer science (68R01) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

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

This page was built for publication: On the Complexity of Master Problems