文章基本信息

标题：Station Location - Complexity and Approximation
本地全文：下载
作者：Mecke, Steffen ; Schöbel, Anita ; Wagner, Dorothea 等
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2005
卷号：2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider a geometric set covering problem. In its original form it consists of adding stations to an existing geometric transportation network so that each of a given set of settlements is not too far from a station. The problem is known to be NP-hard in general. However, special cases with certain properties have been shown to be efficiently solvable in theory and in practice, especially if the covering matrix has (almost) consecutive ones property. In this paper we are narrowing the gap between intractable and efficiently solvable cases of the problem. We also present an approximation algorithm for cases with almost consecutive ones property.
关键词：Station Location; facility location; complexity; approximation