The Hypergraph Assignment Problem
Please always quote using this URN:urn:nbn:de:0296-matheon-11113
- The hypergraph assignment problem (HAP) is the generalization of assignments from directed graphs to directed hypergraphs. It serves, in particular, as a universal tool to model several train composition rules in vehicle rotation planning for long distance passenger railways. We prove that even for problems with a small hyperarc size and hypergraphs with a special partitioned structure the HAP is NP-hard and APX-hard. Further, we present an extended integer linear programming formulation which implies, e. g., all clique inequalities.
| Author: | Ralf Borndörfer, Olga Heismann |
|---|---|
| URN: | urn:nbn:de:0296-matheon-11113 |
| Referee: | Volker Mehrmann |
| Document Type: | Preprint, Research Center Matheon |
| Language: | English |
| Date of first Publication: | 2012/03/11 |
| Release Date: | 2012/03/11 |
| Tag: | assignment; directed hypergraphs; hyperassignment |
| Institute: | Research Center Matheon |
| Zuse Institute Berlin (ZIB) | |
| MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C65 Hypergraphs |
| Preprint Number: | 950 |
