A priori TSP in the scenario model

DOI10.1016/J.DAM.2018.04.002zbMATH Open1409.90161OpenAlexW2809282601WikidataQ129359035 ScholiaQ129359035MaRDI QIDQ1801079FDOQ1801079

Teun Janssen, René A. Sitters, Martijn van Ee, Leo Van Iersel

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

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

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

• Reducibility among Combinatorial Problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Ramanujan graphs
• Some simplified NP-complete graph problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Title not available (Why is that?)
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Improved lower and upper bounds for universal TSP in planar metrics
• Title not available (Why is that?)
• Sometimes Travelling is Easy: The Master Tour Problem
• Regular Graphs with Given Girth and Restricted Circuits
• Oblivious network design
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• Cyclic ordering is NP-complete
• Title not available (Why is that?)
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• Deterministic sampling algorithms for network design
• Improved Lower Bounds for the Universal and a priori TSP
• Algorithms for the universal and a priori TSP
• Title not available (Why is that?)
• On the Complexity of Master Problems
• Title not available (Why is that?)
• On the probabilistic min spanning tree problem
• Scheduling over Scenarios on Two Machines
• Title not available (Why is that?)
• A priori TSP in the Scenario Model

Cited In (3)

• Total completion time scheduling under scenarios
• Algorithms for the universal and a priori TSP
• 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)