Algorithms and Complexity Group

Publications

2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998-1988

2000

Klaus Jansen
Approximation results for the optimum cost chromatic partition problem
Journal of Algorithms 34, 54-89, 2000

Hans Bodlaender and Klaus Jansen
On the complexity of the maximum cut problem
Nordic Journal of Computing 7, 14-31, 2000

Klaus Jansen, Marek Karpinski, and Andrzej Lingas
A polynomial time approximation scheme for max-bisection on planar graphs
Electronic Colloquium on Computational Complexity (ECCC) 7(64), 2000

Klaus Jansen and Lorant Porkolab
Preemptive parallel task scheduling in O(n)+poly(m) time
11th International Symposium on Algorithms and Computation (ISAAC 2000),
Taipeh, Taiwan, December 19 - 21, 2000, Springer LNCS 1969,  398-409

Foto Afrati, Evripidis Bampis, Aleksei V. Fishkin, Klaus Jansen, and Claire Kenyon
Scheduling to minimize the average completion time of dedicated tasks
20th Conference of Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2000),
New Delhi, India, December 13 - 15,  2000, Springer LNCS 1974,  454-464

Thomas Erlebach and Klaus Jansen
Implementation of approximation algorithms for weighted and unweighted edge-disjoint paths in bidirected trees
4th International Workshop on Algoritm Engineering (WAE 2000),
Saarbrücken, Germany, September 5 - 8, 2000, Springer LNCS 1982, 195-206

Klaus Jansen and Lorant Porkolab
Preemptive scheduling on dedicated processors: applications of fractional graph coloring
25th International Symposium on Mathematical Foundations of Computer Science (MFCS 2000),
Bratislava, Slovakia, August 28 - September 1, 2000, Springer LNCS 1893, 446-455

Klaus Jansen and Monaldo Mastrolilli
Parallel machine scheduling problems with controllable processing times
Workshop on Approximation and Randomization Algorithms in Communication Networks, (ARACNE 2000),
Geneva, Carleton Scientific, 2000, 179-190

Thomas Erlebach and Klaus Jansen
Conversion of coloring algorithms into maximum weight independent set algorithms
Workshop on Approximation and Randomization Algorithms in Communication Networks, (ARACNE 2000),
Geneva, Carleton Scientific, 2000, 135-146

Klaus Jansen and Lorant Porkolab
Polynomial time approximation schemes for general multiprocessor job shop scheduling
27th International Colloquium on Automata, Languages and Programming (ICALP 2000),
Geneva, Switzerland, July 9 - 15, 2000, Springer LNCS 1853, 878-889

Klaus Jansen, Monaldo Mastrolilli, and Roberto Solis-Oba
Approximation algorithms for flexible job shop problems
4th Latin American Theoretical Informatics (LATIN 2000),
Punta del Este, Uruguay, April 10 - 14, 2000, Springer LNCS 1776, 68-77

Klaus Jansen and Maxim Sviridenko
Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem
17th Symposium on Theoretical Aspects of Computer Science (STACS 2000),
Lille, France, February 17 - 19, 2000, Springer LNCS 1770, 455-465

Copyright

Copyright and all rights concerning the documents distributed by this server rest with the authors or other copyright holders. They may not be reposted without the copyright holders' explicit permission. The authors offer these documents here solely to ensure that others working in the same field have ready access to their scholarly or technical work on a noncommercial basis, and on condition that all users copying these documents do so respecting the terms and constraints set by the copyright.