Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
From MaRDI portal
Publication:974982
DOI10.1016/J.ORL.2010.02.005zbMATH Open1187.90235OpenAlexW2052340714MaRDI QIDQ974982FDOQ974982
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
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
- The traveling salesman problem. A computational study.
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Title not available (Why is that?)
- Worst-case comparison of valid inequalities for the TSP
- Optimizing over the subtour polytope of the travelling salesman problem
- 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
Cited In (7)
- Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
- A \(4+\epsilon\) approximation for \(k\)-connected subgraphs
- Approximation Algorithms for Multi-budgeted Network Design Problems
- LP extreme points and cuts for the fixed-charge network design problem
- Socially fair network design via iterative rounding
- Multicommodity flow in trees: packing via covering and iterated relaxation
- Title not available (Why is that?)
Uses Software
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)
