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] A Plant Location Guide for the Unsure: Approximation Algorithms for Min-Max Location Problems
    Anthony, Barbara
    Goyal, Vineet
    Gupta, Anupam
    Nagarajan, Viswanath
    MATHEMATICS OF OPERATIONS RESEARCH, 2010, 35 (01) : 79 - 101
  • [22] Approximation and Heuristic Algorithms for the Priority Facility Location Problem with Outliers
    Luo, Hang
    Han, Lu
    Shuai, Tianping
    Wang, Fengmin
    TSINGHUA SCIENCE AND TECHNOLOGY, 2024, 29 (06): : 1694 - 1702
  • [23] New Algorithms for Facility Location Problems on the Real Line
    Chen, Danny Z.
    Wang, Haitao
    ALGORITHMICA, 2014, 69 (02) : 370 - 383
  • [24] New Algorithms for Facility Location Problems on the Real Line
    Danny Z. Chen
    Haitao Wang
    Algorithmica, 2014, 69 : 370 - 383
  • [25] A new approximation algorithm for the multilevel facility location problem
    Gabor, Adriana F.
    van Ommeren, Jan-Kees C. W.
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (05) : 453 - 460
  • [26] Approximation Algorithms for Minimum-Load k-Facility Location
    Ahmadian, Sara
    Behsaz, Babak
    Friggstad, Zachary
    Jorati, Amin
    Salavatipour, Mohammad R.
    Swamy, Chaitanya
    ACM TRANSACTIONS ON ALGORITHMS, 2018, 14 (02)
  • [27] Approximation algorithms for minimum-load k-facility location
    Ahmadian S.
    Behsaz B.
    Friggstad Z.
    Jorati A.
    Salavatipour M.R.
    Swamy C.
    2018, Association for Computing Machinery, 2 Penn Plaza, Suite 701, New York, NY 10121-0701, United States (14)
  • [28] An Algorithm for the Facility Location Problems
    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
  • [29] Exact Algorithms for Integrated Facility Location and Production Planning Problems
    Sharkey, Thomas C.
    Geunes, Joseph
    Romeijn, H. Edwin
    Shen, Zuo-Jun Max
    NAVAL RESEARCH LOGISTICS, 2011, 58 (05) : 419 - 436
  • [30] Solving a class of facility location problems using genetic algorithms
    Chaudhry, SS
    He, SW
    Chaudhry, PE
    EXPERT SYSTEMS, 2003, 20 (02) : 86 - 91
12345