Robust Algorithms for TSP and Steiner Tree

DOI10.1145/3570957arXiv2005.08137OpenAlexW3024720357MaRDI QIDQ6075747

Debmalya Panigrahi, Arun Ganesh, Bruce M. Maggs

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

traveling salesmanSteiner tree

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• On the recoverable robust traveling salesman problem
• On a constant factor approximation for minmax regret problems using a symmetry point scenario
• The computational complexity of the relative robust shortest path problem with interval data
• Complexity of the min-max (regret) versions of min cut problems
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Robust discrete optimization and its applications
• Minimax regret solution to linear programming problems with an interval objective function
• On dual minimum cost flow algorithms
• Robust discrete optimization and network flows
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• New Inapproximability Bounds for TSP
• An improved LP-based approximation for steiner tree
• The Minmax Relative Regret Median Problem on Networks
• Heuristic analysis, linear programming and branch and bound
• Minimax regret p-center location on a network with demand uncertainty
• Minmax Regret Median Location on a Network Under Uncertainty
• A Local-Search Algorithm for Steiner Forest
• On the complexity of a class of combinatorial optimization problems with uncertainty
• The robust spanning tree problem with interval data

This page was built for publication: Robust Algorithms for TSP and Steiner Tree