DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2005.661

Station Location - Complexity and Approximation

Authors: Steffen Mecke, Anita Schöbel, and Dorothea Wagner

Published in: OASIcs, Volume 2, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (2006)

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.

Cite as

Steffen Mecke, Anita Schöbel, and Dorothea Wagner. Station Location - Complexity and Approximation. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05). Open Access Series in Informatics (OASIcs), Volume 2, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

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

Search Results

Documents authored by Mecke, Steffen

Station Location - Complexity and Approximation

Abstract

Cite as

Thanks for your feedback!

Could not send message