A priori TSP in the scenario model

DOI10.1016/j.dam.2018.04.002zbMath1409.90161OpenAlexW2809282601WikidataQ129359035 ScholiaQ129359035MaRDI 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

zbMATH Keywords

traveling salesman problema priori optimizationmaster touroptimization under scenarios

Mathematics Subject Classification ID

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

This page was built for publication: A priori TSP in the scenario model