Station Location — Complexity and Approximation

5th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Steffen Mecke ; Anita Schöbel ; Dorothea Wagner

Others  :  http://drops.dagstuhl.de/opus/volltexte/2006/661/pdf/06001.MeckeSteffen.Paper.661.pdf
PID  :  6978

来源: CEUR

【 摘 要 】

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.