Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14390
For citation please use:
Main Title: The Maximum Capacity of a Line Plan is Inapproximable
Author(s): Puhl, Christina
Stiller, Sebastian
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15617
http://dx.doi.org/10.14279/depositonce-14390
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We consider a basic subproblem which arises in line planning with upper capacities: How much can be routed maximally along all possible lines? The essence of this problem is the Path Constrained Network Flow (PCN) problem. We explore the complexity of this problem. In particular we show that it is as hard to approximate as MAX CLIQUE. We also show that the PCN problem is hard for special graph classes, interesting both from a complexity and from a practical perspective. Finally, we present a relevant graph class for which there is a polynomial-time algorithm.
Subject(s): complexity
approximation
railway optimization
line planning
Issue Date: 2007
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2007, 28
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-028-2007.pdf
Format: Adobe PDF | Size: 207.66 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.