A priori TSP in the Scenario Model

DOI10.1007/978-3-319-51741-4_15zbMath1484.90097OpenAlexW2569842791MaRDI QIDQ2971168

Teun Janssen, Leo van Iersel, Martijn van Ee, R. A. Sitters

Publication date: 4 April 2017

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/25528

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)

Related Items (1)

A priori TSP in the scenario model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic sampling algorithms for network design
• Algorithms for the universal and a priori TSP
• 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
• 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
• 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
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

This page was built for publication: A priori TSP in the Scenario Model