Approximating minimum-cost graph problems with spanning tree edges

DOI10.1016/0167-6377(94)90067-1zbMath0823.90125OpenAlexW2047085423MaRDI QIDQ1892100

Michel X. Goemans, David P. Williamson

Publication date: 6 July 1995

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

Full work available at URL: https://doi.org/10.1016/0167-6377(94)90067-1

zbMATH Keywords

location-routing problemsminimum-cost spanning tree2- matchingNP-hard minimum-cost graph problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (9)

A constant-factor approximation for directed latency in quasi-polynomial time ⋮ Approximation Algorithms for a Network Design Problem ⋮ Eulerian location problems ⋮ A survey of the standard location-routing problem ⋮ An approximation algorithm for network design problems with downwards-monotone demand functions ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ Improving the approximation ratio for capacitated vehicle routing ⋮ Approximation algorithms for minimum tree partition ⋮ A 3/2-approximation algorithm for some minimum-cost graph problems

Cites Work

• A matching problem with side conditions
• Hamiltonian location problems
• Geometric algorithms and combinatorial optimization
• A greedy heuristic for a minimum-weight forest problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• A primal-dual approximation algorithm for generalized Steiner network problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating minimum-cost graph problems with spanning tree edges