Leah Epstein

TCS Journal 2026 Journal Article

More on online cardinality constrained bin packing with small cardinality bounds

• János Balogh
• József Békési
• György Dósa
• Leah Epstein
• Asaf Levin

We revisit online bin packing with cardinality constraints. In this problem, a set of items of positive sizes not larger than 1 and an integer parameter k ≥ 2 are given. The goal is to partition the items into the minimum number of valid bins, where a valid bin is a set of at most k items whose total size is at most 1. We provide better bounds on the asymptotic competitive ratio for cardinality constrained bin packing for k = 3, showcasing current methods for designing algorithms for bin packing problems. We extend the lower bound construction for k = 3 for other values of k, improving all known lower bounds on the best possible asymptotic competitive ratio for small k ≥ 3.

MFCS Conference 2025 Conference Paper

An EPTAS for Minimizing the Total Weighted Completion Time of Jobs with Release Dates on Uniformly Related Machines

• Leah Epstein
• Asaf Levin

Scheduling of independent jobs with release dates so as to minimize the total weighted completion time is a well-known scheduling problem. Here, we study it for the classic machine environment of uniformly related machines. An efficient polynomial time approximation scheme (an EPTAS) is a family of (1+ε)-approximation algorithms where the running time is bounded by a polynomial in the input size times a function of ε > 0. For problems that are NP-hard in the strong sense, as it is the case for the problem studied here, an EPTAS is the best possible approximation scheme. We design an EPTAS for the problem by employing known techniques and introducing a large collection of new methods.

TCS Journal 2023 Journal Article

Several methods of analysis for cardinality constrained bin packing

• Leah Epstein

We consider a known variant of bin packing called cardinality constrained bin packing, also called bin packing with cardinality constraints (BPCC). In this problem, there is a parameter k ≥ 2, and items of rational sizes in [ 0, 1 ] are to be packed into bins, such that no bin has more than k items or total size larger than 1. The goal is to minimize the number of bins. A recently introduced concept, called the price of clustering, deals with inputs that are presented in a way that they are split into clusters. Thus, an item has two attributes which are its size and its cluster. The goal is to measure the relation between an optimal solution that cannot combine items of different clusters into bins, and an optimal solution that can combine items of different clusters arbitrarily. Usually the number of clusters may be large, while clusters are relatively small, though not trivially small. Such problems are related to greedy bin packing algorithms, and to batched bin packing, which is similar to the price of clustering, but there is a constant number of large clusters. We analyze the price of clustering for BPCC, including the parametric case with bounded item sizes. We discuss several greedy algorithms for this problem that were not studied in the past, and comment on batched bin packing.

TCS Journal 2017 Journal Article

Scheduling selfish jobs on multidimensional parallel machines

• Leah Epstein
• Elena Kleiman

We study the multidimensional vector scheduling problem with selfish jobs, both in non-cooperative and in cooperative versions, in two variants. These variants differ in the private costs of the jobs: in the first variant, the cost is the ℓ ∞ norm (maximum over components) while in the second variant it is the ℓ 1 norm (sum of components) of the load. We show existence of assignments that are Nash, strong Nash, weakly and strictly Pareto optimal Nash equilibria in these settings. For the first variant, we improve upon the previous bounds on the price of anarchy for the non-cooperative case, and find tight bounds for every number of machines and dimension. For the cooperative case we provide tight bounds on the strong prices of anarchy and stability, as well as tight bounds on weakly and strictly Pareto optimal prices of anarchy and stability, for every number of machines and dimension. For the second variant, which was not considered before, we again consider all the aforementioned measures, and find tight bounds, each of which being a function of the number of machines and the dimension, showing cardinal differences in the behavior of these measures both between the two variants, and in comparison to the one-dimensional case.

TCS Journal 2015 Journal Article

Offline black and white bin packing

• János Balogh
• József Békési
• György Dósa
• Leah Epstein
• Hans Kellerer
• Asaf Levin
• Zsolt Tuza

We define and study a variant of bin packing called unrestricted black and white bin packing. Similarly to standard bin packing, a set of items of sizes in [ 0, 1 ] are to be partitioned into subsets of total size at most 1, called bins. Items are of two types, called black and white, and the item types must alternate in each bin, that is, two items of the same type cannot be assigned consecutively into a bin. Thus, a subset of items of total size at most 1 can form a valid bin if and only if the absolute value of the difference between the numbers of black items and white items in the subset is at most 1. We study this problem both with respect to the absolute and the asymptotic approximation ratios. We design a fast heuristic whose absolute approximation ratio is 2. We also design an APTAS and modify it into an AFPTAS. The APTAS can be used as an algorithm of absolute approximation ratio 3 2, which is the best possible absolute approximation ratio for the problem unless P = NP.

TCS Journal 2014 Journal Article

Packing resizable items with application to video delivery over wireless networks

• Sivan Albagli-Kim
• Leah Epstein
• Hadas Shachnai
• Tami Tamir

Motivated by fundamental optimization problems in video delivery over wireless networks, we consider the following problem of packing resizable items (PRI). Given is a bin of capacity B > 0, and a set I of items. Each item j ∈ I has a size s j > 0. A packed item must stay in the bin for a fixed common time interval. To accommodate additional items in the bin, each item j can be compressed to a given size p j ∈ [ 0, s j ) for at most a fraction q j ∈ [ 0, 1 ) of the packing interval, during one continuous sub-interval. The goal is to pack in the bin, for the given time interval, a subset of items of maximum cardinality. PRI is a generalization of the well-known Knapsack problem, and it is strongly NP-hard already for highly restricted instances. Our main result is an approximation algorithm that packs, for any instance I of PRI, at least 2 3 OPT ( I ) − 2 items, where OPT ( I ) is the number of items packed in an optimal solution. Our algorithm yields a better performance ratio for instances in which the maximum compression time of an item is q max ∈ ( 0, 1 2 ). For subclasses of instances arising in realistic scenarios, we give an algorithm that packs at least OPT ( I ) − 2 items. Finally, we show that a non-trivial subclass of instances admits an asymptotic fully polynomial time approximation scheme (AFPTAS).

SODA Conference 2013 Conference Paper

A unified approach to truthful scheduling on related machines

• Leah Epstein
• Asaf Levin
• Rob van Stee

MFCS Conference 2013 Conference Paper

Bin Packing Games with Selfish Items

• Leah Epstein

Abstract We discuss recent work on the subject of selfish bin packing. In these problems, items are packed into bins, such that each item wishes to minimize its own payoff. We survey the known results for a number of variants, focusing on worst-case Nash equilibria and other kinds of equilibria, and mentioning several results regarding issues of complexity and convergence to equilibria.

TCS Journal 2013 Journal Article

Maximizing the minimum load: The cost of selfishness

• Xujin Chen
• Leah Epstein
• Elena Kleiman
• Rob van Stee

We consider a scheduling problem on m machines, where each job is controlled by a selfish agent. Each agent is only interested in minimizing its own cost, defined as the total load of the machine that its job is assigned to. We consider the objective of maximizing the minimum load (the value of the cover) over the machines. Unlike the regular makespan minimization problem, which was extensively studied in a game-theoretic context, this problem has not been considered in this setting before. We study the price of anarchy (poa) and the price of stability (pos). These measures are unbounded already for two uniformly related machines [11], and therefore we focus on identical machines. We show that the pos is 1, and derive tight bounds on the pure poa for m ≤ 7 and on the overall pure poa, showing that its value is exactly 1. 7. To achieve the upper bound of 1. 7, we make an unusual use of weighting functions. Finally, we show that the mixed poa grows exponentially with m for this problem. In addition, we consider a similar setting of selfish jobs with a different objective of minimizing the maximum ratio between the loads of any pair of machines in the schedule. We show that under this objective the pos is 1 and the pure poa is 2, for any m ≥ 2.

MFCS Conference 2013 Conference Paper

Rent or Buy Problems with a Fixed Time Horizon

• Leah Epstein
• Hanan Zebedat-Haider

Abstract We study several variants of a fixed length ski rental problem and related scheduling problems with rejection. A ski season consists of m days, and an equipment of cost 1 is to be used during these days. The equipment can be bought on any day, in which case it can be used without any additional cost starting that day and until the vacation ends. On each day, the algorithm is informed with the current non-negative cost of renting the equipment. As long as the algorithm did not buy the equipment, it must rent it every day of the vacation, paying the rental cost of each day of rental. We consider the case of arbitrary, non-increasing, and non-decreasing rental costs. We consider the case where the season cannot end before the m th day, and the case that it can end without prior notice. We propose optimal online algorithms for all values of m for all variants. The optimal competitive ratios are either defined by solutions of equations (closed formulas or finite recurrences) or sets of mathematical programs, and tend to 2 as m grows.

TCS Journal 2013 Journal Article

Selfish bin packing with cardinality constraints

• Ron Adar
• Leah Epstein

Bin packing with cardinality constraints is a variant of bin packing. In this problem, items with sizes of at most 1 are to be partitioned (or packed) into subsets called bins, such that the total size of items packed into a bin would not exceed 1, and each bin would contain at most k items, for a given integer parameter k > 1. We consider a class of games resulting from this problem by seeing the items as selfish players, trying to be packed into a (valid) bin where the total size of items is maximized. Such games always admit pure Nash equilibria. We analyze the Price of Anarchy (PoA) of such games, defined as the asymptotic worst case ratio between the maximum number of bins in a pure Nash equilibrium (NE), and the minimum number of bins in any valid solution, that is, the number of bins in a socially optimal solution. We provide a complete analysis of the PoA as a function of k; we prove that for k = 2, any NE is an optimal solution, for k ⩾ 4, the PoA is exactly 2 − 1 k, and for k = 3, the PoA is exactly 11 7.

TCS Journal 2012 Journal Article

On the max coloring problem

• Leah Epstein
• Asaf Levin

We consider max coloring on hereditary graph classes. The problem is defined as follows. Given a graph G = ( V, E ) and positive node weights w: V → ( 0, ∞ ), the goal is to find a proper node coloring of G whose color classes C 1, C 2, …, C k minimize ∑ i = 1 k max v ∈ C i w ( v ). We design a general framework which allows to convert approximation algorithms for standard node coloring into algorithms for max coloring. The approximation ratio increases by a multiplicative factor of at most e for deterministic offline algorithms and for randomized online algorithms, and by a multiplicative factor of at most 4 for deterministic online algorithms. We consider two specific hereditary classes which are interval graphs and perfect graphs. For interval graphs, we study the problem in several online environments. In the List Model, intervals arrive one by one, in some order. In the Time Model, intervals arrive one by one, sorted by their left endpoints. For the List Model we design a deterministic 12-competitive algorithm, and a randomized 3 e -competitive algorithm. In addition, we prove a lower bound of 4 on the competitive ratio of any deterministic or randomized algorithm. For the Time Model, we use simplified versions of the algorithm and the lower bound of the List Model, to develop a deterministic 4-competitive algorithm, a randomized e -competitive algorithm, and to design a lower bounds of ϕ ≈ 1. 618 on the deterministic competitive ratio and a lower bound of 4 3 on the randomized competitive ratio. The former lower bounds hold even for unit intervals. For unit intervals in the List Model, we obtain a deterministic 8 -competitive algorithm, a randomized 2 e -competitive algorithm and lower bounds of 2 on the deterministic competitive ratio and 11 6 ≈ 1. 8333 on the randomized competitive ratio. Finally, we employ our framework to obtain an offline e -approximation algorithm for max coloring of perfect graphs, improving and simplifying a recent result of Pemmaraju and Raman.

AAMAS Conference 2011 Conference Paper

On the Quality and Complexity of Pareto Equilibria in the Job Scheduling Game

• Leah Epstein
• Elena Kleiman

In the well-known scheduling game, a set of jobs controlled by selfish players wishes each to minimize the load of the machine on which it is executed, while the social goal is to minimize the makespan, that is, the maximum load of any machine. We consider this problem on the three most common machines models, identical machines, uniformly related machines and unrelated machines, with respect to both weak and strict Pareto optimal Nash equilibria. These are kinds of equilibria which are stable not only in the sense that no player can improve its cost by changing its strategy unilaterally, but in addition, there is no alternative choice of strategies for the entire set of players where no player increases its cost, and at least one player reduces its cost (in the case of strict Pareto optimality), or where all players reduce their costs (in the case of weak Pareto optimality). We give a complete classification of the social quality of such solutions with respect to an optimal solution, that is, we find the Price of Anarchy of such schedules as a function of the number of machines, m. In addition, we give a full classification of the recognition complexity of such schedules.

TCS Journal 2011 Journal Article

Online scheduling with rejection and withdrawal

• Leah Epstein
• Hanan Zebedat-Haider

We study an online scheduling problem with rejection, in which some rearrangement of the solution is allowed. This problem is called scheduling with rejection and withdrawal. Each arriving job has a processing time and a rejection cost associated with it, and it needs to be either assigned to a machine or rejected upon arrival. At termination, it is possible to choose at most a fixed number of scheduled jobs and withdraw them (i. e. , decide to reject them). We study the minimization version, where the goal is to minimize the sum of the makespan and the total rejection cost (which corresponds to the penalty), and the maximization problem, where the goal is to maximize the sum of the minimum load and the total rejection cost (which corresponds to profit). We study environments of machines, which are the case of m identical machines and the case of two uniformly related machines, and show a strong relation between these problems and the related classic online scheduling problems which they generalize, in contrast to standard scheduling with rejection, which typically makes the scheduling problems harder.

TCS Journal 2010 Journal Article

Class constrained bin packing revisited

• Leah Epstein
• Csanád Imreh
• Asaf Levin

We study the following variant of the bin packing problem. We are given a set of items, where each item has a (non-negative) size and a color. We are also given an integer parameter k, and the goal is to partition the items into a minimum number of subsets such that for each subset S in the solution, the total size of the items in S is at most 1 (as in the classical bin packing problem) and the total number of colors of the items in S is at most k (which distinguishes our problem from the classical version). We follow earlier work on this problem and study the problem in both offline and online scenarios.

TCS Journal 2010 Journal Article

Improved randomized results for the interval selection problem

• Leah Epstein
• Asaf Levin

Online interval selection is a problem in which intervals arrive one by one, sorted by their left endpoints. Each interval has a length and a non-negative weight associated with it. The goal is to select a non-overlapping set of intervals with maximal total weight and run them to completion. The decision regarding a possible selection of an arriving interval must be done immediately upon its arrival. The interval may be preempted later in favor of selecting an arriving overlapping interval, in which case the weight of the preempted interval is lost. We follow Woeginger (1994) [12] and study the same models. The types of instances we consider are C-benevolent instances, where the weight of an interval is a monotonically increasing (convex) function of length, and D-benevolent instances, where the weight of an interval is a monotonically decreasing function of length. Some of our results can be extended to the case of unit length intervals with arbitrary costs. We significantly improve the previously known bounds on the performance of online randomized algorithms for the problem, namely, we introduce a new algorithm for the D-benevolent case and for unit intervals, which uses a parameter θ and has a competitive ratio of at most θ 2 ln θ ( θ − 1 ) 2. This value is equal to approximately 2. 4554 for θ ≈ 3. 513 being the solution of the equation x − 1 = 2 ln x. We further design a lower bound of 1 + ln 2 ≈ 1. 693 on the competitive ratio of any randomized algorithm. The lower bound is valid for any C-benevolent instance, some D-benevolent functions and for unit intervals. We further show a lower bound of 3 2 for a wider class of D-benevolent instances. This improves over previously known lower bounds. We also design a barely random online algorithm for the D-benevolent case and the case of unit intervals, which uses a single random bit, and has a competitive ratio of 3. 22745.

TCS Journal 2010 Journal Article

Maximizing the minimum load for selfish agents

• Leah Epstein
• Rob van Stee

We consider the problem of maximizing the minimum load (completion time) for machines that are controlled by selfish agents, who are only interested in maximizing their own profit. Unlike the classical load balancing problem, this problem has not been considered for selfish agents until now. The goal is to design a truthful mechanism, i. e. , one in which all users have an incentive to tell the truth about the speeds of their machines. This then allows us to find good job assignments. It is known that this requires monotone approximation algorithms, in which the amount of work assigned to an agent does not increase if its bid (claimed cost per unit work) increases. For a constant number of machines, m, we show a monotone polynomial-time approximation scheme (PTAS) with running time that is linear in the number of jobs. It uses a new technique for reducing the number of jobs while remaining close to the optimal solution. We use an FPTAS for the classical problem, i. e. , where no selfish agents are involved, to give a monotone FPTAS. Additionally, we give a monotone approximation algorithm with approximation ratio min ( m, ( 2 + ε ) s 1 / s m ) where ε > 0 can be chosen arbitrarily small and s i is the (real) speed of machine i. Finally we give improved results for two machines.

MFCS Conference 2010 Conference Paper

Online Clustering with Variable Sized Clusters

• János Csirik
• Leah Epstein
• Csanád Imreh
• Asaf Levin

Abstract In online clustering problems, the classification of points into sets (called clusters) is done in an online fashion. Points arrive one by one at arbitrary locations, to be assigned to clusters at the time of arrival. A point can be assigned to an existing cluster, or a new cluster can be opened for it. We study a one dimensional variant on a line, where there is no restriction on the length of a cluster, and the cost of a cluster is the sum of a fixed set-up cost and its diameter. The goal is to minimize the sum of costs of the clusters used by the algorithm. We study several variants, all maintaining the essential property that a point which was assigned to a given cluster must remain assigned to this cluster, and clusters cannot be merged. In the strict variant, the diameter and the exact location of the cluster must be fixed when it is initialized. In the flexible variant, the algorithm can shift the cluster or expand it, as long as it contains all points assigned to it. In an intermediate model, the diameter is fixed in advance while the exact location can be modified. We give tight bounds on the competitive ratio of any online algorithm in each of these variants. In addition, for each one of the models, we consider also the semi-online case, where points are presented sorted by their location.

TCS Journal 2010 Journal Article

Tight results for Next Fit and Worst Fit with resource augmentation

• Joan Boyar
• Leah Epstein
• Asaf Levin

It is well known that the two simple algorithms for the classic bin packing problem, NF and WF both have an approximation ratio of 2. However, WF seems to be a more reasonable algorithm, since it never opens a new bin if an existing bin can still be used. Using resource augmented analysis, where the output of an approximation algorithm, which can use bins of size b > 1, is compared to an optimal packing into bins of size 1, we give a complete analysis of the asymptotic approximation ratio of WF and of NF, and use it to show that WF is strictly better than NF for any 1 < b < 2, while they have the same asymptotic performance guarantee for all b ≥ 2, and for b = 1.

TCS Journal 2010 Journal Article

Two-dimensional online bin packing with rotation

• Leah Epstein

In two-dimensional bin packing problems, the input items are rectangles which need to be packed in a non-overlapping manner. The goal is to assign the items into unit squares using an axis-parallel packing. Most previous work on online packing concentrated on items of fixed orientation, which must be assigned such that their bottom side is parallel to the bottom of the bin. In this paper we study the case of rotatable items, which can be rotated by ninety degrees. We give almost tight bounds on the (asymptotic) competitive ratio of bounded space bin packing of rotatable items, and introduce a new unbounded space algorithm. This improves the results of Fujita and Hada.

TCS Journal 2009 Journal Article

Optimally competitive list batching

• Wolfgang Bein
• Leah Epstein
• Lawrence L. Larmore
• John Noga

Batching has been studied extensively in the offline case, but applications such as manufacturing or TCP acknowledgment often require online solutions. We consider online batching problems, where the order of jobs to be batched is fixed and where we seek to minimize the sum of the completion times of the jobs. We present optimally competitive online algorithms for both s -batch and p -batch problems, and we also derive results for certain naturally occurring special cases, such as the case of unit processing times.

TCS Journal 2009 Journal Article

Semi-online machine covering for two uniform machines

• Xingyu Chen
• Leah Epstein
• Zhiyi Tan

The machine covering problem deals with partitioning a sequence of jobs among a set of machines, so as to maximize the completion time of the least loaded machine. We study a semi-online variant, where jobs arrive one by one, sorted by non-increasing size. The jobs are to be processed by two uniformly related machines, with a speed ratio of q ≥ 1. Each job has to be processed continuously, in a time slot assigned to it on one of the machines. This assignment needs to be performed upon the arrival of the job. The length of the time slot, which is required for a specific job to run on a given machine, is equal to the size of the job divided by the speed of the machine. We give a complete competitive analysis of this problem by providing an algorithm of the best possible competitive ratio for every q ≥ 1. We first give a tight analysis of the performance of a natural greedy algorithm L P T for the problem. To achieve the best possible performance for the semi-online problem, we use a combination of L P T, together with two alternative algorithms which we design. The new algorithms attain the best possible competitive ratios in the two intervals q ∈ ( 1, 1. 5 ) and q ∈ ( 2. 4856, 1 + 3 ), respectively, whereas the greedy algorithm has the best possible competitive ratio for any other q ≥ 1.

TCS Journal 2008 Journal Article

Online interval coloring with packing constraints

• Leah Epstein
• Meital Levy

We study online interval coloring problems with bandwidth. We are interested in some variants motivated by bin packing problems. Specifically we consider open-end coloring, cardinality constrained coloring, coloring with vector constraints and finally a combination of both the cardinality and the vector constraints. We construct competitive algorithms for each of the variants. Additionally, we present a lower bound of 24/7 for interval coloring with bandwidth, which holds for all the above models, and improves the current lower bound for the standard interval coloring with bandwidth problem.

TCS Journal 2008 Journal Article

Online unit clustering: Variations on a theme

• Leah Epstein
• Asaf Levin
• Rob van Stee

Online unit clustering is a clustering problem where classification of points is done in an online fashion, but the exact location of clusters can be modified dynamically. We study several variants and generalizations of the online unit clustering problem, which are inspired by variants of packing and scheduling problems in the literature.

TCS Journal 2007 Journal Article

Paging with connections: FIFO strikes again

• Leah Epstein
• Yanir Kleiman
• Jiří Sgall
• Rob van Stee

We continue the study of the integrated document and connection caching problem. We focus on the case where the connection cache has a size of one and show that this problem is not equivalent to standard paging, even if there are only two locations for the pages, by giving the first lower bound that is strictly higher than k for this problem. We then give the first upper bound below the trivial value of 2 k for this problem. Our upper bound is k + 4 ℓ where ℓ is the number of locations where the requested pages in a phase come from. This algorithm groups pages by location. In each phase, it evicts all pages from one location before moving on to the next location. In contrast, we show that the lru algorithm is not better than 2 k -competitive. We also examine the resource augmented model and show that the plain fifo algorithm is optimal for the case h = 2 and all k ≥ 2, where h is the size of the offline document cache. We show that also in this case fifo is better than lru, although this is not true for standard paging.

TCS Journal 2006 Journal Article

Load balancing of temporary tasks in the ℓ p norm

• Yossi Azar
• Amir Epstein
• Leah Epstein

We consider the on-line load balancing problem where there are m identical machines (servers). Jobs arrive at arbitrary times, where each job has a weight and a duration. A job has to be assigned upon its arrival to exactly one of the machines. The duration of each job becomes known only upon its termination (this is called temporary tasks of unknown durations). Once a job has been assigned to a machine it cannot be reassigned to another machine. The goal is to minimize the maximum over time of the sum (over all machines) of the squares of the loads, instead of the traditional maximum load. Minimizing the sum of the squares is equivalent to minimizing the load vector with respect to the ℓ 2 norm. We show that for the ℓ 2 norm the greedy algorithm performs within at most 1. 493 of the optimum. We show (an asymptotic) lower bound of 1. 33 on the competitive ratio of the greedy algorithm. We also show a lower bound of 1. 20 on the competitive ratio of any algorithm. We extend our techniques and analyze the competitive ratio of the greedy algorithm with respect to the ℓ p norm. We show that the greedy algorithm performs within at most 2 - Ω ( 1 / p ) of the optimum. We also show a lower bound of 2 - O ( ln p / p ) on the competitive ratio of any on-line algorithm.

TCS Journal 2006 Journal Article

On the remote server problem or more about TCP acknowledgments

• Leah Epstein
• Alex Kesselman

We study an on-line problem that is motivated by service calls management in a remote support center. When a customer calls the remote support center of a software company, a technician opens a service request and assigns it a severity rating. This request is then transferred to the appropriate support engineer (SE) who establishes a connection to the customer's site and uses remote diagnostic capabilities to resolve the problem. We assume that the SE can service at most one customer at time and a request service time is negligible. There is a constant setup cost of creating a new connection to a customer's site and a specific cost per request for delaying its service that depends on the severity of the request. The problem is to decide which customers to serve first so as to minimize the incurred cost. This problem with just two customers is a natural generalization of the TCP acknowledgment problem. For the on-line version of the Remote Server Problem (RSP), we present algorithms for the general case and for a special casef of two customers that achieve competitive ratios of exactly 4 and 3, respectively. We also show that no deterministic on-line algorithm can have competitive ratio better than 3. Then we study generalized versions of our model, these are the case of an asymmetric setup cost function and the case of multiple SEs. For the off-line version of the RSP, we derive an optimal algorithm with a polynomial running time for a constant number of customers.

TCS Journal 2006 Journal Article

The maximum resource bin packing problem

• Joan Boyar
• Leah Epstein
• Lene M. Favrholdt
• Jens S. Kohrt
• Kim S. Larsen
• Morten M. Pedersen
• Sanne Wøhlk

Usually, for bin packing problems, we try to minimize the number of bins used or in the case of the dual bin packing problem, maximize the number or total size of accepted items. This paper presents results for the opposite problems, where we would like to maximize the number of bins used or minimize the number or total size of accepted items. We consider off-line and on-line variants of the problems. For the off-line variant, we require that there be an ordering of the bins, so that no item in a later bin fits in an earlier bin. We find the approximation ratios of two natural approximation algorithms, First-Fit-Increasing and First-Fit-Decreasing for the maximum resource variant of classical bin packing. For the on-line variant, we define maximum resource variants of classical and dual bin packing. For dual bin packing, no on-line algorithm is competitive. For classical bin packing, we find the competitive ratio of various natural algorithms. We study the general versions of the problems as well as the parameterized versions where there is an upper bound of 1 k on the item sizes, for some integer k.

MFCS Conference 2005 Conference Paper

Online Interval Coloring with Packing Constraints

• Leah Epstein
• Meital Levy

Abstract We study online interval coloring problems with bandwidth. We are interested in some variants motivated by bin packing problems. Specifically we consider open-end coloring, cardinality constrained coloring, coloring with vector constraints and finally a combination of both the cardinality and the vector constraints. We construct competitive algorithms for each of the variants. Additionally, we present a lower bound of 24/7 for interval coloring with bandwidth, which holds for all the above models, and improves the current lower bound for the standard interval coloring with bandwidth.

TCS Journal 2005 Journal Article

The chord version for SONET ADMs minimization

• Leah Epstein
• Asaf Levin

We consider a problem which arises in optical routing. WDM/SONET rings are a network architecture used by telecommunications carriers for traffic streams. The dominant cost factor in such networks is the total number of add-drop multiplexers (ADMs) used. A list of traffic streams to be routed between pairs of nodes is given. In this paper we consider the problem where we need to assign a route and a wavelength to each traffic stream, minimizing the total number of used SONET ADMs. This is called the chord version of the SONET ADMs minimization problem, to denote the fact that the routing is not given a priori. The best previously known approximation algorithms for this problem have the performance guarantee of 3 2. We present an improved algorithm with performance guarantee of exactly 10 7 ≈ 1. 42857. Moreover, we study some natural heuristics for this problem, and give tight analysis of their approximation ratios.

SODA Conference 2004 Conference Paper

Optimal online bounded space multidimensional packing

• Leah Epstein
• Rob van Stee

MFCS Conference 2004 Conference Paper

Optimal Preemptive Scheduling for General Target Functions

• Leah Epstein
• Tamir Tassa

Abstract We study the problem of optimal preemptive scheduling with respect to a general target function. Given n jobs with associated weights and m ≤ n uniformly related machines, one aims at scheduling the jobs to the machines, allowing preemptions but forbidding parallelization, so that a given target function of the loads on each machine is minimized. This problem was studied in the past in the case of the makespan. Gonzalez and Sahni [7] and later Shachnai, Tamir and Woeginger [12] devised a polynomial algorithm that outputs an optimal schedule for which the number of preemptions is at most 2( m –1). We extend their ideas for general symmetric, convex and monotone target functions. This general approach enables us to distill the underlying principles on which the optimal makespan algorithm is based. More specifically, the general approach enables us to identify between the optimal scheduling problem and a corresponding problem of mathematical programming. This, in turn, allows us to devise a single algorithm that is suitable for a wide array of target functions, where the only difference between one target function and another is manifested through the corresponding mathematical programming problem.

MFCS Conference 2003 Conference Paper

Approximation Schemes for the Min-Max Starting Time Problem

• Leah Epstein
• Tamir Tassa

Abstract We consider the off-line scheduling problem of minimizing the maximal starting time. The input to this problem is a sequence of n jobs and m identical machines. The goal is to assign the jobs to the machines so that the first time in which all jobs have already started their processing is minimized, under the restriction that the processing of the jobs on any given machine must respect their original order. Our main result is a polynomial time approximation scheme for this problem in the case where m is considered as part of the input. As the input to this problem is a sequence of jobs, rather than a set of jobs where the order is insignificant, we present techniques that are designed to handle ordering constraints. Those techniques are combined with common techniques of assignment problems in order to yield a polynomial time approximation scheme.

TCS Journal 2003 Journal Article

Lower bounds for on-line single-machine scheduling

• Leah Epstein
• Rob van Stee

The problem of scheduling jobs that arrive over time on a single machine is well studied. We study the preemptive model and the model with restarts. We provide lower bounds for deterministic and randomized algorithms for several optimality criteria: weighted and unweighted total completion time, and weighted and unweighted total flow time. By using new techniques, we provide the first lower bounds for several of these problems, and we significantly improve the bounds that were known.

TCS Journal 2003 Journal Article

More on weighted servers or FIFO is better than LRU

• Leah Epstein
• Csanád Imreh
• Rob van Stee

We consider a generalized two-server problem on the uniform space in which servers have different costs. Previous work focused on the case where the ratio between these costs was very large. We give results for varying ratios. For ratios below 2. 2, we present a best possible algorithm which is trackless. We present a general lower bound for trackless algorithms depending on the cost ratio, proving that our algorithm is the best possible trackless algorithm up to a constant factor for any cost ratio. The results are extended for the case where we have two sets of servers with different costs.

MFCS Conference 2003 Conference Paper

Two Dimensional Packing: The Power of Rotation

• Leah Epstein

Abstract Recently there is a rise in the study of two-dimensional packing problems. In such problems the input items are rectangles which need to be assigned into unit squares. However, most of the previous work concentrated on fixed items. Fixed items have a fixed direction and must be assigned so that their bottom is parallel to the bottom of the bin. In this paper we study two-dimensional bin packing of rotatable items. Those are rectangles which can be rotated by ninety degrees. We give almost tight bounds for bounded space bin packing of rotatable items, and introduce a new unbounded space algorithm. This improves the results of Fujita and Hada.

MFCS Conference 2002 Conference Paper

More on Weighted Servers or FIFO is Better than LRU

• Leah Epstein
• Csanád Imreh
• Rob van Stee

Abstract We consider a generalized 2-server problem on the uniform space in which servers have different costs. Previous work focused on the case where the ratio between these costs was very large. We give results for varying ratios. For ratios below 2. 2, we present an optimal algorithm which is trackless. We present a general lower bound for trackless algorithms depending on the cost ratio, proving that our algorithm is the optimal trackless algorithm up to a constant factor for any cost ratio. The results are extended for the case where we have two sets of servers with different costs.

MFCS Conference 2002 Conference Paper

Optimal Non-preemptive Semi-online Scheduling on Two Related Machines

• Leah Epstein
• Lene M. Favrholdt

Abstract We consider the following non-preemptive semi-online scheduling problem. Jobs with non-increasing sizes arrive one by one to be scheduled on two uniformly related machines, with the goal of minimizing the makespan. We analyze both the optimal overall competitive ratio, and the optimal competitive ratio as a function of the speed ratio ( q ≥ 1) between the two machines. We show that the greedy algorithm LPT has optimal competitive ratio 1/4(1 + √17) ≈ 1. 28 overall, but does not have optimal competitive ratio for every value of q. We determine the intervals of q where LPT is an algorithm of optimal competitive ratio, and design different algorithms of optimal competitive ratio for the intervals where it fails to be the best algorithm. As a result, we give a tight analysis of the competitive ratio for every speed ratio.

SODA Conference 2002 Conference Paper

Temporary tasks assignment resolved

• Amitai Armon
• Yossi Azar
• Leah Epstein
• Oded Regev 0001

MFCS Conference 2001 Conference Paper

Lower Bounds for On-Line Single-Machine Scheduling

• Leah Epstein
• Rob van Stee

Abstract The problem of scheduling jobs that arrive over time on a single machine is well-studied. We study the preemptive model and the model with restarts. We provide lower bounds for deterministic and randomized algorithms for several optimality criteria: weighted and unweighted total completion time, and weighted and unweighted total flow time. By using new techniques, we provide the first lower bounds for several of these problems, and we significantly improve the bounds that were known.

SODA Conference 1999 Conference Paper

Randomized Online Scheduling on Two Uniform Machines

• Leah Epstein
• John Noga
• Steven S. Seiden
• Jirí Sgall
• Gerhard J. Woeginger