Algorithms and Complexity Group

2004

Klaus Jansen
Scheduling malleable parallel tasks: an asymptotic fully polynomial-time approximation scheme
Algorithmica 39, 59-81, January 2004

Klaus Jansen and Lorant Porkolab
Preemptive scheduling with dedicated processors: applications of fractional graph coloring
Journal of Scheduling 7, 35-48, January - February 2004

Klaus Jansen and Monaldo Mastrolilli
Approximation schemes for parallel machine scheduling problems with controllable processing times
Computers and Operations Research 31, 1565-1581, September 2004

Klaus Jansen and Guochuan Zhang
On rectangle packing: maximizing benefits
Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004),
New Orleans, January 11 - 13, 2004, 204-213

Miroslav Chlebík and Janka Chlebíková
On approximability of the independent set problem for low degree graphs
Proceedings of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO 2004),
Smolenice Castle, Slovakia, June 21 - 23, 2004, Springer LNCS 3104, 47-56 

Deshi Ye and Guochuan Zhang
On-line scheduling of parallel jobs
Proceedings of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO 2004),
Smolenice Castle, Slovakia, June 21 - 23, 2004, Springer LNCS 3104, 279-290

Deshi Ye and Hu Zhang
The range assignment problem in static ad-hoc networks on metric spaces
Proceedings of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO 2004),
Smolenice Castle, Slovakia, June 21 - 23, 2004, Springer LNCS 3104,  291-302

Klaus Jansen and Guochuan Zhang
Maximizing the number of packed rectangles
Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004),
Humlebæk, Denmark, July 8 - 10, 2004, Springer LNCS 3111, 362-371

Klaus Jansen
Approximation algorithms for the general max-min resource sharing problem: faster and simpler
Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004),
Humlebæk, Denmark, July 8 - 10, 2004, Springer LNCS 3111, 311-322

Miroslav Chlebík and Janka Chlebíková
Improvement of nemhauser-trotter theorem and its applications in parametrized complexity
Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004),
Humlebæk, Denmark, July 8 - 10, 2004, Springer LNCS 3111, 174-186

Klaus Jansen
Approximation algorithms for mixed fractional packing and covering problems
Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science (TCS 2004),
Toulouse, France, August 23 - 26, 2004, 223-236

Olga Gerber, Aleksei V. Fishkin, and Klaus Jansen
On weighted rectangle packing with large resources
Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science (TCS 2004),
Toulouse, France, August 23 - 26, 2004, 237-250

Hu Zhang
Solving packing problem with weaker block solvers
Proceedings of the 3rd IFIP International Conference on Theoretical Computer Science (TCS 2004),
Toulouse, France, August 23 - 26, 2004, 293-306

Klaus Jansen
Approximation algorithms for mixed fractional packing and covering problems
Proceedings of the 2nd Workshop on Approximation and Online Algorith (WAOA 2004),
Bergen, Norway, September 14 - 17, 2004, Springer LNCS 3351, 6-8