License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2005.661
URN: urn:nbn:de:0030-drops-6612
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/661/
Go to the corresponding OASIcs Volume Portal

Mecke, Steffen ; Schöbel, Anita ; Wagner, Dorothea

Station Location - Complexity and Approximation

pdf-format:
06001.MeckeSteffen.Paper.661.pdf (0.3 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{mecke_et_al:OASIcs:2006:661,
  author =	{Steffen Mecke and Anita Sch{\"o}bel and Dorothea Wagner},
  title =	{{Station Location - Complexity and Approximation}},
  booktitle =	{5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-00-2},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{2},
  editor =	{Leo G. Kroon and Rolf H. M{\"o}hring},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/661},
  URN =		{urn:nbn:de:0030-drops-6612},
  doi =		{10.4230/OASIcs.ATMOS.2005.661},
  annote =	{Keywords: Station Location, facility location, complexity, approximation}
}

Keywords: Station Location, facility location, complexity, approximation
Collection: 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05)
Issue Date: 2006
Date of publication: 09.08.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI