Algorithms and Complexity Group

2001

Thomas Erlebach and Klaus Jansen
The complexity of path coloring and call scheduling
Theoretical Computer Science 255, 33-50, 2001

Klaus Jansen and Lorant Porkolab
Improved approximation schemes for scheduling unrelated parallel machines
Mathematics of Operations Research 26, 324-338, 2001

Thomas Erlebach and Klaus Jansen
The maximum edge-disjoint paths problem in bidirected paths
SIAM Journal on Discrete Mathematics 14, 326-355, 2001

Klaus Jansen, Monaldo Mastrolilli, and Roberto Solis-Oba
Job shop scheduling problems with controllable processing times
Proceedings of the 7th Italian Conference on Theoretical Computer Science (ICTCS 2001),
Torino, Italy, 2001, Springer LNCS 2202, 107-122

Aleksei V.Fishkin, Klaus Jansen, and Monaldo Mastrolilli
Grouping techniques for scheduling problems: simpler and faster
Proceedings of the 9th Anual European Symposium (ESA 2001),
Arhus, Denmark, August 28 - 31, 2001, Springer LNCS 2161, 206-217 

Jirí Fiala, Aleksei V.Fishkin, and Fedor Fomin
Off-line and on-line distance constrained labelings of disk graphs
Proceedings of the 9th Anual European Symposium on Algorithms (ESA 2001),
Arhus, Denmark, August 28 - 31, 2001, Springer LNCS 2161, 464-475 

Klaus Jansen
Approximation algorithms for fractional covering and packing problems, and applications, (invited talk)
Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (FCT 2001),
Riga, Latvia, August 22 - 24, 2001, Springer LNCS 2138, 14

Aleksei V. Fishkin, Klaus Jansen, and Lorant Porkolab
On minimizing average weighted completion time: A PTAS for scheduling general multiprocessor tasks
Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (FCT 2001),
Riga, Latvia, August 22 - 24, 2001, Springer LNCS 2138, 495-507

Aleksei V. Fishkin, Klaus Jansen, and Lorant Porkolab
On minimizing average weighted completion time of multiprocessor tasks with release dates
Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 2001),
Crete, Greece July 8 - 12, 2001, Springer LNCS 2076, 875-886 

Jirí Fiala, Klaus Jansen,  Van Bang Le, and Eike Seidel
Graph subcolorings: complexity and algorithms
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science(WG 2001),
Boltenhagen, Germany, June 14 - 16, 2001, Springer LNCS 2204, 154-165

Klaus Jansen, Marek Karpinski, Andrzej Lingas, and Eike Seidel
Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs
18th Annual Symposium on Theoretical Aspects of Computer Science(STACS 2001),
Dresden, Germany, February 15 - 17, 2001, Springer LNCS 2010, 365-375

Thomas Erlebach, Klaus Jansen, and Eike Seidel
Polynomial-time approximation schemes for geometric graphs
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms(SODA 2001),
Washington, DC, USA, January 7 - 9, 2001, ACM-DL, 671-679