Robust algorithms for TSP and Steiner tree

DOI10.4230/LIPICS.ICALP.2020.54MaRDI QIDQ6842519zbMATH OpenFDO

Authors Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.54

zbMATH Keywords

robust optimizationtraveling salesman problemSteiner tree

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 2089220 (Why is no real title available?)
• A local-search algorithm for Steiner forest
• A new mixed integer formulation for the maximum regret problem
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• An approximation scheme for stochastic linear programming and its application to stochastic integer programs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Boosted sampling
• Complexity of the min-max (regret) versions of min cut problems
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Minimax regret p-center location on a network with demand uncertainty
• Minimax regret solution to linear programming problems with an interval objective function
• Minmax Regret Median Location on a Network Under Uncertainty
• New inapproximability bounds for TSP
• On a constant factor approximation for minmax regret problems using a symmetry point scenario
• On the complexity of a class of combinatorial optimization problems with uncertainty
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• On the recoverable robust traveling salesman problem
• Provisioning a virtual private network: a network design problem for multicommodity flow
• Robust Combinatorial Optimization with Exponential Scenarios
• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Sampling-based approximation algorithms for multistage stochastic optimization
• The VPN conjecture is true
• The computational complexity of the relative robust shortest path problem with interval data
• The minmax relative regret median problem on networks
• The robust spanning tree problem with interval data
• Thresholded covering algorithms for robust and max-min optimization
• Two-stage robust network design with exponential scenarios

This page was built for publication: Robust algorithms for TSP and Steiner tree

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