We consider the fault-tolerant facility location problem with penalties. In this problem, we replicate each client \(v_{j}\) times. Some of these replicas are connected to opened facility, while others remain unconnected and are penalized. By employing a natural LP-rounding technique, we provide a 2-approximation algorithm for this problem. In this algorithm, we balance the connection cost and penalty cost by setting thresholds.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An LP-Based Approximation Algorithm for the Fault-Tolerant Facility Location Problem with Penalties

  • Yingying Guo,
  • Qiaoliang Li

摘要

We consider the fault-tolerant facility location problem with penalties. In this problem, we replicate each client \(v_{j}\) times. Some of these replicas are connected to opened facility, while others remain unconnected and are penalized. By employing a natural LP-rounding technique, we provide a 2-approximation algorithm for this problem. In this algorithm, we balance the connection cost and penalty cost by setting thresholds.