Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 1
Zurück zur Trefferliste

The Hypergraph Assignment Problem

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-14822
  • 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.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Ralf BorndörferORCiD, Olga Heismann
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:assignment; directed hypergraphs; hyperassignment
MSC-Klassifikation: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
Datum der Erstveröffentlichung:07.03.2012
Schriftenreihe (Bandnummer):ZIB-Report (12-14)
ISSN:1438-0064
Verlagspublikation:Appeared in: Discrete Optimization 15 (2015) pp. 15-25
DOI:https://doi.org/10.1016/j.disopt.2014.11.002
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.