On-line Algorithms
- "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.
- "Dynamic Pricing for Impatient Bidders: Possibilities and
Impossibilities", with N. Bansal, N. Chen, N. Cherniavsky, A.
Rudra and B. Schieber, 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.
Bin Packing Problems
- "Harmonic
Algorithm for
3-Dimensional Strip Packing Problem",
with N. Bansal, Xin Han, Kazuo Iwama and Guochuan Zhang, in
Proceedings of
SODA2007.
- "Improved Approximation Algorithms for Multidimensional
Packing Problems", with N. Bansal and A. Caprara, in Proceedings of
FOCS
2006.
- "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.

Scheduling Problems
- "Tight Bounds for the Permutation Flow Shop", with Viswanath
Nagarajan, submitted for publication.
- "Complete complexity classification of shop scheduling problems",
with A. Kononov and S. Sevastianov, submitted for pulication.
- "High-Multiplicity Cyclic Job Shop Scheduling", with T. Kimbrel,
submitted for publication.
- "New Lower Bound for the Flow Shop Scheduling Problem",
with P. Baptiste and A. Kononov, submitted for publication.
- "The Santa Claus Problem", with N.
Bansal,submitted for
publication, preliminary version appeared in Proceedings of STOC2006,
pp. 31--40.
- "Structural
Properties of
Preemptive Schedules",
with P. Baptiste, J. Carlier, A. Kononov, M. Queyranne and S.
Sevastianov,
submitted for publication.
- "Improved approximation
algorithms for Broadcast Scheduling",
with N. Bansal and D. Coppersmith, submitted for publication,
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.
- "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.
Optimization Problems on
Graphs, Facility
Location and Related Problems
- "Approximating the minimum quadratic
assignment problems", with
R. Hassin and A. Levin, submitted for publication.
- "Bundle Pricing with Comparable Items", with Alexander Grigoriev,
Joyce van Loon, Marc Uetz, Tjark Vredeveld, in Proceedings of ESA 2007,
475-486.
- "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.
- "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.
- "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.
- "Tight Approximation Algorithms for Maximum General Assignment
Problems.", with L. Fleischer, M. Goemans and V.
Mirrokni, SODA 2006.
- "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.
- "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.
- "A Note on Maximizing a Submodular
Set
Function
Subject to Knapsack Constraint" , Operations Research Letters v.32
(2004), pp. 41-43.
- "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)
Papers Motivated by Real-Life Optimization Projects
- "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.
- "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.
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
