Algorithms and Complexity Group

2005

Klaus Jansen, Monaldo Mastrollili, and Roberto Solis-Oba
Approximation algorithms for flexible job shop problems
International Journal of Foundations of Computer Science, volume 16, issue 2, 361-379, April 2005

Thomas Erlebach, Klaus Jansen, and Eike Seidel
Polynomial-time approximation schemes for geometric intersection graphs
SIAM Journal on Computing, volume 34, issue 6, 1302-1323, 2005

Klaus Jansen, Marek Karpinski, Andrzej Lingas, and Eike Seidel
Polynomial time approximation schemes for max-bisection on planar and geometric graphs
SIAM Journal on Computing, volume 35, issue 1, 110-119, 2005

Klaus Jansen and Lorant Porkolab
General multiprocessor task scheduling: approximate solutions in linear time
SIAM Journal on Computing, volume 35, issue 3, 519-530, 2005

Thomas Erlebach and Klaus Jansen
Conversion of coloring algorithms into maximum weight independent set algorithms
Discrete Applied Mathematics, volume 148, issue 1, 107-125, April 2005

Klaus Jansen, Monaldo Mastrolilli, and Roberto Solis-Oba
Approximation schemes for job shop scheduling problems with controllable processing times
European Journal of Operational Research, volume 167, Issue 2, 297-319, December 2005

Aleksei V. Fishkin, Olga Gerber, Klaus Jansen, and Roberto Solis-Oba
On packing squares with resource augmentation: maximizing the profit
Proceedings of Computing: The Australasian Theory Symposium (CATS 2005),
Newcastle, Australia, 30 January - 3 February, 2005, 61-67

Klaus Jansen and Rob van Stee
On strip packing with rotations
Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005),
Baltimore, USA, May 21 - 24, 2005, 755-761

Klaus Jansen and Hu Zhang
Scheduling malleable tasks with precedence constraints
Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005),
Las Vegas, NV, USA, July 17 - 20, 2005, 86-95

Aleksei Fishkin, Olga Gerber, Klaus Jansen, and Roberto Solis-Oba
Packing weighted rectangles into a square
Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005),
Gdansk, Poland, August 29 - September 2, 2005, Springer LNCS 3618, 352-363

Aleksei Fishkin, Klaus Jansen, S. Sevastianov, and R. Sitters
Preemptive scheduling of independent jobs on identical parallel machines subject to migration delay
Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005),
Mallorca, Spain, October 3-6, 2005, Springer LNCS 3669, 580-591

Aleksei Fishkin, Olga Gerber, and Klaus Jansen
On efficient weighted rectangle packing with large resources
Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005),
Sanya, Hainan, China, December 19 - 21, 2005, Springer LNCS 3827, 1039-1050

Klaus Jansen and Hu Zhang
An approximation algorithm for scheduling malleable tasks under general precedence constraints
Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005),
Sanya, Hainan, China, December 19 - 21, 2005, Springer LNCS 3827, 236-245