A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

DOI10.1007/s10878-009-9227-8zbMath1180.90349MaRDI QIDQ1041431

Kyung-Yong Chwa, Mohammad Khairul Hasan, Hyunwoo Jung

Publication date: 2 December 2009

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

Full work available at URL: https://doi.org/10.1007/s10878-009-9227-8

zbMATH Keywords

greedy algorithm; approximation algorithms; primal-dual algorithms; facility location problems

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90B80: Discrete location and assignment

Related Items

Combinatorial approximation algorithms for the robust facility location problem with penalties, A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem

Cites Work

• Approximation algorithms for connected facility location problems
• Primal-dual algorithms for connected facility location problems
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• A General Approximation Technique for Constrained Forest Problems
• Provisioning a virtual private network
• Integer Programming and Combinatorial Optimization
• Algorithms - ESA 2003
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item