Robust Algorithms for TSP and Steiner Tree

DOI10.1145/3570957MaRDI QIDQ6075747zbMATH OpenOpenAlexFDO

Authors Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi

Publication date 23 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.08137

zbMATH Keywords

Steiner treetraveling salesman

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution's cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.

Recommendations

• A robust and scalable algorithm for the Steiner problem in graphs
• Robust reoptimization of Steiner trees
• Robust reoptimization of Steiner trees
• On the approximability of robust spanning tree problems
• Strong Steiner tree approximations in practice
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• Robust optimization for routing problems on trees
• Exact approaches for solving robust prize-collecting Steiner tree problems
• Computing and Combinatorics
• Algorithms for terminal Steiner trees

Cites work

• scientific article; zbMATH DE number 2089220 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A local-search algorithm for Steiner forest
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• An improved LP-based approximation for Steiner tree
• Complexity of the min-max (regret) versions of min cut problems
• Heuristic analysis, linear programming and branch and bound
• 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 dual minimum cost flow algorithms
• 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
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• 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

Cited in

(3)

• Improved guarantees for the a priori TSP
• Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization
• Greediness is not always a vice: efficient discovery algorithms for assignment problems

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 Q6075747)