【24h】

Approximation Algorithms for Movement Repairmen

机译:运动修理工的近似算法

获取原文
获取原文并翻译 | 示例

摘要

In the Movement Repairmen (MR) problem we are given a metric space (V, d) along with a set R of k repairmen r_1, r_2, …, r_k with their start depots s_1,S_2,…,s_t ∈ V and speeds v_i,v_2, …,v_k ≥ 0 respectively and a set C of m clients c_i, c_2,…, c_m having start locations s'_i, s'_2, …, s'_m ∈ V and speeds v'_i, v'_2, …, v'_m ≥ 0 respectively. If t is the earliest time a client c_j is collocated with any repairman (say, r_i) at a node u, we say that the client is served by n at u and that its latency is t. The objective in the (Sum-MR) problem is to plan the movements for all repairmen and clients to minimize the sum (average) of the clients latencies. The motivation for this problem comes, for example, from Amazon Locker Delivery [Ama10] and USPS gopost [Ser10]. We give the first O(log n)-approximation algorithm for the Sum-MR problem. In order to solve Sum-MR we formulate an LP for the problem and bound its integrality gap. Our LP has exponentially many variables, therefore we need a separation oracle for the dual LP. This separation oracle is an instance of Neighborhood Prize Collecting Steiner Tree (NPCST) problem in which we want to find a tree with weight at most L collecting the maximum profit from the clients by visiting at least one node from their neighborhoods. The NPCST problem, even with the possibility to violate both the tree weight and neighborhood radii, is still very hard to approximate. We deal with this difficulty by using LP with geometrically increasing segments of the time line, and by giving a tricriteria approximation for the problem. The rounding needs a relatively involved analysis. We give a constant approximation algorithm for Sum-MR in Euclidean Space where the speed of the clients differ by a constant factor. We also give a constant approximation for the makespan variant.
机译:在运动修理工(MR)问题中,我们给定了度量空间(V,d)以及一组k个修理工r_1,r_2,…,r_k的R,其起始站点s_1,S_2,…,s_t∈V和速度v_i ,v_2,…,v_k≥0且一组C个m个客户端c_i,c_2,…,c_m的起始位置为s'_i,s'_2,...,s'_m∈V并且速度为v'_i,v'_2 ,…,v'_m≥0。如果t是最早的时间,客户端c_j与任何修理工(例如,r_i)在节点u上并置,我们说客户端在n处由n服务,并且其延迟时间为t。 (Sum-MR)问题的目的是为所有维修人员和客户计划移动,以最大程度地减少客户等待时间的总和(平均值)。出现此问题的动机例如来自Amazon Locker Delivery [Ama10]和USPS gopost [Ser10]。我们给出了Sum-MR问题的第一个O(log n)近似算法。为了解决Sum-MR,我们为该问题制定了LP并​​限制了其完整性差距。我们的LP具有成倍的指数变量,因此我们需要对偶LP进行分隔。这个分离预言是邻域奖品收集斯坦纳树(NPCST)问题的一个实例,在该问题中,我们希望找到一个权重最大为L的树,通过访问其邻域中的至少一个节点来收集最大的利润。 NPCST问题,即使有可能同时侵犯树的权重和邻域半径,仍然很难估计。我们通过将LP与时间线的几何增长段配合使用并给出问题的三准则近似来解决此难题。四舍五入需要一个相对复杂的分析。我们给出了欧几里德空间中Sum-MR的恒定近似算法,其中客户端的速度相差一个恒定因子。我们还为makepan变量提供了一个恒定的近似值。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号