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

2003

Klaus Jansen and Roberto Solis-Oba
An asymptotic fully polynomial time approximation scheme for bin covering
Theoretical Computer Science 306, 543-551, 2003

Jirí Fiala, Klaus Jansen, Van Bang Le, and Eike Seidel
Graph subcolorings: complexity and algorithms
SIAM Journal on Discrete Mathematics 16(4), 635-650, 2003

Klaus Jansen
The mutual exclusion scheduling problem for permutation and comparability graphs
Information and Computation 180, 71-81, 2003

Klaus Jansen and Lorant Porkolab
Computing optimal preemptive schedules for parallel tasks: linear programming approaches
Mathematical Programming 95(3), 617-630, 2003

Klaus Jansen
Approximate strong separation with application in fractional graph coloring and preemptive scheduling
Theoretical Computer Science 302(1-3), 239-256, 2003

Klaus Jansen, Roberto Solis-Oba, and Maxim Sviridenko
Makespan minimization in job shops: a linear time approximation scheme
SIAM Journal on Discrete Mathematics 16(2), 288-300, 2003

Guochuan Zhang, Xiao-Qiang Cai, and C.K. Wong
Optimal on-line algorithms for scheduling on parallel batch processing machines
IIE Transactions on Scheduling and Logistics 35(2), 175-181, 2003

Deshi Ye and Guochuan Zhang
On-line scheduling with extendable working time on a small number of machines
Information Processing Letters 85(4), 171-177, 2003

Aleksei Fishkin and Guochuan Zhang
On maximizing the throughput of multiprocessor tasks
Theoretical Computer Science 302(1-3), 319-335, 2003

Miroslav Chlebík and Janka Chlebíková
Inapproximability results for bounded variants of optimization problems
Electronic Colloquium on Computational Complexity, Report No. 26, 2003 

Aleksei V. Fishkin, Klaus Jansen, and Monaldo Mastrolilli
On minimizing average weighted completion time: a PTAS for job shop scheduling with release dates
Proceedings of the 14th International Symposium on Algorithms and Computation (ISAAC 2003),
Kyoto, Japan, December 15 - 17, 2003, Springer LNCS 2906, 319-328

Miroslav Chlebík and Janka Chlebíková
Approximation hardness of minimum edge dominating set and minimum maximal matching
Proceedings of the 14th International Symposium on Algorithms and Computation (ISAAC 2003),
Kyoto, Japan, December 15 - 17, 2003, Springer LNCS 2906, 415-424

Deshi Ye and Guochuan Zhang
On-line scheduling of parallel jobs with dependencies on 2-dimensional meshes
Proceedings of the 14th International Symposium on Algorithms and Computation (ISAAC 2003),
Kyoto, Japan, December 15 - 17, 2003, Springer LNCS 2906, 329-338

Deshi Ye and Guochuan Zhang
On-line extensible bin packing with unequal bin sizes
Proceedings of the Workshop on Approximation and online Algorithms (WAOA 2003),
Budapest, Hungary, September 15 - 18, 2003, Springer LNCS 2909, 235-247

Janka Chlebíková and Klaus Jansen
The d-precoloring problem on k-degenerate graphs
Proceedings of the 2th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2003),
Prag, September 8 - 12, 2003, 81-85

Klaus Jansen and Roberto Solis-Oba
Approximation algorithms for scheduling jobs with chain precedence constraints
Proceedings of the 5th International Conference on Parallel Processing and Applied Mathematics (PPAM 2003),
Czestochowa, Poland, September 7 - 10, 2003, Springer LNCS 3019, 105-112 

Miroslav Chlebík and Janka Chlebíková
Inapproximability results for bounded variants of optimization problems
Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT 2003),
Malmo, Sweden, August 12 - 15, 2003, Springer LNCS 2751, 123-145

Miroslav Chlebík and Janka Chlebíková
Approximation hardness for small occurrence instances of NP-hard problems
Proceedings of the 5th Conference on Algorithms and Complexity (CIAC 2003),
Rome, Italy, May 28 - 30, 2003, Springer LNCS 2653, 52-164

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.