• search hit 12 of 153
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.