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

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:

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

  2. "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.

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

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

  5. "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