Simpler analysis of LP extreme points for traveling salesman and survivable network design problems

DOI10.1016/j.orl.2010.02.005zbMath1187.90235OpenAlexW2052340714MaRDI QIDQ974982

Mohit Singh, R. Ravi, Viswanath Nagarajan

Publication date: 8 June 2010

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2010.02.005

zbMATH Keywords

traveling salesmanapproximation algorithmslinear programming relaxationssurvivable network design

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (6)

Approximation Algorithms for Multi-budgeted Network Design Problems ⋮ Unnamed Item ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ A \(4+\epsilon\) approximation for \(k\)-connected subgraphs ⋮ Multicommodity flow in trees: packing via covering and iterated relaxation ⋮ Socially fair network design via iterative rounding

Uses Software

• Concorde

Cites Work

• Optimizing over the subtour polytope of the travelling salesman problem
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Worst-case comparison of valid inequalities for the TSP
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Approximating the smallest k -edge connected spanning subgraph by LP-rounding
• Additive Guarantees for Degree-Bounded Directed Network Design
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• Unnamed Item
• Unnamed Item

This page was built for publication: Simpler analysis of LP extreme points for traveling salesman and survivable network design problems