direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Publikationen

Disser, Yann and Klimm, Max and Lübbecke, Elisabeth
Scheduling Bidirectional Traffic on a Path.
In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 406-418, 2015.  [pdf]


Günther, Elisabeth and König, Felix G. and Megow, Nicole
Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width.
Journal of Combinatorial Optimization, Vol. 27, pp. 164-181, 2014.  [pdf]


Günther, Elisabeth and Maurer, Olaf and Megow, Nicole and Wiese, Andreas
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio.
In Proceedings of the 24st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 118-128, 2013.  [pdf]


Günther, Elisabeth and König, Felix G. and Megow, Nicole
Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width.
In Approximation and Online Algorithms: 7th International Workshop, WAOA 2009, Lecture Notes in Computer Science, Vol. 5893, pp. 170-181, Springer, 2010.  [pdf]


Technical Reports

Lübbecke, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.
Ship Traffic Optimization for the Kiel Canal.
Preprint 4681, Optimization Online, 2014.


A New Approach to Competitive Analysis: Approximating the Optimal Competitive Ratio
Zitatschlüssel Report-031-2011
Autor Günther, Elisabeth and Maurer, Olaf and Megow, Nicole and Wiese, Andreas
Jahr 2011
Nummer 031
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We propose a new approach to competitive analysis by introducing the novel concept of online approximation schemes. Such scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possible competitive ratio up to an arbitrary accuracy. This strongly contrasts all previous manually obtained competitiveness results for algorithms and, most importantly, it reduces the search for the optimal competitive ratio to a question that a computer can answer. We believe that our method can also be applied to many other problems and yields a completely new and interesting view on online algorithms.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag

Extended Abstracts

Günther, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.
Challenges in Scheduling when Planning the Ship Traffic on the Kiel Canal.
In Proceedings of the 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011), 2011.  [pdf]


Günther, Elisabeth and Lübbecke, Marco E. and Möhring, Rolf H.
Ship Traffic Optimization for the Kiel Canal.
In Proceedings of the Seventh Triennial Symposium on Transportation Analysis (TRISTAN 2010), 2010.  [pdf]


Günther, Elisabeth and König, Felix G. and Megow, Nicole
The Bin Scheduling Problem.
In Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009), 2009.  [pdf]


Diplomarbeit

Günther, Elisabeth
Bin Scheduling: Partitionieren verformbarer Jobs mit Nebenbedingungen.
Diplomarbeit, Technische Universität Berlin, Deutschland, December 2008.
(Ausgezeichnet mit einem 3. Clara von Simson-Preis 2009)

Hinweis zum Copyright

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.