Approximation Algorithms for Bounded Facility Location Problems

被引：0
作者：
Piotr Krysta
Roberto Solis-Oba
机构：
[1] Max-Planck-Institut für Informatik,
来源：
Journal of Combinatorial Optimization | 2001年 / 5卷
关键词：
facility location; approximation algorithms; randomized algorithms; clustering;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The bounded k-median problem is to select in an undirected graph G = (V,E) a set S of k vertices such that the distance from any vertex v ∈ V to S is at most a given bound d and the average distance from vertices V\S to S is minimized. We present randomized algorithms for several versions of this problem and we prove some inapproximability results. We also study the bounded version of the uncapacitated facility location problem and present extensions of known deterministic algorithms for the unbounded version.
引用
收藏
页码：233 / 247
页数：14
相关论文
共 50 条
[21]   Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers [J].
Luo, Hang ;
Han, Lu ;
Shuai, Tianping ;
Wang, Fengmin .
TSINGHUA SCIENCE AND TECHNOLOGY, 2024, 29 (06) :1694-1702
[22]   A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems [J].
Anthony, Barbara ;
Goyal, Vineet ;
Gupta, Anupam ;
Nagarajan, Viswanath .
MATHEMATICS OF OPERATIONS RESEARCH, 2010, 35 (01) :79-101
[23]   New Algorithms for Facility Location Problems on the Real Line [J].
Danny Z. Chen ;
Haitao Wang .
Algorithmica, 2014, 69 :370-383
[24]   New Algorithms for Facility Location Problems on the Real Line [J].
Chen, Danny Z. ;
Wang, Haitao .
ALGORITHMICA, 2014, 69 (02) :370-383
[25]   A new approximation algorithm for the multilevel facility location problem [J].
Gabor, Adriana F. ;
van Ommeren, Jan-Kees C. W. .
DISCRETE APPLIED MATHEMATICS, 2010, 158 (05) :453-460
[26]   Approximation Algorithms for Graph Clustering Problems with Clusters of Bounded Size [J].
Il’ev, V.P. ;
Il’eva, S.D. ;
Kononov, A.V. .
Journal of Applied and Industrial Mathematics, 2024, 18 (04) :686-696
[27]   Approximation algorithms for facility location and k-median with differential privacy [J].
Wang, Lu ;
Science, Qilong Feng ;
Wang, Jianxin .
THEORETICAL COMPUTER SCIENCE, 2025, 1052
[28]   Approximation Algorithms for Minimum-Load k-Facility Location [J].
Ahmadian, Sara ;
Behsaz, Babak ;
Friggstad, Zachary ;
Jorati, Amin ;
Salavatipour, Mohammad R. ;
Swamy, Chaitanya .
ACM TRANSACTIONS ON ALGORITHMS, 2018, 14 (02)
[29]   An Algorithm for the Facility Location Problems [J].
An, Fengxian ;
Wang, Zongyao ;
Wang, Dongdong .
2010 2ND INTERNATIONAL ASIA CONFERENCE ON INFORMATICS IN CONTROL, AUTOMATION AND ROBOTICS (CAR 2010), VOL 1, 2010, :56-59
[30]   Constant work-space algorithms for facility location problems [J].
Bhattacharya, Binay K. ;
De, Minati ;
Nandy, Subhas C. ;
Roy, Sasanka .
DISCRETE APPLIED MATHEMATICS, 2020, 283 :456-472
12345