# 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