On the Complexity of Master Problems
From MaRDI portal
Publication:2946425
DOI10.1007/978-3-662-48054-0_47zbMath1465.68110MaRDI QIDQ2946425
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
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