A priori TSP in the scenario model

DOI10.1016/J.DAM.2018.04.002MaRDI QIDQ1801079zbMATH OpenOpenAlexWikidataFDO

Authors Martijn van Ee, Leo Van Iersel, Teun Janssen, René 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)

Recommendations

• A priori TSP in the Scenario Model
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• A Priori Optimization
• The A priori traveling repairman problem
• A Priori Optimization of the Probabilistic Traveling Salesman Problem

Cites work

• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 3526435 (Why is no real title available?)
• scientific article; zbMATH DE number 1303538 (Why is no real title available?)
• scientific article; zbMATH DE number 6469210 (Why is no real title available?)
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• A priori TSP in the Scenario Model
• Algorithms for the universal and a priori TSP
• Beating the random ordering is hard: every ordering CSP is approximation resistant
• Cyclic ordering is NP-complete
• Deterministic sampling algorithms for network design
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved lower and upper bounds for universal TSP in planar metrics
• Improved lower bounds for the universal and a priori TSP
• Oblivious network design
• On the NP-hardness of approximating ordering-constraint satisfaction problems
• On the complexity of master problems
• On the probabilistic min spanning tree problem
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Ramanujan graphs
• Reducibility among combinatorial problems
• Regular Graphs with Given Girth and Restricted Circuits
• Scheduling over scenarios on two machines
• Some optimal inapproximability results
• Some simplified NP-complete graph problems
• Sometimes Travelling is Easy: The Master Tour Problem
• Stochastic and robust scheduling in the cloud

Cited in

(7)

• Improved guarantees for the a priori TSP
• Total completion time scheduling under scenarios
• The A priori traveling repairman problem
• Algorithms for the universal and a priori TSP
• Routing under uncertainty: the \textit{a priori} traveling repairman problem
• Total completion time scheduling under scenarios
• A priori TSP in the Scenario Model

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

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