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

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

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

- "Concentration Inequalities for Nonlinear Matroid
Intersection and Their Applications", with K. Makarychev and W. Schudy,
submitted for publication.

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

- "A Note on Maximizing a Submodular Set Function Subject to Knapsack Constraint" , Operations Research Letters v.32 (2004), pp. 41-43.

- "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.
- "Harmonic
Algorithm for
3-Dimensional Strip Packing Problem",
with N. Bansal, Xin Han, Kazuo Iwama and Guochuan Zhang, in
Proceedings of
SODA2007.
- "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.
- "Two-dimensional
bin packing
with one dimensional resource
augmentation", with
N.
Bansal, Discrete Optimization v. 4 (2007), pp. 143-153.
- "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.
- "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.

- "New Lower Bound for the Flow Shop Scheduling Problem",
with P. Baptiste and A. Kononov, submitted for publication.
- "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.

- "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.
- "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.
- "High-Multiplicity Cyclic Job Shop Scheduling", with T. Kimbrel,
Operations Research Letters 36(5) (2008), pp. 574-578.
- "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.
- "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.
- "The Santa Claus Problem", with N.
Bansal, in Proceedings of STOC2006,
pp. 31--40.
- "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.

- "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.
- "Minimizing
makespan in no-wait
job
shops",
with N. Bansal and M. Mahdian, Mathematics of Operations
Research v.30 (2005), pp. 817--831.
- "A Note on Permutation Flow Shop
Problem", Annals of Operations Research v. 129 (2004), pp. 247-252.
- "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.
- "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.
- "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.
- "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.
- "Linear Time Combinatorial Approximation Scheme for Open Shop
Problem
with
Release Dates",with A. Kononov, Operations Research
Letters,
v. 30 (2002), pp. 276--280.
- "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.
- "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.

- "Inapproximability of the multilevel uncapacitated facility
location problem", with Ravishankar Krishnaswamy, submitted for
publication.

- "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.
- "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.
- "Approximating the minimum quadratic
assignment problems", with
R. Hassin and A. Levin, Transactions on Algorithms 6(1): (2009)
- "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.
- "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.
- "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.
- "Hamiltonian
Completion in Sparse
Random Graphs", with D. Gamarnik, Discrete Applied
Mathematics v.152 (2005), pp. 139-158.

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

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

- "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.
- "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.
- "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.
- "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.
- "Approximating the Maximum Quadratic
Assignment
Problem", with E. Arkin and R. Hassin, Information Processing
Letters
v.77 (2001), pp. 13-16 .
- "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.
- "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.
- "An 0.828-Approximation algorithm
for
uncapacitated
facility location problem", with A.Ageev, Discrete Applied
Mathematics
v.93 (1999), pp. 289-296.
- "Approximation algorithm for weighted p-center problem", Discrete
Analysis
and Operations Research, 1998, series 1, 5(1), pp. 60-63. (in
Russian)

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

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

- "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.
- "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.
- "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.
- "Dynamic application placement under service and memory constraints", with T. Kimbrel, M. Steinder and A. Tantawi, in Proceedings of WEA 2005, pp. 391-402.

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

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.

Maxim Sviridenko homepage