On the complexity of master problems

DOI10.1007/978-3-662-48054-0_47MaRDI QIDQ2946425zbMATH OpenOpenAlexFDO

Authors Martijn van Ee, René 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 hierarchyunique optimal solutionsuniversal optimization

Mathematics Subject Classification ID

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

Recommendations

• Sometimes Travelling is Easy: The Master Tour Problem
• scientific article; zbMATH DE number 4027206
• Sometimes travelling is easy: The master tour problem
• Generalized Steiner problems and other variants
• A note on the traveling salesman problem

Cites work

• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• Algorithms for the universal and a priori TSP
• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 5042868 (Why is no real title available?)
• Improved lower bounds for the universal and a priori TSP
• NP is as easy as detecting unique solutions
• Oblivious network design
• On the complexity of unique solutions
• On the unique satisfiability problem
• Sometimes Travelling is Easy: The Master Tour Problem
• The complexity of facets (and some facets of complexity)
• The complexity of optimization problems
• The polynomial-time hierarchy

Cited in

(8)

• Master-slave strategy and polynomial approximation
• On the query complexity of black-peg AB-mastermind
• The multi-stripe travelling salesman problem
• A priori TSP in the scenario model
• On the complexity of MMSNP
• A priori TSP in the Scenario Model
• scientific article; zbMATH DE number 7650068 (Why is no real title available?)
• On the algorithmic complexity of the Mastermind game with black-peg results

This page was built for publication: On the complexity of master problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946425)