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

DOI10.1016/J.ORL.2010.02.005MaRDI QIDQ974982zbMATH OpenOpenAlexFDO

Authors Viswanath Nagarajan, R. Ravi, Mohit Singh

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

approximation algorithmssurvivable network designtraveling salesmanlinear programming relaxations

Mathematics Subject Classification ID

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

Recommendations

• LP extreme points and cuts for the fixed-charge network design problem
• Exterior point simplex-type algorithms for linear and network optimization problems
• scientific article; zbMATH DE number 1263260
• An efficient approximation algorithm for the survivable network design problem
• scientific article; zbMATH DE number 2086687
• Extremal Points and an Algorithm for a Class of Continuous Transportation Problems
• On the Polytope of the (1,2)-Survivable Network Design Problem
• A note on iterated rounding for the survivable network design problem
• scientific article; zbMATH DE number 1305423
• Fast Approximation Algorithms for the Generalized Survivable Network Design Problem

Cites work

• scientific article; zbMATH DE number 795223 (Why is no real title available?)
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Additive guarantees for degree-bounded directed network design
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Optimizing over the subtour polytope of the travelling salesman problem
• The traveling salesman problem. A computational study.
• Worst-case comparison of valid inequalities for the TSP

Cited in

(7)

• Socially fair network design via iterative rounding
• A note on iterated rounding for the survivable network design problem
• LP extreme points and cuts for the fixed-charge network design problem
• A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
• Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
• Approximation algorithms for multi-budgeted network design problems
• Multicommodity flow in trees: packing via covering and iterated relaxation

Describes a project that uses

Uses Software

• Concorde

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

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