Algorithms and Complexity Group

2009

Klaus Jansen
Parameterized approximation scheme for the multiple knapsack problem
SIAM Journal on Computing 39(4), 1392-1412, 2009

Klaus Jansen and Roberto Solis-Oba
Rectangle packing with one-dimensional resource augmentation
Discrete Optimization 6 , 310-323, 2009

Florian Diedrich, Klaus Jansen, Ulrich M. Schwarz, and Denis Trystram
A survey on approximation algorithms for scheduling with machine unavailability
Algorithmics of Large and Complex Networks 5515, 50-64, 2009

Thomas Erlebach, Klaus Jansen, Christos Kaklamanis, and Giuseppe Persiano
Directed tree networks
Encyclopedia of Optimization, 716-725, 2009

Klaus Jansen
Parameterized approximation scheme for the multiple knapsack problem
Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA 2009),
New York, USA, January 4 - 6,  2009

Florian Diedrich and Klaus Jansen
Improved approximation algorithms for scheduling with fixed jobs
Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA 2009),
New York, USA, January 4 - 6, 2009

Klaus Jansen
An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009),
Rhodes, Greece, July 5 - 12, 2009

Klaus Jansen, Lars Prädel, and Ulrich M. Schwarz
Two for One: Tight approximation of 2D Bin Packing
Proceedings of the 20th Workshop on Algorithms And Data Structures (WADS 2009),
Banff, Canada, August 21 - 23, 2009

Marin Bougeret, Pierre Francois Dutot, Klaus Jansen, Christina Otte, and Denis Trystram
Approximation Algorithms for Multiple Strip Packing
7th Workshop on Approximation and Online Algorithms (WAOA),
Copenhagen, Denmark, September 10 - 11, 2009

Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel, and Maxim Sviridenko
A Structural Lemma in 2-Dimensional Packing, and its Implications on Approximability
20th International Symposium on Algorithms and Computation (ISAAC 2009),
Hawaii, USA, December 16 - 18, 2009


Technical Reports

Florian Diedrich and Klaus Jansen
Tight approximation algorithms for scheduling with fixed jobs and non-availability
Technical Report 0902, Institut für Informatik, Christian-Albrechts-Universität zu Kiel, February 2009

Klaus Jansen, Lars Prädel and Ulrich Michael Schwarz
A 2-approximation for 2D bin packing
Technical Report 0904, Institut für Informatik, Christian-Albrechts-Universität zu Kiel, March 2009

Klaus Jansen and Hu Zhang
Scheduling Malleable Tasks with Precedence Constraints
Technical Report 0906, Institut für Informatik, Christian-Albrechts-Universität zu Kiel, March 2009

Klaus Jansen and Lars Prädel
How to Maximize the Total Area of Rectangles Packed into a Rectangle?
Technical Report 0908, Institut für Informatik, Christian-Albrechts-Universität zu Kiel, March 2009

Klaus Jansen
Parameterized Approximation Scheme for the Multiple Knapsack Problem
Technical Report 0909, Institut für Informatik, Christian-Albrechts-Universität zu Kiel, March 2009

Klaus Jansen
A fast approximation scheme for the multiple knapsack problem
Technical Report 0916, Institut für Informatik, Christian-Albrechts-Universität zu Kiel, July 2009