Maxim Sviridenko
List Of Publications
Journal Papers
 "Bernsteinlike Concentration and Moment Inequalities for Polynomials of Independent Random Variables: Multilinear Case", with W. Schudy, submitted for publication.
 "Online MaketoOrder Joint Replenishment Model: Primal Dual Competitive Algorithms", with N. Buchbinder, T. Kimbrel, R. Levi, K. Makarychev, Operations Research, 61 (2013), pp. 10141029.
 "Preemptive and NonPreemptive Generalized Min Sum Set Cover", with S. Im and R. van der Zwaan, to appear in Mathematical Programming.
 "Supermodularity and Affine Policies in Dynamic Robust Optimization", with D. Iancu and M. Sharma, Operations Research, 61 (2013), pp. 941956.
 "Concentration Inequalities for Nonlinear Matroid Intersection", with K. Makarychev and W. Schudy, to appear in Random Structures and Algorithms.
 "Harmonic Algorithm for 3Dimensional Strip Packing Problem", with N. Bansal, Xin Han, Kazuo Iwama and Guochuan Zhang, SIAM Journal on Computing, 42(2) (2013), pp. 579592.
 "Matroid Matching: The Power of Local Search", with J. Lee and J. Vondrak, SIAM Journal of Computing v.42(1) (2013), pp. 357379.
 "Alberto Caprara (19682012): Scientific Contributions", with N. Bansal, M. Fischetti, G. Lancia, A. Letchford, A. Lodi, M. Monaci, U. Pferschy, D. Pisinger, J. SalazarGonzalez and P. Toth, Optima, issue 91, (2013), pp. 111.
 "Integer preemptive scheduling on parallel machines", with P. Baptiste, J. Carlier, A. Kononov, M. Queyranne and S. Sevastyanov, Operations Research Letters 40 (2012), pp. 440444.
 "A Complete 4parametric complexity classification of short shop scheduling problems", with A. Kononov and S. Sevastyanov, Journal of Scheduling 15(4): 427446 (2012).
 "A note on the KenyonRemila strippacking algorithm", Information Processing Letters, 112(12) (2012), pp. 1012.
 "Discretization orders for distance geometry problems", with Carlile Lavor, Jon Lee, Audrey LeeSt. John, Leo Liberti and Antonio Mucherino, Optimization Letters 6(4): 783796 (2012).
 "Tight Approximation Algorithms for Maximum Separable Assignment Problems", with L. Fleischer, M. Goemans and V. Mirrokni, Mathematics of Operations Research 36 (2011), pp. 416431.
 "Min Sum Edge Coloring in Multigraphs Via Configuration LP", with Magnús M. Halldórsson and Guy Kortsarz, ACM Transactions on Algorithms 7(2), 22 (2011).
 "Properties of optimal schedules in preemptive shop scheduling", with Philippe Baptiste, Jacques Carlier, Alexander Kononov, Maurice Queyranne, Sergey Sevastyanov, Discrete Applied Mathematics 159(5): 272280 (2011).
 "Submodular Maximization Over Multiple Matroids via Generalized Exchange Properties", with Jon Lee and Jan Vondrak, Mathematics of Operations Research 35(4): 795806 (2010).
 "Nonmonotone submodular maximization under matroid and knapsack constraints", with Jon Lee, Vahab Mirrokni and Vishnawath Nagarajan, SIAM Journal on Discrete Math. 23(4): 20532078 (2010).
 "Dynamic Pricing for Impatient Bidders", with N. Bansal, N. Chen, N. Cherniavsky, A. Rudra and B. Schieber, ACM Transactions on Algorithms 6(2), (2010).
 "The Maximum Quadratic Assignment Problem", with V. Nagarajan, Mathematics of Operations Research v.34, (2009), pp. 859868.
 "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): 12561278 (2009).
 "Tight Bounds for the Permutation Flow Shop", with Viswanath Nagarajan, Mathematics of Operations Research v. 34 (2009), pp. 417427.
 "Approximating the minimum quadratic assignment problems", with R. Hassin and A. Levin, ACM Transactions on Algorithms 6(1): (2009).
 "Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3Cycle Cover Problems", with M. Blaser and L. Shankar Ram, Operations Research Letters v.37(3) (2009), pp. 176180.
 "On the rate of convergence to the neutral attractor of a family of onedimensional maps", with T. Nowicki, G. Swirszcz and S. Winograd, Fundamenta Mathematicae v. 206 (2009), pp.253269.
 "Structural properties of optimal schedules with operation interruptions", with P. Baptiste, J. Carlier, A. Kononov, M. Queyranne and S. Sevastianov, Discrete Analysis and Operations Research (Diskretn. Anal. Issled. Oper.) 16 (2009), no. 1, 336, 96. (in Russian)
 "Improved approximation algorithms for Broadcast Scheduling", with N. Bansal and D. Coppersmith, SIAM Journal on Computing 38(3): 11571174 (2008).
 "Approximation Algorithms for the MultiItem Capacitated LotSizing Problem via FlowCover Inequalities", with R. Levi and A. Lodi, Mathematics of Operations Research v.33 (2008), pp. 461  474.
 "HighMultiplicity Cyclic Job Shop Scheduling", with T. Kimbrel, Operations Research Letters 36 (2008), pp. 574578.
 "Algorithms for Capacitated Rectangle Stabbing and Lot Sizing with Joint SetUp Cost", with Guy Even, Retsef Levi, Dror Rawitz, Baruch Schieber, Shimon (Moni) Shahar, ACM Transactions on Algorithms 4(3): (2008).
 "A Constant Factor Approximation Algorithm for the OneWarehouse MultiRetailer Problem", with R. Levi, R. Roundy and D. Shmoys, Management Science v.54 (2008), pp. 763776.
 "Optimal bundle pricing with monotonicity constraint", with Alexander Grigoriev, Joyce van Loon, Marc Uetz, Tjark Vredeveld, Operations Research Letters v.36 (2008), pp. 609614.
 "Machine scheduling with resource dependent processing times", with A. Grigoriev and M. Uetz, Mathematical Programming v.110 (2007), pp. 209228.
 "Inventory Allocation and Transportation Scheduling for Logistics of NetworkCentric 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. 391408.
 "Twodimensional bin packing with one dimensional resource augmentation", with N. Bansal, Discrete Optimization v.4 (2007), 143153.
 "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. 3149.
 "Job shop with unit processing times", with N. Bansal and T. Kimbrel, Mathematics of Operations Research v.31 (2006), pp. 381389.
 "Minimizing migrations in fair multiprocessor scheduling of persistent tasks", with T. Kimbrel and B. Schieber, Journal of Scheduling v.9 (2006), pp. 365379.
 "Minimizing makespan in nowait job shops", with N. Bansal and M. Mahdian, Mathematics of Operations Research v.30 (2005), pp. 817831.
 "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. 602626.
 "Hamiltonian Completion in Sparse Random Graphs", with D. Gamarnik, Discrete Applied Mathematics v.152 (2005), pp. 139158.
 "An Improved Upper Bound for TSP in Cubic 3Connected Graphs", with D. Gamarnik and M. Lewenstein, Operations Research Letters v.33 (2005), pp. 467474.
 "Buffer Overflow Management in QoS Switches", with A. Kesselman, Z. Lotker, Y. Mansour, B. PattShamir, B. Schieber, SIAM Journal on Computing v.33 (2004), pp. 563583.
 "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.175187.
 "A Note on Maximizing a Submodular Set Function Subject to Knapsack Constraint" , Operations Research Letters v.32 (2004), pp. 4143.
 "A Note on Permutation Flow Shop Problem", Annals of Operations Research v. 129 (2004), pp. 247252.
 "Pipage Rounding: a New Method of Constructing Algorithms with Proven Performance Guarantee", with A.Ageev, Journal of Combinatorial Optimization 8(3): 307328 (2004).
 "Makespan Minimization in NoWait Flow Shops: a Polynomial Time Approximation Scheme", SIAM Journal of Discrete Mathematics v.16 (2003), pp. 313322.
 "Makespan Minimization in Job Shops: a Linear Time Approximation Scheme", with K.Jansen and R.SolisOba, SIAM Journal of Discrete Mathematics v.16 (2003), pp. 288300.
 "Approximating Assymetric Maximum TSP", with M. Lewenstein, SIAM Journal of Discrete Mathematics v.17 (2003), pp. 237248.
 "A (2+epsilon)Approximation Algorithm for Generalized Preemptive Open Shop Problem with Minsum Objective" , with M. Queyranne, Journal of Algorithms, v. 45 (2002), pp. 202212.
 "Approximation Algorithms for Shop Scheduling Problems with Minsum Objective", with M. Queyranne, Journal of Scheduling v.5 (2002), pp. 287305.
 "The diameter of a long range percolation graph", with D. Coppersmith and D. Gamarnik, Random Structures and Algorithms v.21 (2002), pp. 113.
 "Linear Time Combinatorial Approximation Scheme for Open Shop Problem with Release Dates",with A. Kononov, Operations Research Letters, v. 30 (2002), pp. 276280.
 "An 0.5Approximation 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. 246255.
 "Approximating the Maximum Quadratic Assignment Problem", with E. Arkin and R. Hassin, Information Processing Letters v.77 (2001), pp. 1316 .
 "Best possible approximation algorithm for MAX SAT with cardinality constraint", Algorithmica v.30 (2001), pp. 398405.
 "Worstcase analysis of the greedy algorithm for a generalization of the maximum pfacility location problem" , Operations Research Letters v.26 (2000), pp. 193197.
 "An 0.828Approximation algorithm for uncapacitated facility location problem", with A.Ageev, Discrete Applied Mathematics v.93 (1999), pp. 289296.
 "Approximation algorithm for weighted pcenter problem", Discrete Analysis and Operations Research, 1998, series 1, 5(1), pp. 6063. (in Russian)
 "Approximation algorithm for dynamic pfacility location problem", Discrete Analysis and Operations Research, 1997, series 2, 4(2), pp. 5562. (in Russian)
 "Approximation algorithms for maximization facility location problems", Discrete Analysis and Operations Research, 1997, series 1, 4(3), pp. 3548. (in Russian)
Refereed Conference Proceedings
 "NoWait Flowshop Scheduling is as Hard as Asymmetric Traveling Salesman Problem", with Marcin Mucha, to appear in ICALP2013.
 "Large Neighborhood Local Search for the Maximum Set Packing Problem", with Justin Ward, to appear in ICALP2013.
 "Approximation Algorithms for the Joint Replenishment Problem with Deadlines", with Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil Dobbs, Tomasz Nowicki, Grzegorz Świrszcz and Neal E. Young, to appear in ICALP2013.
 "An Efficient PolynomialTime Approximation Scheme for the Joint Replenishment Problem", with Tim Nonner, in Proceedings of IPCO 2013, pp. 314323.
 "Approximating the ConfigurationLP for Minimizing Weighted Sum of Completion Times on Unrelated Machines", with Andreas Wiese, in Proceedings of IPCO 2013, pp. 387398.
 "New and Improved Bounds for the Minimum Set Cover Problem", with R. Saket, in Proceedings of APPROXRANDOM 2012, pp. 288300.
 "Preemptive and NonPreemptive Generalized Min Sum Set Cover", with S. Im and R. van der Zwaan, in Proceedings of STACS2012, pp. 465476.
 "Concentration and Moment Inequalities for Polynomials of Independent Random Variables", with W. Schudy, in Proceedings of SODA 2012, pp. 437446.
 "Concentration Inequalities for Nonlinear Matroid Intersection", with K. Makarychev and W. Schudy, in Proceedings of SODA 2012, pp. 420436.
 "Inapproximability Results for the Multilevel Uncapacitated Facility Location Problem", with Ravishankar Krishnaswamy, in Proceedings of SODA 2012, pp. 718734.
 "Maximizing a Polynomial Subject to Assignment Constraints", with K. Makarychev, in Proceedings ICALP 2011, pp. 510520.
 "Matroid Matching: The Power of Local Search", with Jon Lee and Jan Vondrak, in Proceedings of Symposium on Theory of Computing (STOC 2010), pp. 369378.
 "Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LPBased Approximation Algorithm", with Konstantin Makarychev and Rajsekar Manokaran, In Proceedings of ICALP2010, pp. 594604.
 "Submodular Maximization Over Multiple Matroids via Generalized Exchange Properties", with Jon Lee and Jan Vondrak, in Proceedings of APPROX2009, pp. 244257.
 "Nonmonotone submodular maximization under matroid and knapsack constraints", with Jon Lee, Vahab Mirrokni and Vishnawath Nagarajan, in Proceedings of STOCS 2009, pp. 323332.
 "The Maximum Quadratic Assignment Problem", with V. Nagarajan, in Proceedings of SODA 2009, pp. 516524.
 "On Hardness of Pricing Items for SingleMinded Bidders", with Rohit Khandekar, Tracy Kimbrel and Konstantin Makarychev, in Proceedings of APPROXRANDOM 2009, pp. 202216.
 "A Structural Lemma in 2dimensional Packing and Its Implications on Approximability", with N. Bansal, A. Caprara, K. Jansen, L. Pradel, in proceedings of ISAAC 2009.
 "Complete complexity classification of short shop scheduling problems", with A. Kononov and S. Sevastianov,in Proceedings of CSR 2009, Lecture Notes in Computer Science 5675, pp. 227236.
 "Structural Properties of Preemptive Schedules", with P. Baptiste, J. Carlier, A. Kononov, M. Queyranne and S. Sevastianov, in Proceedings of CSR 2009, Lecture Notes in Computer Science 5675, pp. 3846.
 "Min Sum Edge Coloring in Multigraphs Via Configuration LP", with Magnús M. Halldórsson and Guy Kortsarz, in Proceedings of IPCO 2008, pp. 359373.
 "Tight Bounds for the Permutation Flow Shop", with Viswanath Nagarajan, in Proceedings of IPCO 2008, pp. 154168.
 "Online MaketoOrder Joint Replenishment Model: Primal Dual Competitive Algorithms", with N. Buchbinder, T. Kimbrel, R. Levi, K. Makarychev, in Proceedings of SODA2008, pp. 952961.
 "Harmonic Algorithm for 3Dimensional Strip Packing Problem", with N. Bansal, Xin Han, Kazuo Iwama and Guochuan Zhang, in Proceedings of SODA2007, 11971206.
 "Dynamic Pricing for Impatient Bidders", with N. Bansal, N. Chen, N. Cherniavsky, A. Rudra and B. Schieber, in Proceedings of SODA2007, 726735.
 "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.
 "Approximation Algorithms for the MultiItem Capacitated LotSizing Problem via FlowCover Inequalities", with R. Levi and A. Lodi, in Proceedings of IPCO2007, 454468.
 "Bundle Pricing with Comparable Items", with Alexander Grigoriev, Joyce van Loon, Marc Uetz, Tjark Vredeveld, in Proceedings of ESA 2007, 475486.
 "Tight Approximation Algorithms for Maximum General Assignment Problems", with L. Fleischer, M. Goemans and V. Mirrokni, in Proceedings of SODA 2006, pp. 611620.
 "The Santa Claus Problem", with N. Bansal, in Proceedings of STOC2006, pp. 3140.
 "Improved Approximation Algorithm for the OneWarehouse MultiRetailer Problem", with R. Levi, In Proceedings of APPROXRANDOM 2006, pp. 188199.
 "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. 595604.
 "LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times" with Alexander Grigoriev and Marc Uetz, in Proceedings of APPROXRANDOM 2006, pp. 140151.
 "Improved approximation algorithms for Broadcast Scheduling", with N. Bansal and D. Coppersmith, in Proceedings of SODA 2006.
 "Improved Approximation Algorithms for Multidimensional Packing Problems", with N. Bansal and A. Caprara, in Proceedings FOCS 2006, 697708.
 "Dynamic application placement under service and memory constraints", with T. Kimbrel, M. Steinder and A. Tantawi, in Proceedings of Workshop on Experimental Algorithms (WEA 2005), pp. 391402.
 "Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3Cycle Cover Problems", with M. Blaser, in Proceedings of WADS2005, Lecture Notes in Computer Science 3608, pp. 350359.
 "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. 657666.
 "Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times" with Alexander Grigoriev and Marc Uetz, In Proceedings of IPCO 2005, pp. 182195.
 "Job shop with unit processing times", with N. Bansal and T. Kimbrel, in Proceedings of SODA 2005, pp. 207214.
 "Minimizing migrations in fair multiprocessor scheduling of persistent tasks", with T. Kimbrel and B. Schieber, in Proceedings of SODA 2004, pp. 975984.
 "New approximability and inapproximability results for 2dimensional bin packing", with N. Bansal, in Proceedings of SODA 2004, pp.179188 and pp.189196.
 "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. 196207.
 "Approximation algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs", with H. Kaplan, M. Lewenstein and N. Shafrir, in Procedings of Symposium on Foundations of Computer Science (FOCS 2003), pp.5665.
 "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.230239.
 "Approximating Assymetric Maximum TSP", with M. Lewenstein, in Proceedings of SODA03, pp. 646654.
 "Approximations for Maximum Transportation Problem with Permutable Supply Vector and Others Capacitated Star Packing Problems", with E. Arkin, R. Hassin and S. Rubinstein, in Proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT02), Lecture Notes in Computer Science v. 2368, pp.280287.
 "The diameter of a long range percolation graph", with D. Coppersmith and D. Gamarnik, in Proceedimgs of Symposium on Discrete Algorithms (SODA02), pp. 329337.
 "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. 540549.
 "Buffer Overflow Management in QoS Switches", with A. Kesselman, Z. Lotker, Y. Mansour, B. PattShamir, B. Schieber, in Proceedings of Symposium on Theory of Computing (STOC 01), pp. 520529.

"A (2+epsilon)Approximation Algorithm for Generalized Preemptive Open Shop Problem with Minsum Objective" , with M. Queyranne, in Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO 2001), Lecture Notes in Computer Science v.2081, pp.361369.

"Approximability and NonApproximability Results for NoWait Shop Scheduling Problems", with G. Woeginger, in Procedings of Symposium on Foundations of Computer Science (FOCS00), pp. 116125.

"New and Improved Algorithms for Minsum Shop Scheduling", with M. Queyranne, in Proceedimgs of Symposium on Discrete Algorithms (SODA00), pp.871878.

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

"An approximation algorithm for Hypergraph Max Cut with given sizes of parts", with A. Ageev, in Proceedings of European Symposium on Algorithms (ESA00), pp. 3241.

"An 0.5Approximation Algorithm for the MAX DICUT with given sizes of parts", with A.Ageev and R. Hassin, in Proceedings of APPROX00, Lecture Notes in Computer Science v.1913, pp.3441.

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

"Makespan Minimization in Job Shops: a Polynomial Time Approximation Scheme", with K.Jansen and R.SolisOba, in Proceedings of Symposium on Theory of Computing (STOC99), pp.394399.

"A Linear Time Approximation Scheme for Job Shop Scheduling Problems", with K.Jansen and R.SolisOba, in Proceedings of APPROX99, Lecture Notes in Computer Science v.1671, pp.177188.

"Approximation algorithms for Maximum Coverage and Max Cut with given sizes of parts", with A. Ageev, In Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO99), Lecture Notes in Computer Science v.1610, pp.1730.

"Best possible approximation algorithm for MAX SAT with cardinality constraint", in Proceedings of APPROX98, Lecture Notes in Computer Science v.1444, pp. 193199.
 I moved to Yahoo! Labs in February, 2014, contact me at my new email: sviri at yahooinc.com also check out my new webpage http://labs.yahoo.com/author/sviri/
 Research Interests
I am interested in Foundations of Computer Science, Algorithmic and Mathematical aspects of Operations Research, Optimization and some aspects of Probability Theory. In particular,
 Inventory and Supply Chain Optimization Problems;
 Scheduling and routing problems;
 Bin Packing problems;
 Discrete facility location problems;
 Online algorithms;
 Approximation algorithms for NPhard optimization problems;
 Randomized algorithms.
 Computational complexity (especially, hardness of approximation);
 Integer and Linear programming, Combinatorial Optimization.
 Probability Theory: Concentration and Moment Inequalities;
 Mathematical modelling of business optimization problems. Algorithm engineering and implementation for such problems;