Station Location - Complexity and Approximation

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

doi:10.4230/OASIcs.ATMOS.2005.661

Document

Station Location - Complexity and Approximation

Authors Steffen Mecke, Anita Schöbel, Dorothea Wagner

Part of: Volume: 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05) (ATMOS 2005)
Part of: Series: Open Access Series in Informatics (OASIcs)
Part of: Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2006-08-09

PDF

File

PDF

OASIcs.ATMOS.2005.661.pdf

Filesize: 280 kB
11 pages

Document Identifiers

DOI: 10.4230/OASIcs.ATMOS.2005.661
URN: urn:nbn:de:0030-drops-6612

Subject Classification

Keywords

Station Location
facility location
complexity
approximation

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/OASIcs.ATMOS.2005.661

Author Details

Steffen Mecke

Anita Schöbel

Dorothea Wagner

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail