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

DOI10.1007/978-3-540-85097-7_25MaRDI QIDQ5505665zbMATH OpenOpenAlexFDO

Authors Hyunwoo Jung, Mohammad Khairul Hasan, 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) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
• Primal-dual algorithms for connected facility location problems
• scientific article; zbMATH DE number 1947062
• The online connected facility location problem
• Improved Approximation Algorithm for Connected Facility Location Problems

Cites work

• scientific article; zbMATH DE number 5764866 (Why is no real title available?)
• scientific article; zbMATH DE number 1303535 (Why is no real title available?)
• scientific article; zbMATH DE number 1947060 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A new greedy approach for facility location problems
• A simpler and better derandomization of an approximation algorithm for single source rent-or-buy
• Algorithms - ESA 2003
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Greedy Strikes Back: Improved Facility Location Algorithms
• Improved Approximation Algorithm for Connected Facility Location Problems
• Improved Approximation Algorithms for the Uncapacitated Facility Location Problem
• Integer Programming and Combinatorial Optimization
• Primal-dual algorithms for connected facility location problems
• Provisioning a virtual private network: a network design problem for multicommodity flow

Cited in

(11)

• Deterministic sampling algorithms for network design
• Approximate robust optimization for the connected facility location problem
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees (extended abstract)
• A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
• A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
• MIP models for connected facility location: a theoretical and computational study
• General network design: a unified view of combined location and network design problems
• scientific article; zbMATH DE number 1947062 (Why is no real title available?)
• Improved Approximation Algorithm for Connected Facility Location Problems
• Primal-dual algorithms for connected facility location problems
• Connected facility location via random facility sampling and core detouring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5505665)