2004 | OriginalPaper | Buchkapitel
Solving Geometric Covering Problems by Data Reduction
verfasst von : Steffen Mecke, Dorothea Wagner
Erschienen in: Algorithms – ESA 2004
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider a scenario where stops are to be placed along an already existing public transportation network in order to improve its attractiveness for the customers. The core problem is a geometric set covering problem which is $\mathcal{NP}$-hard in general. However, if the corresponding covering matrix has the consecutive ones property, it is solvable in polynomial time. In this paper, we present data reduction techniques for set covering and report on an experimental study considering real world data from railway systems as well as generated instances. The results show that data reduction works very well on instances that are in some sense “close” to having the consecutive ones property. In fact, the real world instances considered could be reduced significantly, in most cases even to triviality. The study also confirms and explains findings on similar techniques for related problems.