论文标题
统一的电容设施位置问题与处罚/异常值
Uniform Capacitated Facility Location Problems with Penalties/Outliers
论文作者
论文摘要
在本文中，我们提出了一个框架，用于设计使用LP-rounding的罚款/离群值的电容设施位置问题的近似算法。在处理异常值和处罚方面特别成功的原始偶尔技术在处理能力方面并不是很成功。另一方面，没有原始的双重解决方案能够打破电容设施位置问题（CFLP）的硬度。直到Grover等人最近的一项工作，LP连杆技术在处理能力方面也不是很成功。 \ cite {grovergkp18}。他们持续的因素近似违反了一个因素（$ 1 +ε$），这是有望在处理能力的同时。也就是说，我们的结果是通过将解决方案四舍五入到天然LP的再次表现出来的。通过LP-RONDING获得的解决方案易于与其他基于LP的算法集成。在本文中，我们应用框架来获得与Outier（CFLPO）的电容设施位置问题（CFLPO）（CFLPO）的第一个恒定因子近似值（CFLPO），并具有$ k $ - $ -Faciality的位置问题（C $ K $ k $ k $ k $ flpp）用于使用LP-lp-lp-rpound lp-Round lp-Round lp-Round。我们的解决方案在没有基数（$ k $）约束的问题（$ 2 +ε$）的问题的问题上遇到了轻微的违规行为（$ 1 +ε$）。对于异常变种，我们还会在异常值中造成微小的损失（$ 1 +ε$）。由于基本问题的硬度，违规是不可避免的。因此，我们通过解决这些问题的自然LP解决方案来实现最好的成就。据我们所知，CFLPO和C $ k $ FLPP的尚无结果。
In this paper, we present a framework to design approximation algorithms for capacitated facility location problems with penalties/outliers using LP-rounding. Primal-dual technique, which has been particularly successful in dealing with outliers and penalties, has not been very successful in dealing with capacities. On the other hand, no primal-dual solution has been able to break the hardness of capacitated facility location problem(CFLP). LP-rounding techniques had also not been very successful in dealing with capacities until a recent work by Grover et al. \cite{GroverGKP18}. Their constant factor approximation violating the capacities by a small factor ($1 + ε$) is promising while dealing with capacities.Though LP-rounding has not been very promising while dealing with penalties and outliers, we successfully apply it to deal with them along with capacities. That is, our results are obtained by rounding the solution to the natural LP once again exhibiting the power of LP-rounding technique. Solutions obtained by LP-rounding are easy to integrate with other LP-based algorithms.In this paper, we apply our framework to obtain first constant factor approximations for capacitated facility location problem with outlier (CFLPO) and capacitated $k$-facility location problem with penalty(C$k$FLPP) for hard uniform capacities using LP-rounding. Our solutions incur slight violations in capacities, ($1 + ε$) for the problems without cardinality($k$) constraint and ($2 + ε$) for the problems with the cardinality constraint. For the outlier variant, we also incur a small loss ($1 + ε$) in outliers. Due to the hardness of the underlying problems, the violations are inevitable. Thus we achieve the best possible by rounding the solution of natural LP for these problems. To the best of our knowledge, no results are known for CFLPO and C$k$FLPP.
