Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem

DOI10.1007/978-3-540-85097-7_25zbMath1168.90630OpenAlexW1492246659MaRDI QIDQ5505665

Mohammad Khairul Hasan, Hyunwoo Jung, Kyung-Yong Chwa

Publication date: 27 January 2009

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85097-7_25

zbMATH Keywords

approximation algorithmsfacility location problemprimal-dual algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (7)

Approximate robust optimization for the connected facility location problem ⋮ A quadratic time exact algorithm for continuous connected 2-facility location problem in trees ⋮ General network design: a unified view of combined location and network design problems ⋮ A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract) ⋮ Connected facility location via random facility sampling and core detouring ⋮ Deterministic sampling algorithms for network design ⋮ MIP models for connected facility location: a theoretical and computational study

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Improved Approximation Algorithm for Connected 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

This page was built for publication: Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem