Publications (of Leah Epstein)

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

L. Epstein, A. Levin

An AFPTAS for variable sized bin packing with general activation costs

Journal of Computer and System Sciences, 84, 79-96, 2017.

 

L. Epstein, A. Levin, A. J. Soper, V. A. Strusevich

Power of preemption for minimizing total completion time on uniform parallel machines

SIAM Journal on Discrete Mathematics, 31(1), 101-123, 2017.

 

L. Epstein, I. Yatsiv

Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times

Journal of Scheduling, 20(2), 115-127, 2017.

 

R. Adar, L. Epstein

The k-metric dimension

Journal of Combinatorial Optimization , to appear.

 

L. Epstein,  A. Levin

The benefit of preemption for single machine scheduling so as to minimize total weighted completion time

Operations Research Letters, 44(6) 772-774, 2016.

 

J. Bekesi, Gy. Dosa, L. Epstein

Bounds for online bin packing with cardinality constraints

Information and Computation, 249, 190-204, 2016.

 

L. Epstein

More on batched bin packing

Operations Research Letters, 44(2), 273-277, 2016.

 

L. Epstein, A. Levin, G. J. Woeginger

Vertex cover meets scheduling

Algorithmica, 74(3), 1148-1173, 2016.

 

L. Epstein, H. Zebedat-Haider

Online scheduling of unit jobs on three machines with rejection: A tight result

Information Processing Letters, 116(3), 252-255, 2016.

 

J. Boyar, L. Epstein, L. M. Favrholdt, K. S. Larsen, A. Levin

Online bounded analysis

Proc. of the 11th CSR, 2016, 131-145.

 

J. Boyar, L. Epstein, L. M. Favrholdt, K. S. Larsen, A. Levin

Batch coloring of graphs

Proc. of the 14th WAOA, 2016, 52-64.

 

R. Adar, L. Epstein
The weighted 2-metric dimension of trees in the non- landmarks model
Discrete Optimization, 17, 123-135, 2015.

J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, H. Kellerer, Zs. Tuza
Online black and white bin packing
Theory of Computing Systems, 56(1), 137-155, 2015.


J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, H. Kellerer, A. Levin, Zs. Tuza
Offline black and white bin packing
Theoretical Computer Science, 596, 92-101, 2015.

L. Epstein, E. Kleiman
Selfish vector packing
Proc. of the 23rd ESA, 2015, 471-482.

L. Epstein, E. Kleiman
Scheduling selfish jobs on multidimensional parallel machines
Proc. of the 26th SPAA, 2014, 108-117.

Gy. Dosa, L. Epstein
Colorful bin packing
Proc. of the 14th SWAT, 2014, 170-181.

This conference paper was merged with another paper for the journal version, and will appear as:

M. Bohm, Gy. Dosa,  L. Epstein, J. Sgall, P. Vesely 

Colored Bin Packing: Online Algorithms and Lower Bounds

Algorithmica, to appear.

 

Gy. Dosa, L. Epstein
The convergence time for selfish bin packing
Proc. of the 7th SAGT, 2014, 37-48.

L. Epstein, H. Zebedat-Haider

Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

Journal of Scheduling, 17(1), 87-93, 2014.


L. Epstein, H. Zebedat-Haider
Online scheduling with rejection and reordering: exact algorithms for unit size jobs.
Journal of Combinatorial Optimization, 28(4), 875-892, 2014.

L. Epstein, A. Levin

An efficient polynomial time approximation scheme for load balancing on uniformly related machines

Mathematical Programming, 147(1-2), 1-23, 2014.


S. Zhang, Z. Qian, J. Wu, S. Lu, L. Epstein

Virtual Network embedding with opportunistic resource sharing

IEEE Transactions on Parallel and Distributed Systems, 25(3), 816-827, 2014.

 

L. Epstein, A. Levin,

Robust approximation schemes for cube packing

SIAM Journal on Optimization, 23(2), pages 1310-1343, 2013.

 

L. Epstein, H. Zebedat-Haider
Rent or buy problems with a fixed time horizon
Proc. of the 38th MFCS, 2013,
361-372.
Also in Theory of Computing Systems, 56(2), 309-329, 2015.

 

R. Adar, L. Epstein

Selfish bin packing with cardinality constraints

Theoretical Computer Science, 495, 66-80, 2013.

 

L. Epstein  M. Feldman, T. Tamir, L. Witkowski, M. Witkowski

Approximate strong equilibria in job scheduling games with two uniformly related machines

Discrete Applied Mathematics, 161(13-14), 1843-1858, 2013.

 

L. Epstein, Cs. Imreh, A. Levin,

Bin covering with cardinality constraint,

Discrete Applied Mathematics, 161(13-14), 1975-1987, 2013.

 

L. Epstein

Bin packing games with selfish items

Proc. of the 38th MFCS, 2013, 8-21 (an invited paper).

L. Epstein, A. Levin, D. Segev, O. Weimann
Improved bounds for online preemptive matching
Proc. of the 30th STACS, 2013, 389-399.

L. Epstein, A. Levin, R. van Stee
A unified approach to truthful scheduling on related machines
Proc. of the 24th SODA, 2013, 1243-1252.

Also in Mathematics of Operations Research, 41(1), 332-351, 2016.

L. Epstein, A. Levin
Bin packing with general cost structures
Mathematical Programming, 132(1-2), 355-391, 2012.

J. Boyar, Gy. Dosa, L. Epstein

On the absolute approximation ratio for First Fit and related results

Discrete Applied Mathematics, 160(13-14), 1914-1923, 2012.


S. Albagli-Kim, L. Epstein, H. Shachnai, T. Tamir
Packing resizable items with application to video delivery over wireless networks
Proc. of the 8th ALGOSENSORS, 2012, 6-17.
Also in Theoretical Computer Science, 553, 91-105, 2014.

L. Epstein, L. Jez, J. Sgall, R. van Stee
Online Scheduling of Jobs with Fixed Start Times on Related Machines

Proc. of the 15th APPROX, 2012, 134-145.

Also in Algorithmica, 74(1), pages 156-176, 2016.

L. Epstein, A. Levin, G. J. Woeginger
The (weighted) metric dimension of graphs: hard and easy cases
Proc. of the 38th WG, 2012, 114-125.
Also in Algorithmica, 72(4), 1130-1171, 2015.

L. Epstein, S. O. Krumke, A. Levin, H. Sperber
Selfish bin coloring
Journal of Combinatorial Optimization, 22(4), 531-548, 2011.

L. Epstein, L. M. Favrholdt, A. Levin
Online variable-sized bin packing with conflicts
Discrete Optimization, 8(2), 333-343, 2011.

L. Epstein, H. Zebedat-Haider
Online scheduling with rejection and withdrawal
Theoretical Computer Science, 412(48), 6666-6674, 2011.

L. Epstein, A. Levin
Scheduling with processing set restrictions: PTAS results for several variants
International Journal of Production Economics, 133(2), 586-595, 2011.

L. Epstein, A. Levin
Robust algorithms for preemptive scheduling
Proc. of the 19th ESA, 2011, 567-578.
Also in Algorithmica, 69(1), 26-57, 2014.

 

L. Epstein, Cs. Imreh, A. Levin, J. Nagy-Gyorgy
On variants of file caching
Proc. of the 38th ICALP, 2011, part 1, 195-206.
Also in Algorithmica ("Online file caching with rejection penalties"), 71(2), 279-306, 2015.

L. Epstein, E. Kleiman
On the quality and complexity of Pareto equlibria in the job scheduling game
Proc. of the 10th AAMAS, 2011, 525-532.

L. Epstein, A. Levin
AFPTAS results for common variants of bin packing: A new method for handling the small items
SIAM Journal on Optimization, 20(6), 3121-3145, 2010.

L. Epstein, A. Levin, R. van Stee
Max-min online allocations with a reordering buffer
Proc. of the 37th ICALP, 2010, part 1, 336-347.
Also in SIAM Journal on Discrete Mathematics, 25(3), 1230-1250, 2011.

L. Epstein, A. Levin, J. Mestre, D. Segev
Improved approximation guarantees for weighted matching in the semi-streaming model
Proc. of the 27th STACS, 2010, 347-358.
Also in SIAM Journal on Discrete Mathematics, 25(3), 1251-1265, 2011.

L. Epstein, A. Levin, A. Marchetti-Spaccamela, N. Megow, J. Mestre, M. Skutella, L. Stougie
Universal sequencing on a single machine
Proc. of the 14th IPCO, 2010, 230-243.

Also in SIAM Journal on Computing, 41(3), 565-586, 2012.

J. Csirik, L. Epstein, Cs. Imreh, A. Levin
Online clustering with variable sized clusters
Proc. of the 35th MFCS, 2010, 282-293.
Also in algorithmica, 65(2), 251-274, 2013.

J. Boyar, L. Epstein, A. Levin
Tight results for Next Fit and Worst Fit with resource augmentation
Theoretical Computer Science, 411(26-28), 2572-2580, 2010.

L. Epstein, A. Levin, B. Menachem
Minimization of SONET ADMs in ring networks revisited
Computing, 87(1-2), 3-19, 2010.

L. Epstein
Equilibria for two parallel links: The strong price of anarchy versus the price of anarchy
Acta Informatica, 47(7-8), 375-389, 2010.

L. Epstein, M. Levy
Dynamic multi-dimensional bin packing
Journal of Discrete Algorithms, 8(4), 356-372, 2010.

L. Epstein, L. M. Favrholdt, J. S. Kohrt
Comparing online algorithms for bin packing problems
Journal of Scheduling, 15(1), 13-21, 2012.

L. Epstein
On online bIn packing with LIB constraints
Naval Research Logistics, 56(8), 780-786, 2009.

L. Epstein, Cs. Imreh, A. Levin
Class constrained bin covering
Theory of Computing Systems, 46(2), 246-260, 2010.

L. Epstein, Cs. Imreh, A. Levin
Class constrained bin packing revisited
Theoretical Computer Science, 411(34-36), 3073-3089, 2010.

Gy. Dosa, L. Epstein
Preemptive online scheduling with reordering
Proc. of the 17th ESA, 2009, 456-467.
Also in SIAM Journal on Discrete Mathematics, 25(1), 21-49, 2011.

L. Epstein, A. Levin
On equilibria for ADM minimization games
Proc. of the 2nd SAGT, 2009, 347-358.
Also in Algorithmica, 63(1-2), 246-273, 2012.

L. Epstein, E. Kleiman, R. van Stee
Maximizing the minimum load: the cost of selfishness
Proc. of the 5th WINE, 2009, 232-243.
This conference paper was split into two parts which appeared as two journal papers.
L. Epstein, E. Kleiman, R. van Stee
The cost of selfishness for maximizing the minimum load on uniformly related machines
Journal of Combinatorial Optimization, 27(4), 767-777, 2014.
and
L. Epstein, E. Kleiman, R. van Stee, X. Chen
Maximizing the minimum load: The cost of selfishness
Theoretical Computer Science, 482, 9-19, 2013.

L. Epstein, E. Kleiman, J. Mestre
Parametric packing of selfish items and the Subset Sum algorithm
Proc. of the 5th WINE, 2009, 67-78.

Also in Algorithmica, 74(1), 177-207, 2016.

L. Epstein, E. Kleiman
Selfish bin packing
Proc. of the 16th ESA, 2008, 368-380.
Also in Algorithmica, 60(2), 368-394, 2011.

L. Epstein, E. Kleiman
Resource augmented semi-online bounded space bin packing
Discrete Applied Mathematics, 157(13), 2785-2798, 2009.

L. Epstein, A. Levin
Improved randomized results for that interval selection problem
Proc. of the 16th ESA, 2008, 381-392.
Also in Theoretical computer Science, 411(34-36), 3129-3135, 2010.

L. Epstein, A. Fiat, M. Levy
Caching content under digital rights management
Proc. of the 6th WAOA, 2008, 188-200.

L. Epstein, A. Levin
An APTAS for generalized cost variable sized bin packing
SIAM Journal on Computing, 38(1), 411-428, 2008.

L. Epstein, A. Levin
Randomized algorithms for online bounded bidding
Information Processing Letters, 110(12-13), 503-506, 2010.

L. Epstein, A. Levin
Asymptotic fully polynomial approximation schemes for variants of open-end bin packing
Information Processing Letters, 109(1), 32-37, 2008.

J. R. Correa, L. Epstein
Bin packing with controllable item sizes
Information and Computation, 206(8), 1003-1016, 2008.

L. Epstein, A. Levin, R. van Stee
Online unit clustering: variations on a theme
Theoretical Computer Science, 407(1-3), 85-96, 2008.

L. Epstein, R. van Stee
The price of anarchy on uniformly related machines revisited
Proc. of the 1st SAGT, 2008, 46-57.
Also in Information and Computation, 212, 37-54, 2012.

Gy. Dosa, L. Epstein
Preemptive scheduling on a small number of hierarchical machines
Information and Computation, 206(5), 602-619, 2008.

Gy. Dosa, L. Epstein
Online scheduling with a buffer on related machines
Journal of Combinatorial Optimization, 20(2), 161-179, 2010.

X. Chen, L. Epstein, Zh. Tan
Semi-online machine covering for two uniform machines
Theoretical Computer Science, 410(47-49), 5047-5062, 2009.

J. Csirik, L. Epstein, Cs. Imreh, A. Levin
On the sum minimization version of the online bin covering problem
Discrete Applied Mathematics, 158(13), 1381-1393, 2010.

L. Epstein, A. Levin
More on online bin packing with two item sizes
Discrete Optimization, 5(4), 705-713, 2008.

L. Epstein, R. van stee
Maximizing the minimum load for selfish agents
Proc. of the 8th LATIN, 2008, 264-275.
Also in Theoretical computer Science, 411(1), 44-57, 2010.

L. Epstein, R. van Stee
On the online unit clustering problem
Proc. of the 5th WAOA, 2007, 193-206.
Also in Transactions on Algorithms, volume 7(1), article 7, 18 pages, 2010.

L. Epstein, R. van Stee
Approximation schemes for packing splittable items with cardinality constraints
Proc. of the 5th WAOA, 2007, 232-245.
The journal version appeared as:
L. Epstein, A. Levin, R. van Stee
Approximation schemes for packing splittable items with cardinality constraints
Algorithmica, 62(1-2), 102-129, 2012.

L. Epstein, A. Levin
On the max coloring problem
Proc. of the 5th WAOA, 2007, 142-155.

Also in Theoretical Computer Science, 462(1), 23-38, 2012.

L. Epstein, A. Levin
Minimum weighted sum bin packing
Proc. of the 5th WAOA, 2007, 218-231.

L. Epstein, R. van Stee
Preemptive scheduling on selfish machines
Proc. of the 4th CAAN, 2007, 57-70.

L. Epstein, R. van Stee
Improved results for a memory allocation problem
Proc. of the 10th WADS, 2007, 362-373.
Also in Theory of Computing Systems, 48(1), 79-92, 2011.

L. Epstein, A. Levin, R. van Stee
Multi-dimensional packing with conflicts
Proc. of the 16th FCT, 2007, 288-299.
Also in Acta Informatica, 45(3), 155-175, 2008.

L. Epstein, T. Erlebach, A. Levin
Online capacitated interval coloring
Proc. of the 1st ESCAPE, 2007, 243-254.
Also in SIAM Jounral on Discrete Mathematics, 23(2), 822-841, 2009.

O. Chassid, L. Epstein
The hierarchical model for load balancing on two machines
Journal of Combinatorial Optimization, 15(4), 305-314, 2008.

L. Epstein, D. Ye
Semi-online scheduling with "end of sequence" information
Journal of Combinatorial Optimization, 14(1), 45-61, 2007.

L. Epstein, R. van Stee
Calculating lower bounds for caching
Computing, 80(3), 275-285, 2007.

L. Epstein, Y. Kleiman, J. Sgall, R. van Stee
Paging with connections: FIFO strikes again
Theoretical Computer Science, 377(1-3), 55-64, 2007.

L. Epstein, L. M. Favrholdt, J. S. Kohrt
Separating online scheduling algorithms with the relative worst order ratio
Journal of Combinatorial Optimization, 12(4), 362-385, 2006.
(In a special issue dedicated to the memory of Yong He.)

L. Epstein, A. Kesselman
On the remove server problem or more about TCP acknowledgments
Theoretical Computer Science, 369(1-3), 285-299, 2006.

L. Epstein, A. Levin
A robust APTAS for the classical bin packing problem
Proc. of the 33rd ICALP, 2006, 214-225.
Also in Mathematical Programming, 119(1), 33-49, 2009.

L. Epstein, A. Levin, G. J. Woeginger
Graph coloring with rejection
Proc. of the 14th ESA, 2006, 364-375.
Also in Journal of Computer and Systems Sciences, 77(2), 439-447, 2011..

L. Epstein, M. M. Halldorsson, A. Levin, H. Shachnai
Weighted sum coloring in batch scheduling of conflicting jobs
Proc. of the 9th APPROX, 2006, 116-127.
Also in Algorithmica, 55(4), 643-665, 2009.

L. Epstein, R. van Stee, T. Tamir
Paging with request sets
Proc of the 10th SWAT, 2006, 124-135.
Also in Theory of Computing Systems, 44(1), 67-81, 2009.

L. Epstein, T. Erlebach, A. Levin
Variable sized online interval coloring with bandwidth
Proc. of the 10th SWAT, 2006, 29-40.
Also in Algorithmica, 53(3), 385-401, 2009.

H. Attiya, L. Epstein, H. Shachnai, T. Tamir
Transactional contention management as a non-clairvoyant scheduling problem
Proc. of the 25th PODC, 2006, 308-315.
Also in Algorithmica, 57(1), 44-61, 2010.

L. Epstein, A. Levin
On bin packing with conflicts
Proc. of the 4th WAOA, 2006, 160-173.
Also in SIAM Journal on Optimization, 19(3), 1270-1298, 2008.

L. Epstein
Bin packing with rejection revisited
Proc. of the 4th WAOA, 2006, 146-159.
Also in Algorithmica, 56(4), 505-528, 2010.

L. Epstein, A. Levin
The chord version for SONET ADMs minimization (an updated version)
Theoretical Computer Science, 349(3), 337-346, 2005.

L. Epstein
Online bin packing with cardinality constraints
Proc. of the 13th ESA (2005), 604-615.
Also in SIAM Journal on Discrete Mathematics, 20(4), 1015-1030, 2006.

L. Epstein, A. Levin
SONET ADMs minimization with divisible paths
Proc. of the 3rd WAOA (2005), 119-132.
Also in Algorithmica, 49(1), 51-68, 2007.

L. Epstein, A. Levin
The conference call search problem in wireless networks
Proc. of the 3rd WAOA (2005), 133-146.
Also in Theoretical Computer Science, 359(1-3), 418-429, 2006.

L. Epstein, M. Levy
Online interval coloring and variants
Proc. of the 32nd ICALP (2005), 602-613.

L. Epstein, M. Levy
Online interval coloring with packing constraints
Proc. of the 30th MFCS (2005), 295-307.
Also in Theoretical Computer Science, 407(1-3), 203-212, 2008.

J. Boyar, L. Epstein, L. M. Favrholdt, J. S. Kohrt, K. S. Larsen, M. M. Pedersen, S. Wohlk
The maximum resource bin packing problem
Proc. of the 15th FCT (2005), 397-408.
Also in Theoretical Computer Science, 362(1-3), 127-139, 2006.

Zh. Tan, Y. He, L. Epstein
Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data
Information and Computation 196(1), 57-70, 2005.

L. Epstein, R. van Stee
This side up!
Proc. of the 2nd WAOA (2004), 48-60.
Also in ACM Transactions on Algorithms, 2(2), 228-243, 2006.

L. Epstein, R. van Stee
Online bin packing with resource augmentation
Proc. of the 2nd WAOA (2004), 23-35.
Also in Discrete Optimization, 4(3-4), 322-333, 2007.

 

L. Epstein, A. Levin
Better bounds for minimizing SONET ADMs
Proc. of the 2nd WAOA (2004), 281-294.
Also in Journal of Computer and System Sciences, 75(2), 122-136, 2009.

L. Epstein, A. Levin
A PTAS for delay minimization in establishing wireless conference calls
Proc. of the 2nd WAOA (2004), 36-47.
Also in Discrete Optimization, 5(1), 88-96, 2008.

L. Epstein, R. van Stee
On variable-sized multidimensional packing
Proc. of the 12th ESA (2004), 287-298.

L. Epstein, R. van Stee
Optimal online bounded space multidimensional packing
Proc. of the 15th SODA (2004), 207-216.
Parts of the two above papers were published as the following journal papers

L. Epstein, R. van Stee
Optimal online algorithms for multidimensional packing problems
SIAM journal on Computing, 35(2), 431-448, 2005.
and
L. Epstein, R. van Stee
Online square and cube packing
Acta Informatica 41(9), 595-606, 2005.
and finally
L. Epstein, R. van Stee
Bounds for online bounded space hypercube packing
Discrete Optimization, 4(2), 185-197, 2007.

L. Epstein, T. Tassa
Optimal preemptive scheduling for general target functions
Proc. of the 29th MFCS (2004), 562-573.
Also in Journal of Computer and System Sciences, 72(1), 132-162, 2006.

A. Bremler-Barr, L. Epstein
Path layout on tree networks: Bounds in different label switching models
Proc. of the 11th SIROCCO (2004), 35-46.
Also in Nordic Journal on Computing, 14(1-2), 109-125, 2007.

W. W. Bein, L. Epstein, L. L. Larmore, J. Noga
Optimally competitive list batching
Proc. of the 9th SWAT (2004), 77-89.

Also in Theoretical Computer Science, 410(38-40), 3631-3639, 2009.

L. Epstein, R. van Stee
Online scheduling of splittable tasks
Proc. of the 9th SWAT (2004), 408-419.
Also in ACM Transactions on Algorithms, 2(1), 79-94, 2006.

L. Epstein, T. Tassa
Approximation schemes for the min-max starting time problem
Proc. of the 28th MFCS (2003), 408-418.
Also in Acta Informatica 40(9), 657-674, 2004.

L. Epstein
Two dimensional packing : the power of rotation
Proc. of the 28th MFCS (2003), 398-407.
Also in Theoretical Computer Science, 411(31-33), 2899-2911, 2010. (as "Two dimensional online bin packing with rotation").

Y. Azar, A. Epstein, L. Epstein
Load balancing of temporary tasks in the Lp norm
Proc. of the 1st WAOA (2003), 53-66.
Also in Theoretical Computer Science, 361(2-3), 314-328, 2006.

L. Epstein, A. Ganot
Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
Proc. of the 1st WAOA (2003), 109-122.
Also in Theory of Computing Systems, 42(4), 431-449, 2008.

L. Epstein
Bin stretching revisited
Acta Informatica, 39(2), 2003, pages 97-117.

L. Epstein, J. Noga, G.J. Woeginger
On-line scheduling of unit time jobs with rejection: minimizing the total completion time
Operation Research Letters, 30(6), 2002, pages 415-420.

 

L. Epstein, T. Tassa
Vector assignment problems: a general framework
Proc. of the 10th ESA (2002), 461-472.
This conference paper was split into two parts which appeared as two journal papers.
L. Epstein, T. Tassa
Vector assignment problems: a general framework
Journal of Algorithms, 48(2), 360-384, 2003.
and
L. Epstein, T. Tassa
Graph based vector assignment problems
Acta Informatica, 42(6-7), 501-514, 2006.

L. Epstein, R. van Stee
Minimizing the maximum starting time on-line
Proc. of the 10th ESA (2002), 449-460.
Also in Information and Computation, 195(1-2), 53-65, 2004.

L. Epstein
Tight bounds for bandwidth allocation on two links
Proc. of the 3rd ARACNE (2002), 39-50.
Also in Discrete Applied Math., 148(2), 181-188, 2005.

L. Epstein, L. M. Favrholdt
Optimal non-preemptive semi-online scheduling on two related machines
Proc. of the 27th MFCS (2002), 245-256.
Also in Journal of Algorithms, 57(1), 49-73, 2005.

L. Epstein, Cs. Imreh, R. van Stee
More on weighted servers or FIFO is better than LRU
Proc. of the 27th MFCS (2002), 257-268.
Also in Theoretical Computer Science, 306(1-3), 305-317, 2003.

Y. Azar, L. Epstein, Y. Richter, G. Woeginger
All norm approximation algorithms
Proc. of the 8th SWAT (2002), 288-297.
Also in Journal of algorithms, 52(2), 120-133, 2004.

M. Chrobak, L. Epstein, J. Noga, J. Sgall, R. van Stee, T. Tichy, N. Vakhania
Preemptive scheduling in overloaded systems
Proc. of the 29th ICALP (2002), 800-811.
Also in Journal of Computer and System Sciences, 67(1), 183-197, 2003.

S. S. Seiden, R. van Stee, L. Epstein
New bounds for variable-sized and resource augmented online bin packing
Proc. of the 29th ICALP (2002), 306-317.
Also in SIAM Journal on Computing, 32(2), 455-469, 2003.

L. Epstein, L. M. Favrholdt
On-line maximizing the number of items packed in variable sized bins
Proc. of the 8th COCOON (2002), 467-475.
Also in Acta Cybernetica, 16, 57-66, 2003.

L. Epstein
On variable sized vector packing
Acta Cybernetica, 16, 47-56, 2003.

 

A. Armon, Y. Azar, L. Epstein, O. Regev
Temporary tasks assignment resolved
Proc. of the 13th SODA (2002), 116-124.
Also in Algorithmica 36(3), 295-314, 2003.
The next paper also branched from the same conference paper
A. Armon, Y. Azar, L. Epstein, O. Regev
On-line restricted assignment of temporary tasks with unknown duration
Information Processing Letters, 85(2), 67-72, 2003.

L. Epstein, L. M. Favrholdt
Optimal preemptive semi-online scheduling to minimize makespan on two related machines
Operations Research Letters, 30(4) 269-275, 2002.

Y. Azar, J. Boyar, L. Epstein, L. M. Favrholdt, K. S. Larsen, M. N. Nielsen
Fair versus unrestricted bin packing
Algorithmica, 34(2), 181-196, 2002.

E. Bach, J. Boyar, L. Epstein, L. M. Favrholdt, T. Jiang, K. S. Larsen, G.-H. Lin, R. van Stee
Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem
Journal of Scheduling (in a special issue on on-line algorithms), 6(2), 131-147, 2003.

L. Epstein, R. van Stee
Lower bounds for on-line single machine scheduling
Proc. of 26th MFCS (2001), 338-350.
Also in Theoretical Computer Science, 299(1-3), 439-450, 2003.

L. Epstein, R. van Stee
Optimal on-line flow time with resource augmentation
Proc. of 13th FCT (2001), 472-482 (was presented at the WEA workshop).
Also in Discrete Applied Math. 154(4), 611-621, 2006.

L. Epstein
On-line variable sized covering
Proc. of 7th COCOON (2001), 463-472.

Also in Information and Computation 171(2), 294-305, 2001.

L. Epstein
Optimal preemptive scheduling on uniform processors with non-decreasing speed ratios
Proc. of 18th STACS (2001), 230-237.

Also in Operations Research Letters 29(2), 93-98, 2001.

Y. Azar, L. Epstein
On-line scheduling with precedence constraints
Proc. of 7th SWAT (2000), 164-174.
Also in Discrete Applied Math. 119(1-2), 169-180, 2002.

Y. Azar, L. Epstein, R. van Stee
Resource augmentation in load balancing
Proc. of 7th SWAT (2000), 189-199.
Also in Journal of Scheduling 3(5), 249-258, 2000. (In a special issue on Approximation Algorithms).

L. Epstein, J. Sgall
A lower bound for on-line scheduling on uniformly related machines
Operations Research Letters 26(1), 17-22, 2000.

L. Epstein, J. Sgall
Approximation schemes for scheduling on uniformly related and identical parallel machines
Proc. of 7th ESA (1999), 151-162.
Also in Algorithmica, 39(1), 43-57, 2004.

L. Epstein, J. Noga, S. Seiden, J. Sgall, G. Woeginger
Randomized on-line scheduling on two uniform machines
Proc. of 10th SODA (1999), 317-326.
Also in Journal of Scheduling 4(2), 71-92, 2001.

N. Alon, Y. Azar, J. Csirik, L. Epstein, S. Sevastianov, A. Vestjens, G. Woeginger
On-line and off-line approximation algorithms for vector covering problems
Algorithmica 21(1), 104-118, 1998.

L. Epstein
Lower bounds for on-line scheduling with precedence constraints on identical machines
Proc. of 1st APPROX (1998), 89-98.
Also in Information Processing Letters 76(4-6), 149-153, 2000.

Y. Azar, L. Epstein
Approximation schemes for covering and scheduling on related machines
Proc. of 1st APPROX (1998), 39-47.

Y. Azar, L. Epstein
On-line machine covering
Proc. of 5th ESA (1997), 23-36.
Also in J. of Scheduling 1(2), 67-77, 1998.

Y. Azar, L. Epstein
On-line load balancing of temporary tasks on identical machines
Proc of 5th ISTCS (1997), 119-25.
Also in SIAM Journal on Discrete Mathematics 18(2), 347-352, 2004.

Y. Azar, L. Epstein
On two dimensional packing
Proc. of 5th SWAT (1996), 321-332.
Also in J. of Algorithms 25(2), 290-310, 1997.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------