direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Publications

Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width.

Günther, Elisabeth and König, Felix G. and Megow, Nicole

Journal of Combinatorial Optimization, Vol. 27, pp. 164-181, 2014.

Link to publication Link to original publication Download Bibtex entry

Approximation Algorithms for Capacitated Location Routing.

Harks, Tobias and Matuschke, Jannik and König, Felix G.

Transportation Science, Vol. 47, pp. 3-22, 2013.

Link to publication Link to original publication Download Bibtex entry

Integrated Sequencing and Scheduling in Coil Coating.

Höhn, Wiebke and König, Felix G. and Lübbecke, Marco E. and Möhring, Rolf H.

Management Science, Vol. 57, pp. 647–666, 2011.

Finalist for the EURO Excellence in Practice Award 2009.

Link to publication Link to original publication Download Bibtex entry

Multi-dimensional commodity covering for tariff selection in transportation.

König, Felix G. and Matuschke, Jannik and Richter, Alexander

In Daniel Delling and Leo Liberti (ed.)12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, OpenAccess Series in Informatics (OASIcs), Vol. 25, pp. 58–70, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.

Download Bibtex entry

1D Vehicle Scheduling with Conflicts.

Gellert, Torsten J. and König, Felix G.

In Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX 2011, pp. 107-115, Society for Industrial and Applied Mathematics, 2011.

Download Bibtex entry

Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width.

Günther, Elisabeth and König, Felix G. and Megow, Nicole

In Approximation and Online Algorithms: 7th International Workshop, WAOA 2009, Lecture Notes in Computer Science, Vol. 5893, pp. 170-181, Springer, 2010.

Download Bibtex entry

The Bin Scheduling Problem.

Günther, Elisabeth and König, Felix G. and Megow, Nicole

In Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009), 2009.

Download Bibtex entry

Sorting with Complete Networks of Stacks.

König, Felix G. and Lübbecke, Marco E.

In Algorithms and Computation: 19th International Symposium, ISAAC 2008, Lecture Notes in Computer Science, Vol. 5369, pp. 896-907, Springer, 2008.

Download Bibtex entry

Traffic Optimization under Route Constraints with Lagrangian Relaxation and Cutting Plane Methods.

König, Felix G.

In Operations Research Proceedings 2006, pp. 53-59, Springer, 2007.

Download Bibtex entry

Solutions to Real-World Instances of PSPACE-Complete Stacking.

König, Felix G. and Lübbecke, Marco E. and Möhring, Rolf H. and Schäfer, Guido and Spenke, Ines

In Algorithms - ESA 2007: 15th Annual European Symposium, Lecture Notes in Computer Science, Vol. 4698, pp. 729-740, Springer, 2007.

Download Bibtex entry

To top

Preprints

Sorting with Complete Networks of Stacks
Citation key Report-036-2007
Author König, Felix G. and Lübbecke, Marco E.
Year 2007
Address Stra\
Number 036
Month January
Note Algorithms and Computation: 19th International Symposium, ISAAC 2008, volume 5369 of Lecture Notes in Computer Science, pp. 896-907, Springer-Verlag, 2008.
Institution Technische Universität Berlin, Institut für Mathematik
Abstract Knuth introduced the problem of sorting with a sequence of stacks. Tarjan extended this idea to sorting with acyclic networks of stacks (and queues), where items to be sorted move from a source through the network to a sink while they may be stored temporarily at nodes (the stacks). Both characterized which permutations are sortable; but complexity of sorting was not an issue. In contrast, given a complete, thus cyclic, network of k >= 2 stacks, any permutation is obviously sortable. We ask how to do the sorting with a minimum number = 036, stacks. This is a natural algorithmic complement to the structural questions asked by Knuth, Tarjan, and others. It is the first time shuffles are considered in stack sorting – despite their practical importance. We show that it is NP-hard to approximate the minimum number = 036, networks of k >= 4 stacks, even when the problem is restricted to complete networks, by relating stack sorting to MIN-k-PARTITION on circle graphs (for which we prove a stronger inapproximability result). For complete networks, a simple merge sort algorithm achieves an approximation ratio of O(n log n) for k >= 3; however, closing the logarithmic gap to our lower bound appears to be an intriguing open question. Yet, on the positive side, we present a tight approximation algorithm which computes a solution with a linear approximation guarantee, using a resource augmentation to ak+1 stacks, given an a-approximation algorithm for coloring circle graphs. When there are constraints as to which items may be placed on top of each other, deciding about sortability becomes non-trivial again. We show that this problem is PSPACE-complete, for every fixed k >= 3.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

To top

Doctoral Thesis

Sorting with Objectives - Graph Theoretic Concepts in Industrial Optimization.

König, Felix G.

Doctoral thesis, Technische Universität Berlin, 2009.

Supervisors: Rolf H. Möhring and Peter Widmayer.

Link to publication Download Bibtex entry

To top

Diploma Thesis

Verkehrsoptimierung unter Routennebenbedingungen mit Lagrange-Relaxation und Schnittebenenverfahren.

König, Felix G.

Diploma thesis, Technische Universität Berlin, 2005.

Supervisor: Rolf H. Möhring. Won the GOR-Diplomarbeitspreis 2006 (Master Thesis Award of the German Association for Operations Research). In German.

Download Bibtex entry

To top

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions