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

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

Mohammad Khairul Hasan, Hyunwoo Jung, Kyung-Yong Chwa

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 algorithmapproximation algorithmsprimal-dual algorithmsfacility location problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Related Items (3)

Combinatorial approximation algorithms for the robust facility location problem with penalties ⋮ Approximate the lower-bounded connected facility location problem ⋮ 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

This page was built for publication: A 6.55 factor primal-dual approximation algorithm for the connected facility location problem