Loading…
The Maximum Capacity of a Line Plan is Inapproximable
Puhl, Christina; Stiller, Sebastian
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
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.
