[ IBM Research ]
line
Inventory Management Problems
  1. "Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms", with N. Buchbinder, T. Kimbrel, R. Levi  and K. Makarychev, in Proceedings of SODA 2008.
  2. "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, Transactions on Algorithms 4(3) (2008).
  3. "Approximation Algorithms for the Multi-Item Capacitated Lot-Sizing Problem via Flow-Cover Inequalities", with R. Levi and A. Lodi, Mathematics of Operations Research v. 33 (2008), pp. 461--474, preliminary version appeared in Proceedings of IPCO2007, 454-468.
  4. "A Constant Factor Approximation Algorithm for the One-Warehouse Multi-Retailer Problem",  with R. Levi, R. Roundy and D. Shmoys, Management Science v. 54 (2008), pp. 763-776, preliminary versions appeared in APPROX 2006 and SODA 2005.
line
On-line Algorithms
  1. "Dynamic Pricing for Impatient Bidders", with  N. Bansal, N. Chen, N. Cherniavsky, A. Rudra and B. Schieber, ACM Transactions on Algorithms 6(2): (2010), in  Proceedings of SODA2007.
  2. "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.
  3. "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.
  4. "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

Matroids and Submodular Functions
  1.  "Concentration Inequalities for Nonlinear Matroid Intersection and Their Applications", with K. Makarychev and W. Schudy, submitted for publication.
  2. "Matroid Matching: The Power of Local Search", with Jon Lee and Jan Vondrak, submitted for publication, preliminary version appeared in  Proceedings of Symposium on Theory of Computing (STOC2010), 369-378.
  3. "Submodular Maximization Over Multiple Matroids via Generalized Exchange Properties", with Jon Lee and Jan Vondrak, to appear in Mathematics of Operations Research, to appear in Proceedings of APPROX2009.
  4. "Non-monotone submodular maximization under matroid and knapsack constraints", with Jon Lee, Vahab Mirrokni and Vishnawath Nagarajan, SIAM Journal on Discrete Mathematics 23(4): 2053-2078 (2010), preliminary version appeared in Proceedings of STOCS 2009, pp. 323--332.
  5.  "A Note on Maximizing a Submodular Set Function Subject to Knapsack Constraint" , Operations Research Letters v.32 (2004), pp. 41-43.
line
Bin Packing Problems
  1. "A Structural Lemma in 2-dimensional Packing and Its Implications on Approximability", with N. Bansal, A. Caprara, K. Jansen, L. Pradel, to appear in Proceedings of ISAAC 2009.
  2. "Harmonic Algorithm for 3-Dimensional Strip Packing Problem", with N. Bansal, Xin Han, Kazuo Iwama and Guochuan Zhang, in  Proceedings of SODA2007.
  3. "A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing", with N. Bansal and A. Caprara, SIAM Journal on Computing 39(4): 1256-1278 (2009), preliminary version appeared with the title "Improved Approximation Algorithms for Multidimensional Packing Problems",  in Proceedings of FOCS 2006, pp. 697-708.
  4. "Two-dimensional bin packing with one dimensional resource augmentation", with N. Bansal, Discrete Optimization v. 4 (2007), pp. 143-153.
  5.  "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.
  6. "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. "New Lower Bound for the Flow Shop Scheduling  Problem", with P. Baptiste and A. Kononov, submitted for publication.
  2. "Complete complexity classification of short shop scheduling problems", with A. Kononov and S. Sevastianov, submitted for pulication, preliminary version appeared in Proceedings of CSR 2009, Lecture Notes in Computer Science 5675, pp. 227-236.
  3. "Integrality Property in Preemptive Parallel Machine Scheduling", with P. Baptiste, J. Carlier, A. Kononov, M. Queyranne and S. Sevastianov, submitted for publication, preliminary version appeared in Proceedings of CSR 2009, Lecture Notes in Computer Science 5675, pp. 38-46.
  4. "Tight Bounds for the Permutation Flow Shop", with Viswanath Nagarajan, Mathematics of Operation Research 34(2) (2009), pp. 417-227, preliminary version appeared in the Proceedings of (IPCO2008), pp. 154-168.
  5. "High-Multiplicity Cyclic Job Shop Scheduling", with T. Kimbrel, Operations Research Letters 36(5) (2008), pp. 574-578.
  6. "Improved approximation algorithms for Broadcast Scheduling", with N. Bansal and D. Coppersmith, SIAM J. Comput. 38(3): 1157-1174 (2008), preliminary version appeared in SODA 2006.
  7. "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.
  8. "The Santa Claus Problem", with N. Bansal, in Proceedings of STOC2006, pp. 31--40.
  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. "Inapproximability of the multilevel uncapacitated facility location problem", with Ravishankar Krishnaswamy, submitted for publication.
  2. "On the maximum quadratic assignment problem",  with Vishnawath Nagarajan,  Mathematics of Operations Research 34(4) (2009), pp. 859-868, preliminary version appeared in Proceedings of SODA 2009, pp. 516-524.
  3. "Min Sum Edge Coloring in Multigraphs Via Configuration LP", with Magnus Halldorsson and Guy Kortsarz, to appear in Transactions on Algorithms, preliminary version appeared in Proceedings of IPCO2008, pp. 359-373.
  4. "Approximating the minimum quadratic assignment problems", with R. Hassin and A. Levin, Transactions on Algorithms 6(1): (2009)
  5. "On the maximum quadratic assignment problem",  with Vishnawath Nagarajan,  Mathematics of Operations Research 34(4) (2009), pp. 859-868, preliminary version appeared in Proceedings of SODA 2009, pp. 516-524.
  6. "Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems", with M. Blaser, Operations Research Letters v.37(3)  (2009), pp. 176-180, preliminary version appeared in Procedings of WADS2005, Lecture Notes in Computer Science 3608, pp. 350--359.
  7. "Tight Approximation Algorithms for Maximum General Assignment Problems.", with L. Fleischer, M. Goemans and V. Mirrokni, submitted for publication, preliminary version appeared in SODA 2006.
  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. "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.
  14. "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.
  15. "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.
  16. "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.
  17. "Approximating the Maximum Quadratic Assignment Problem", with E. Arkin and R. Hassin, Information Processing Letters  v.77 (2001), pp. 13-16 . 
  18. "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. 
  19. "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. 
  20. "An 0.828-Approximation algorithm for uncapacitated facility location problem", with A.Ageev, Discrete Applied Mathematics v.93 (1999), pp. 289-296. 
  21. "Approximation algorithm for weighted p-center problem", Discrete Analysis and Operations Research, 1998, series 1, 5(1), pp. 60-63. (in Russian)
  22. "Approximation algorithm for dynamic p-facility location problem", Discrete Analysis and Operations Research, 1997, series 2, 4(2), pp. 55-62. (in Russian)
  23. "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, in Proceedings of 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
  Other Papers
  1. "On the rate of convergence to the neutral attractor of a family of one-dimensional maps", with T. Nowicki, G. Swirszcz and S. Winograd, Fundamenta Mathematicae v. 206 (2009), pp.253--269.
  2. "On Hardness of Pricing Items for Single-Minded Bidders", with Rohit Khandekar, Tracy Kimbrel and Konstantin Makarychev, in Proceedings of APPROX-RANDOM 2009, pp. 202-216.
  3. "Optimal bundle pricing with monotonicity constraint", with Alexander Grigoriev, Joyce van Loon, Marc Uetz, Tjark Vredeveld, Operations Research Letters v. 36 (2008), pp. 609--614, preliminary version appeared in Proceedings of ESA 2007.
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