direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Karl Däubel

Lupe

Wissenschaftlicher Mitarbeiter

Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik, Sekr. MA 5-2

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Germany

E-Mail:
Tel.: +49 (0)30 314-78657
Fax: +49 (0)30 314-25191
Raum: MA 514
Sprechzeiten: nach Vereinbarung

Forschungsinteressen

Kombinatorische Optimierung und Algorithmen:

  • Unsplittable Flows/Ring Loading
  • Anwendungen in der Logistik für große Netzwerke
  • Inkrementelle Flüsse

Veröffentlichungen

An Improved Upper Bound for the Ring Loading Problem
Zitatschlüssel Daeubel2020
Autor Däubel, Karl
Buchtitel Approximation and Online Algorithms
Seiten 89–105
Jahr 2020
DOI 10.1007/978-3-030-39479-0_7
Herausgeber Springer International Publishing
Zusammenfassung The Ring Loading Problem emerged in the 1990s to model an important special case of telecommunication networks (SONET rings) which gained attention from practitioners and theorists alike. Given an undirected cycle on n nodes together with non-negative demands between any pair of nodes, the Ring Loading Problem asks for an unsplittable routing of the demands such that the maximum cumulated demand on any edge is minimized. Let L be the value of such a solution. In the relaxed version of the problem, each demand can be split into two parts where the first part is routed clockwise while the second part is routed counter-clockwise. Denote with L* the maximum load of a minimum split routing solution. In a landmark paper, Schrijver, Seymour and Winkler [SSW '98] showed that L <= L* + 3/2 D, where D is the maximum demand value. They also found (implicitly) an instance of the Ring Loading Problem with L = L* + 101/100 D. Recently, Skutella [Sku '16] improved these bounds by showing that L <= L* + 19/14 D, and there exists an instance with L = L* + 11/10 D. We contribute to this line of research by showing that L <= L* + 13/10 D. We also take a first step towards lower and upper bounds for small instances.
Link zur Originalpublikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.