Survivable networks, linear programming relaxations and the parsimonious property
From MaRDI portal
Publication:689117
DOI10.1007/BF01580607zbMath0790.90072WikidataQ89228111 ScholiaQ89228111MaRDI QIDQ689117
Dimitris J. Bertsimas, Michel X. Goemans
Publication date: 6 December 1993
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
heuristicstraveling salesmanworst-case analysisSteiner treesurvivable network design\(k\)-edge- connected network designedge- connectivity requirementsparsimonious property
Related Items
Network design with edge-connectivity and degree constraints, A primal-dual approximation algorithm for generalized Steiner network problems, On perfectly two-edge connected graphs, The parsimonious property of cut covering problems and its applications, On the graphical relaxation of the symmetric traveling salesman polytope, A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case, A deterministic better-than-3/2 approximation algorithm for metric TSP, Robust capacitated Steiner trees and networks with uniform demands, Unnamed Item, A Survey on Covering Supermodular Functions, Shorter tours and longer detours: uniform covers and a bit beyond, Approximation algorithms for metric tree cover and generalized tour and tree covers, Approximation algorithms for connected graph factors of minimum weight, Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems, Analysis of the Held-Karp lower bound for the asymmetric TSP, 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem, A partition-based relaxation for Steiner trees, Deterministic sampling algorithms for network design, The directed orienteering problem, On survivable network polyhedra, Steiner trees and polyhedra, A comparison of Steiner tree relaxations, Improved algorithms for the Steiner problem in networks, Computing a tree having a small vertex cover, Intuitive solution-doubling techniques for worst-case analysis of some survivable network design problems, Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements, On the core of traveling salesman games, The indefinite period traveling salesman problem, On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, On the integrality ratio for tree augmentation, Group-Strategyproof Cost Sharing for Metric Fault Tolerant Facility Location, Approaches to the Steiner Problem in Networks, A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem, An efficient approximation algorithm for the survivable network design problem, An improved approximation ratio for the minimum latency problem, Generalized spanning trees, Resilient layout, design and operation of energy-efficient water distribution networks for high-rise buildings using MINLP, Problems of synthesis of connected networks with respect to isomorphic subgraphs, On the facial structure of symmetric and graphical traveling salesman polyhedra, Relay placement for two-connectivity, Unnamed Item, A technique for speeding up the solution of the Lagrangean dual, Separation of partition inequalities for the \((1,2)\)-survivable network design problem
Cites Work
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Minimum-weight two-connected spanning networks
- A note on the prize collecting traveling salesman problem
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- A fast algorithm for Steiner trees
- A dual ascent approach for steiner tree problems on a directed graph
- Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
- Steiner problem in networks: A survey
- Multi-Terminal Network Flows
- Heuristic analysis, linear programming and branch and bound
- An integer linear programming approach to the steiner problem in graphs
- Integer Solution to Synthesis of Communication Networks
- On some connectivity properties of Eulerian graphs
- P-Complete Approximation Problems
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- Une heuristique pour le problème de l'arbre de Steiner
- Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
- A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design
- Maximum matching and a polyhedron with 0,1-vertices
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The traveling-salesman problem and minimum spanning trees: Part II
- A faster approximation algorithm for the Steiner problem in graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
