Single facility collection depots location problem in the plane

详细信息    查看全文

• 作者：Robert Benkoczi ; Binay K. Bhattacharya ; S ; ip Das ; Jeff Sember
• 关键词：Facility location ; Minmax ; Minsum ; Voronoi diagram ; Approximation algorithms ; Coresets
• 刊名：Computational Geometry
• 出版年：2009
• 出版时间：July 2009
• 年：2009
• 卷：42
• 期：5
• 页码：403-418
• 全文大小：588 K

文摘

In this paper we consider an extension of the classical facility location problem where besides n weighted customers, a set of p collection depots are also given. In this setting the service of a customer consists of the travel of a server to the customer and return back to the center via a collection depot. We have analyzed the problem and showed that the collection depots problem using the Euclidean metric can be transformed to O(p²n²) number of different classical facility location problems and this bound is tight. We then show the existence of small coresets for these problems. These coresets are then used to provide (1+)-factor approximation algorithms which have linear running times for fixed customer weights and .