TU Berlin

Felix KönigPublications at COGA, TU Berlin

Page Content

to Navigation

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

Preprints

Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width
Citation key Report-020-2009
Author Günther, Elisabeth and König, Felix G. and Megow, Nicole
Year 2009
Number 020
Month jun
Note Approximation and Online Algorithms: 7th International Workshop, WAOA 2009, to appear as a volume of Lecture Notes in Computer Science, Springer-Verlag, 2009.
Institution Technische Universität Berlin, Institut für Mathematik
Abstract We study two related problems in non-preemptive scheduling and packing of malleable tasks with precedence constraints to minimize the makespan. We distinguish the scheduling variant, in which we allow the free choice of processors, and the packing variant, in which a task must be assigned to a contiguous subset of processors. For precedence constraints of bounded width, we completely resolve the complexity status for any particular problem setting concerning width bound and number of processors, and give polynomial-time algorithms with best possible performance. For both, scheduling and packing malleable tasks, we present an FPTAS for the NP-hard problem variants and exact algorithms for all remaining special cases. To obtain the positive results, we do not require the common monotonous penalty assumption on processing times, whereas our hardness results hold even when assuming this restriction. With the close relation between contiguous scheduling and strip packing, our FPTAS is the first (and best possible) constant factor approximation for (malleable) strip packing under special precedence constraints.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

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

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

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe