Refine
Year of publication
- 2012 (1) (remove)
Document Type
- ZIB-Report (1)
Language
- English (1)
Has Fulltext
- yes (1) (remove)
Is part of the Bibliography
- no (1)
Keywords
- directed hypergraphs (1) (remove)
Institute
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.