[ IBM Research ]
 
[ Find ][ News ][ Products ][ Support ][ Business solutions ][ Inside IBM ][ Interest groups ]
line
On-line Algorithms
  1. "Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms", with N. Buchbinder, T. Kimbrel, R. Levi  and K. Makarychev, to appear in SODA 2008.
  2. "Dynamic Pricing for Impatient Bidders: Possibilities and Impossibilities", with  N. Bansal, N. Chen, N. Cherniavsky, A. Rudra and B. Schieber, in  Proceedings of SODA2007.
  3. "Further Improvements in Competitive Guarantees for QoS Buffering", with N. Bansal, L. Fleischer, T. Kimbrel, M. Mahdian and B. Schieber,  in  Proceedings of ICALP 2004, pp. 196--207.
  4. "Buffer Overflow Management in QoS Switches", with A. Kesselman, Z. Lotker, Y. Mansour, B. Patt-Shamir, B. Schieber, SIAM Journal on Computing v.33 (2004), pp. 563--583, preliminary version appeared in  Proceedings of Symposium on Theory of Computing (STOC 01), pp. 520--529.
  5. "Online Server Allocation in a Server Farm via Benefit Task System", with T. S. Jayram, T. Kimbrel, R. Krauthgamer, B. Schieber, in  Proceedings of Symposium on Theory of Computing (STOC 01), pp. 540--549.
line
Bin Packing Problems
  1. "Harmonic Algorithm for 3-Dimensional Strip Packing Problem", with N. Bansal, Xin Han, Kazuo Iwama and Guochuan Zhang, in  Proceedings of SODA2007.
  2. "Improved Approximation Algorithms for Multidimensional Packing Problems", with N. Bansal and A. Caprara, in Proceedings of FOCS 2006.
  3. "Two-dimensional bin packing with one dimensional resource augmentation", with N. Bansal, Discrete Optimization v. 4 (2007), pp. 143-153.
  4.  "A Tale of Two Dimensional Bin Packing", with N. Bansal and A. Lodi, in Procedings of Symposium on Foundations of Computer Science (FOCS 2005), pp. 657--666.
  5. "Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes", with N. Bansal, J. Correa, C. Kenyon, Mathematics of Operations Research v.31 (2006), pp. 31--49, this paper is a union of two papers "Approximation Schemes for Multidimensional Packing" and "New approximability and inapproximability results for 2-dimensional bin packing", in Proceedings of SODA 2004, pp.179--188 and pp.189--196.
line
Scheduling Problems
  1. "Tight Bounds for the Permutation Flow Shop", with Viswanath Nagarajan, submitted for publication.
  2. "Complete complexity classification of shop scheduling problems", with A. Kononov and S. Sevastianov, submitted for pulication.
  3. "High-Multiplicity Cyclic Job Shop Scheduling", with T. Kimbrel, submitted for publication.
  4. "New Lower Bound for the Flow Shop Scheduling  Problem", with P. Baptiste and A. Kononov, submitted for publication.
  5. "The Santa Claus Problem", with N. Bansal,submitted for publication, preliminary version appeared in Proceedings of STOC2006, pp. 31--40.
  6. "Structural Properties of Preemptive Schedules", with P. Baptiste, J. Carlier, A. Kononov, M. Queyranne and S. Sevastianov, submitted for publication.
  7. "Improved approximation algorithms for Broadcast Scheduling", with N. Bansal and D. Coppersmith, submitted for publication, preliminary version appeared in SODA 2006.
  8. "Unrelated parallel machine scheduling with resource-dependent processing times", with A. Grigoriev and M. Uetz, Mathematical Programming v.110 (2007), pp. 209-228, preliminary version appeared in Proceedings of APPROX 2006 and  IPCO 2005, pp. 182-195.
  9. "Job shop with unit processing times", with N. Bansal and T. Kimbrel, Mathematics of Operations Research v.31 (2006), pp. 381--389, preliminary version appeared in Proceedings of SODA 2005, pp. 207--214.
  10. "Minimizing migrations in fair multiprocessor scheduling of persistent tasks", with T. Kimbrel and B. Schieber, Journal of Scheduling v.9 (2006), pp. 365--379, preliminary version appeared  in Proceedings of SODA 2004, pp. 975--984.
  11. "Minimizing makespan in no-wait job shops", with N. Bansal and M. Mahdian, Mathematics of Operations Research v.30 (2005), pp. 817--831.
  12. "A Note on Permutation Flow Shop Problem", Annals of Operations Research v. 129 (2004), pp. 247-252.
  13. "Makespan Minimization in No-Wait Flow Shops: a Polynomial Time Approximation Scheme", SIAM Journal of Discrete Mathematics v.16 (2003), pp. 313-322, joint preliminary version appeared with the title "Approximability and Non-Approximability Results for No-Wait Shop Scheduling Problems", with G. Woeginger,  in Procedings of Symposium on Foundations of Computer Science (FOCS00), pp. 116-125. 
  14. "Makespan Minimization in Job Shops: a Linear Time Approximation Scheme", with K.Jansen and R.Solis-Oba, SIAM Journal of Discrete Mathematics v.16 (2003), pp. 288-300, preliminary versions appeared as  "Makespan Minimization in Job Shops: a Polynomial Time Approximation Scheme", in  Proceedings of Symposium on Theory of Computing (STOC99), pp.394-399  and "A Linear Time Approximation Scheme for Job Shop Scheduling Problems", in Proceedings of APPROX99, Lecture Notes in Computer Science v.1671, pp.177-188. 
  15. "A (2+epsilon)-Approximation Algorithm for Generalized Preemptive Open Shop Problem with Minsum Objective" , with M. Queyranne, Journal of Algorithms, v. 45 (2002), pp. 202-212, preliminary version appeared in Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO 2001), Lecture Notes in Computer Science v.2081, pp.361--369. 
  16. "Approximation Algorithms for Shop Scheduling Problems with Minsum Objective", with M. Queyranne, Journal of Scheduling v.5 (2002), pp. 287--305, extended abstract appeared with the title "New and Improved Algorithms for Minsum Shop Scheduling"  in Proceedimgs of Symposium on Discrete Algorithms (SODA00), pp.871-878. 
  17. "Linear Time Combinatorial Approximation Scheme for Open Shop Problem with Release Dates",with A. Kononov,  Operations Research Letters,  v. 30 (2002), pp. 276--280.
  18. "Approximation Schemes for Multiprocessor Flow and Open Shop Problems", with K. Jansen, Proceedings of Symposium on Theoretical Aspects of Computer Science (STACS00), Lecture Notes in Computer Science v.1770, pp. 455-466. 
  19. "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, in Procedings of Symposium on Foundations of Computer Science (FOCS99), pp.32-43.
line
Optimization Problems on Graphs, Facility Location and Related Problems

  1. "Approximating the minimum quadratic assignment problems", with R. Hassin and A. Levin, submitted for publication.
  2. "Bundle Pricing with Comparable Items", with Alexander Grigoriev, Joyce van Loon, Marc Uetz, Tjark Vredeveld, in Proceedings of ESA 2007, 475-486.
  3. "Algorithms for Capacitated Rectangle Stabbing and Lot Sizing with Joint Set-Up Cost", with Guy Even, Retsef Levi, Dror Rawitz, Baruch Schieber, Shimon (Moni) Shahar,  to appear in Transactions on Algorithms.
  4. "Approximation Algorithms for the Multi-Item Capacitated Lot-Sizing Problem via Flow-Cover Inequalities", with R. Levi and A. Lodi, to appear in Mathematics of Operations Research, preliminary version appeared in Proceedings of IPCO2007, 454-468.
  5. "A Constant Factor Approximation Algorithm for the One-Warehouse Multi-Retailer Problem",  with R. Levi, R. Roundy and D. Shmoys, to appear in Management Science, preliminary versions appeared in APPROX 2006 and SODA 2005.
  6. "Tight Approximation Algorithms for Maximum General Assignment Problems.", with L. Fleischer, M. Goemans and V. Mirrokni, SODA 2006.
  7. "Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems", with M. Blaser, submitted for publication, preliminary version appeared in Procedings of WADS2005, Lecture Notes in Computer Science 3608, pp. 350--359.
  8. "Hamiltonian Completion in Sparse Random Graphs", with D. Gamarnik, Discrete Applied Mathematics v.152 (2005), pp. 139-158.
  9. "Approximation algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs", with H. Kaplan, M. Lewenstein and N. Shafrir, Journal of ACM v.52 (2005), pp. 602-626, preliminary version appeared in Procedings of Symposium on Foundations of Computer Science (FOCS 2003), pp.56-65.
  10. "An Improved Upper Bound for TSP in Cubic 3-Connected Graphs", with D. Gamarnik and M. Lewenstein, Operations Research Letters v.33 (2005), pp. 467-474.
  11. "Pipage Rounding: a New Method of Constructing Algorithms with Proven Performance Guarantee", with A.Ageev, Journal of Combinatorial Optimization v.8 (2004), preliminary versions appeared as "Approximation algorithms for Maximum Coverage and Max Cut with given sizes of parts", In  Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO99), Lecture Notes in Computer Science v.1610, pp.17-30. and "An approximation algorithm for Hypergraph Max Cut with given sizes of parts", in Proceedings of European Symposium on Algorithms (ESA00).
  12. "Approximations for Maximum Transportation Problem with Permutable Supply Vector and Others Capacitated Star Packing Problems", with E. Arkin, R. Hassin and S. Rubinstein, Algorithmica v.39 (2004), pp.175--187,  preliminary version appeared in  Proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT02), Lecture Notes in Computer Science v. 2368, pp.280--287.
  13. "A Note on Maximizing a Submodular Set Function Subject to Knapsack Constraint" , Operations Research Letters v.32 (2004), pp. 41-43.
  14. "Approximating Assymetric Maximum TSP",  with M. Lewenstein, SIAM Journal of Discrete Mathematics v.17 (2003), pp. 237-248, preliminary version appeared in Proceedings of SODA03, pp. 646-654.
  15. "An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem", in  Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO02), Lecture Notes in Computer Science v. 2337, pp.230--239.
  16. "The diameter of a long range percolation graph", with D. Coppersmith  and D. Gamarnik, Random Structures and Algorithms v.21 (2002), pp. 1-13, preliminary version appeared in Proceedimgs of Symposium on Discrete Algorithms (SODA02), pp. 329-337.
  17. "An 0.5-Approximation Algorithm for the MAX DICUT with given sizes of parts", with  A.Ageev  and R. Hassin,  SIAM Journal of Discrete Mathematics v.14 (2001), pp. 246--255, preliminary version appeared in Proceedings of APPROX00, Lecture Notes in Computer Science v.1913, pp.34-41.
  18. "Approximating the Maximum Quadratic Assignment Problem", with E. Arkin and R. Hassin, Information Processing Letters  v.77 (2001), pp. 13-16 . 
  19. "Best possible approximation algorithm for MAX SAT with cardinality constraint", Algorithmica v.30 (2001), pp. 398--405., preliminary version appeared in Proceedings of APPROX98, Lecture Notes in Computer Science v.1444, pp. 193-199. 
  20. "Worst-case analysis of the greedy algorithm for a generalization of the maximum p-facility location problem" ,  Operations Research Letters v.26 (2000), pp. 193-197. 
  21. "An 0.828-Approximation algorithm for uncapacitated facility location problem", with A.Ageev, Discrete Applied Mathematics v.93 (1999), pp. 289-296. 
  22. "Approximation algorithm for weighted p-center problem", Discrete Analysis and Operations Research, 1998, series 1, 5(1), pp. 60-63. (in Russian)
  23. "Approximation algorithm for dynamic p-facility location problem", Discrete Analysis and Operations Research, 1997, series 2, 4(2), pp. 55-62. (in Russian)
  24. "Approximation algorithms for maximization facility location problems", Discrete Analysis and Operations Research, 1997, series 1, 4(3), pp. 35-48. (in Russian)
line

Papers Motivated by Real-Life Optimization Projects
  1. "Test Machine Scheduling and Optimization for z/OS", with M. Kaplan, T. Kimbrel, K. Mckenzie, R. Prewitt, Clay Williams and C.Yilmaz, to appear in CISched 2007.
  2. "Inventory Allocation and Transportation Scheduling for Logistics of Network-Centric Military Operations", with F. Barahona, P. Chowdhary, M. Ettl,  Pu Huang, T. Kimbrel, L. Ladanyi, Y. Lee, B. Schieber, K. Sourirajan and G. Swirszcz,  IBM Journal of Research and Development v51., (2007), pp. 391-408.
  3. "Dynamic Application Placement  for Clustered Web Applications", with A. Karve, T. Kimbrel, G. Pacifici, M. Spreitzer, M. Steinder and A. Tantawi,  in Proceedings of WWW2006, pp. 595-604.
  4. "Dynamic application placement under service and memory constraints", with T. Kimbrel, M. Steinder and A. Tantawi,  in Proceedings of WEA 2005, pp. 391-402.
line
 This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected  to adhere to the terms and constraints invoked by each author's copyright.  In most cases, these works may not be reposted without the explicit permission  of the copyright holder.
line
Maxim Sviridenko homepage