Sobolev Institute of Mathematics
Laboratory "Mathematical Methods of Decision Making"

Sviridenko Maxim Junior researcher Address: Akademika Koptyuga pr.4, Sobolev Institute of Mathematics, Novosibirsk, 630090, Russia E-mail: svir@math.nsc.ru Phone: +73 8323 32086 Fax: +73 8323 32598

Curriculum Vitae

Education:

• Ph.D. in Mathematics and Physics, "Approximation algorithms for discrete facility location problems" ,
  Sobolev Institute of Mathematics, January, 1999.
  Advisor: Prof. Vladimir L.Beresnev.

• M.D. in Applied Mathematics and Computer Science,
  Novosibirsk State University, May, 1998.

Affiliation:

• 1994-date, Sobolev Institute of Mathematics

Research Interests

Approximation algorithms for hard combinatorial problems;
Computational complexity (especially, hardness of approximation);
Discrete facility location problems;
Scheduling problems.

Publications

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

2. "Approximation algorithms for Maximum Coverage and Max Cut with cardinality constraint,
   with A.Ageev, to appear in IPCO99.

3. "Makespan minimization in job shops: a polynomial time approximation scheme",
   with K.Jansen and R.Solis-Oba, to appear in STOC99.

4. "An 0.828-Approximation algorithm for uncapacitated facility location problem" ,
   with A.Ageev, to appear in Discrete Applied Mathematics.

5. "Best possible approximation algorithm for MAX SAT with cardinality constraint",
   to appear in Algorithmica,Preliminary version appeared in Proceedings of APPROX98, pp. 193-199.

Papers in Russian

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

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

3. M.I.Sviridenko,"Approximation algorithm for weighted p-center problem", Discrete Analysis and Operations Research, 1998, series 1, 5(1), pp. 60-63.

E-mail: svir@math.nsc.ru

Update 14.01.99