Maxim Sviridenko

Scheduling Theory

1. "Approximation Algorithms for Shop Scheduling Problems with Minsum Criteria", with M. Queyranne, submitted for publication, extended abstract accepted to SODA00 with title "New and Improved Algorithms for Minsum Shop Scheduling".

2. "Linear Time Combinatorial Approximation Scheme for Open Shop Problem with Release Dates",with A. Kononov, submitted for publication.

3. "Approximation Schemes for Multiprocessor Flow and Open Shop Problems", with K. Jansen, submitted for publication.

4. "Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates", with F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella and C. Stein, to appear in Procedings of FOCS99.

5. "Makespan Minimization in Job Shops: a Linear Time Approximation Scheme",
   with K.Jansen and R.Solis-Oba, submitted for publication,
   preliminary versions appeared as

• "Makespan Minimization in Job Shops: a Polynomial Time Approximation Scheme", in  Proceedings of STOC99, pp.394-399.

• "A Linear Time Approximation Scheme for Job Shop Scheduling Problems", to appear in APPROX99.

Facility Location and Related Problems

1. "Worst-case analysis of greedy algorithm for generalization of maximum p-facility location problem", submitted for publication.

2. "Approximation algorithms for some combinatorial problems with cardinality-type constraints", with A.Ageev, journal version in preparation,
   preliminary versions are:

• "Approximation algorithms for some combinatorial problems with cardinality-type constraints", In Proceedings of XI Baikal workshop "Optimization Methods and Its Applications" v.1 (1997), pp.1-4.

• "Approximation algorithms for Maximum Coverage and Max Cut with given sizes of parts", In  Proceedings of IPCO99, Lecture Notes in Computer Science v.1610, pp.17-30.

3. "An 0.828-Approximation algorithm for uncapacitated facility location problem" ,
   with A.Ageev, Discrete Applied Mathematics v.93 (1999). pp. 289-296.

4. "Best possible approximation algorithm for MAX SAT with cardinality constraint",
   to appear in Algorithmica, Preliminary version appeared in Proceedings of APPROX98, Lecture Notes in Computer Science v.1444, pp. 193-199.

5. "Approximation algorithms for maximization facility location problems", Discrete Analysis and Operations Research, 1997, series 1, 4(3), pp. 35-48. (in Russian)

6. "Approximation algorithm for dynamic p-facility location problem", Discrete Analysis and Operations Research, 1997, series 2, 4(2), pp. 55-62. (in Russian)

7. "Approximation algorithm for weighted p-center problem", Discrete Analysis and Operations Research, 1998, series 1, 5(1), pp. 60-63. (in Russian)

Maxim Sviridenko homepage

Update 27.09.99