A priori TSP in the scenario model
From MaRDI portal
Publication:1801079
DOI10.1016/j.dam.2018.04.002zbMath1409.90161OpenAlexW2809282601MaRDI QIDQ1801079
Teun Janssen, Martijn van Ee, Leo van Iersel, R. A. Sitters
Publication date: 26 October 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://research.vu.nl/en/publications/614d619a-75aa-4c3a-a542-3a7986febaef
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deterministic sampling algorithms for network design
- Algorithms for the universal and a priori TSP
- Ramanujan graphs
- Some simplified NP-complete graph problems
- Cyclic ordering is NP-complete
- On the probabilistic min spanning tree problem
- Hedging uncertainty: approximation algorithms for stochastic optimization problems
- Scheduling over Scenarios on Two Machines
- On the Complexity of Master Problems
- A priori TSP in the Scenario Model
- Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
- Improved lower and upper bounds for universal TSP in planar metrics
- Oblivious network design
- Improved Lower Bounds for the Universal and a priori TSP
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Sometimes Travelling is Easy: The Master Tour Problem
- Reducibility among Combinatorial Problems
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Regular Graphs with Given Girth and Restricted Circuits
