The parsimonious property of cut covering problems and its applications

DOI10.1016/S0167-6377(97)00032-1zbMath0914.90254MaRDI QIDQ1375118

Chung-Piaw Teo, Dimitris J. Bertsimas

Publication date: 12 January 1998

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

zbMATH Keywords

vehicle routingSteiner treesurvivable network designparsimonious propertycovering cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27)

Related Items (4)

A Survey on Covering Supermodular Functions ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ A new contraction technique with applications to congruency-constrained cuts ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem

Cites Work

• Survivable networks, linear programming relaxations and the parsimonious property
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Matching theory
• Short proofs on multicommodity flows and cuts
• Four-terminus flows
• Heuristic analysis, linear programming and branch and bound
• On some connectivity properties of Eulerian graphs
• A primal-dual approximation algorithm for generalized Steiner network problems
• Maximum matching and a polyhedron with 0,1-vertices
• Feasibility of Two Commodity Network Flows
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The parsimonious property of cut covering problems and its applications