Approximation algorithms for connected facility location problems

DOI10.1007/s10878-007-9130-0zbMath1159.90022OpenAlexW2034619144MaRDI QIDQ1016041

Hyunwoo Jung, Mohammad Khairul Hasan, Kyung-Yong Chwa

Publication date: 4 May 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9130-0

zbMATH Keywords

integer programmingapproximation algorithmsSteiner treeconnected facility locationLP-rounding

Mathematics Subject Classification ID

Integer programming (90C10) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract) ⋮ Approximate the lower-bounded connected facility location problem ⋮ Branch-and-cut-and-price for capacitated connected facility location ⋮ A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem ⋮ A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual algorithms for connected facility location problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Simpler and better approximation algorithms for network design
• A General Approximation Technique for Constrained Forest Problems
• Provisioning a virtual private network
• Algorithm Theory - SWAT 2004
• Improved Approximation for Single-Sink Buy-at-Bulk