The Maximum Capacity of a Line Plan is Inapproximable

dc.contributor.authorPuhl, Christina
dc.contributor.authorStiller, Sebastian
dc.date.accessioned2021-12-17T10:07:27Z
dc.date.available2021-12-17T10:07:27Z
dc.date.issued2007
dc.description.abstractWe 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.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15617
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14390
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.othercomplexityen
dc.subject.otherapproximationen
dc.subject.otherrailway optimizationen
dc.subject.otherline planningen
dc.titleThe Maximum Capacity of a Line Plan is Inapproximableen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2007, 28en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Report-028-2007.pdf
Size:
207.66 KB
Format:
Adobe Portable Document Format

Collections