论文标题
定位充电站：连接，电容和奖励
Locating Charging Stations: Connected, Capacitated and Prize- Collecting
论文作者
论文摘要
在本文中，我们研究了将充电站问题作为设施位置问题及其变体（$ k $ -Median，$ k $ - 易期位置和$ k $ - center）。我们研究这些问题的连通性和容量限制。 对于所有这些问题，文献中已经研究了能力和连通性约束。当两个约束都存在时，我们给出了第一个常数因子近似值。扩展/修改问题的连接变体所使用的技术包括能力或问题的电容变体以包括连接性是一项乏味而挑战性的任务。在本文中，我们通过将问题减少到基本研究的问题，将它们作为黑匣子解决并结合获得的解决方案来结合两个约束。我们还将这两个约束结合在奖励收集设置中。 在奖励收集设置中，当存在一个约束时，甚至没有研究问题。我们也为它们提供了恒定的因子近似。
In this paper, we study locating charging station problem as facility location problem and its variants ($k$-Median, $k$-Facility location and $k$-center). We study the connectivity and the capacity constraints in these problem. Capacity and connectivity constraints have been studied in the literature separately for all these problems. We give first constant factor approximations when both the constraints are present. Extending/modifying the techniques used for connected variants of the problem to include capacities or for capacitated variants of problem to include connectivity is a tedious and challenging task. In this paper, we combine the two constraints by reducing the problem to underlying well studied problems, solving them as black box and combine the obtained solutions. We also, combine the two constraints in the prize-collection set up. In the prize-collecting set up, the problems are not even studied when one of the constraint is present. We present constant factor approximation for them as well.
