The Maximum Capacity of a Line Plan is Inapproximable
dc.contributor.author | Puhl, Christina | |
dc.contributor.author | Stiller, Sebastian | |
dc.date.accessioned | 2021-12-17T10:07:27Z | |
dc.date.available | 2021-12-17T10:07:27Z | |
dc.date.issued | 2007 | |
dc.description.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. | en |
dc.identifier.issn | 2197-8085 | |
dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15617 | |
dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14390 | |
dc.language.iso | en | en |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
dc.subject.ddc | 510 Mathematik | en |
dc.subject.other | complexity | en |
dc.subject.other | approximation | en |
dc.subject.other | railway optimization | en |
dc.subject.other | line planning | en |
dc.title | The Maximum Capacity of a Line Plan is Inapproximable | en |
dc.type | Research Paper | en |
dc.type.version | submittedVersion | en |
tub.accessrights.dnb | free | en |
tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
tub.affiliation.institute | Inst. Mathematik | de |
tub.publisher.universityorinstitution | Technische Universität Berlin | en |
tub.series.issuenumber | 2007, 28 | en |
tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1