Guaranteeing Fair Service to Persistent Dependent Tasks.
We introduce a new scheduling problem that is motivated by applications in the area of access and flow control in high-speed and wireless networks. An instance of the problem consists of a set of persistent tasks that have to be scheduled repeatedly. Each task has a demand to be scheduled "as often as possible." There is no explicit limit on the number of tasks that can be scheduled concurrently. However, such limits are imposed implicitly because some tasks may be in conflict and cannot be scheduled simultaneously. These conflicts are presented in the form of a conflict graph. We define parameters which quantify the fairness and regularity of a given schedule. We then proceed to show lower bounds on these parameters and present fair and efficient scheduling algorithms for the case where the conflict graph is an interval graph. Some of the results presented here extend to the case of perfect graphs and circular-arc graphs as well.
Introduction
In this paper we consider a new form of a scheduling
problem which is characterized by two features:
Persistence of the tasks: A task does not simply go
away once it is scheduled. Instead, each task must
be scheduled innitely many times. The goal is to
schedule every task as frequently as possible.
Dependence among the tasks: Some tasks con
ict with
each other and hence cannot be scheduled concur-
rently. These con
icts are given by a con
ict graph.
This graph imposes constraints on the sets of tasks
that may be scheduled concurrently. Note that these
constraints are not based simply on the cardinality of
the sets, but rather on the identity of the tasks within
the sets.
Extended summary
y IBM { Research Division, T. J. Watson Research Center,
Yorktown Heights, NY 10598.
Email: famotz,sbar,madhug@watson.ibm.com.
z Dept. of Computer Science, Columbia University, New
York, NY 10027. Email: mayer@cs.columbia.edu. Part of this
work was done while the author was at the IBM T. J. Watson
Research Center. Partially supported by an IBM Graduate
Fellowship, NSF grant CCR-93-16209, and CISE Institutional
Infrastructure Grant CDA-90-24735
We consider both the problems of allocation, i.e.,
how often should a task be scheduled and regularity,
i.e., how evenly spaced are lengths of the intervals
between successive scheduling of a specic task. We
present a more formal description of this problem
next and discuss our primary motivation immediately
afterwards. While all our denitions are presented for
general con
ict graphs, our applications, bounds, and
algorithms are for special subclasses { namely, perfect
graphs, interval graphs and circular arc-graphs 1 .
Problem statement An instance of the scheduling
problem consists of a con
ict graph G with n vertices.
The vertices of G are the tasks to be scheduled and
the edges of G dene pairs of tasks that cannot be
scheduled concurrently. The output of the scheduling
algorithm is an innite sequence of subsets of the
vertices, I 1 ; I lists the tasks that are
scheduled at time t. Notice that for all t, I t must be
an independent set of G.
In the form above, it is hard to analyze the running
time of the scheduling algorithm. We consider instead
a nite version of the above problem and use it to
analyze the running time.
Input: A con
ict graph G and a time t.
Output: An independent set I t denoting the set of tasks
scheduled at time unit t.
The objective of the scheduling algorithm is to
achieve a fair allocation and a regular schedule. We
next give some motivation and describe the context
of our work. As we will see, none of the existing
measures can appropriately capture the \goodness"
of a schedule in our framework. Hence we proceed to
introduce measures which allow for easier presentation
of our results.
1 A graph is perfect if for all its induced subgraphs the size of
the maximum clique is equal to the chromatic number (cf. [11]).
A graph is an interval graph (circular-arc graph) if its vertices
correspond to intervals on a line (circle), and two vertices are
adjacent if the corresponding intervals intersect (cf. [20]).
A. Bar-Noy, A. Mayer, B. Schieber, and M. Sudan
1.1 Motivation
Session scheduling in high-speed local-area net-
works. MetaRing ([7]) is a recent high-speed local-area
ring-network that allows \spatial reuse", i.e., concurrent
access and transmission of user sessions, using
only minimal intermediate buering of packets. The
basic operations in MetaRing can be approximated by
the following: if some node has to send data to some
other node a session is established between the source
and the destination. Sessions typically last for a while
and can be active only if they have exclusive use of
all the links in their routes. Hence, sessions whose
routes share at least one link are in con
ict. These
con
icts need to be regulated by breaking the data
sent in a session into units of quotas that are transmitted
according to some schedule. This schedule has
to be e-cient and fair. E-cient means that the total
number of quotas transmitted (throughput) is maximized
whereas fair means that the throughput of each
session is maximized, and that the time between successive
activation of a session is minimized, so that
large buers at the source nodes can be avoided. It
has been recognized ([5]) that the access and
control in such a network should depend on locality in
the con
ict graph. However, no rm theoretical basis
for an algorithmic framework has been proposed
up to now. To express this problem as our scheduling
problem we create a circular-arc graph whose vertices
are the sessions, and in which vertices are adjacent if
the corresponding paths associated with the sessions
intersect in a link.
Time sharing in wireless networks. Most indoor
designs of wireless networks are based on a cellular architecture
with a very small cell size. (See, e.g., [13].)
The cellular architecture comprises two levels { a stationary
level and a mobile level. The stationary level
consists of xed base stations that are interconnected
through a backbone network. The mobile level consists
of mobile units that communicate with the base stations
via wireless links. The geographic area within
which mobile units can communicate with a particular
base station is referred to as a cell. Neighboring
cells overlap with each other, thus ensuring continuity
of communications. The mobile units communicate
among themselves, as well as with the xed information
networks, through the base stations and the back-bone
network. The continuity of communications is a
crucial issue in such networks. A mobile user who
crosses boundaries of cells should be able to continue
its communication via the new base-station. To ensure
this, base-stations periodically need to transmit their
identity using the wireless communication. In some
implementations the wireless links use infra-red waves.
Therefore, two base-station whose cells overlap are in
con
ict and cannot transmit their identity simulta-
neously. These con
icts have to be regulated by a
time-sharing scheme. This time sharing has to be ecient
and fair. E-cient means that the scheme should
accommodate the maximal number of base stations
whereas fair means that the time between two consecutive
transmissions of the same base-station should
be less then the time it takes a user to cross its corresponding
cell. Once again this problem can be posed
as our graph-scheduling problem where the vertices of
the graph are the base-stations and an edge indicates
that the base stations have overlapping cells.
1.2 Relationship to past work
Scheduling problems that only consider either persistence
of the tasks or dependence among the tasks (but
not both) have been dealt with before.
The task of scheduling persistent tasks has been
studied in the work of Baruah et al. [2]. They consider
the problem of scheduling a set of n tasks with given
(arbitrary) frequencies on m machines. (Hence,
yields an instance of our problem where the con
ict
graph is a clique.) To measure \regularity" of a
schedule for their problem they introduce the notion
of P -fairness. A schedule for this problem is P -fair
(proportionate-fair) if at each time t for each task i
the absolute value of the dierence in the number of
times i has been scheduled and f i t is strictly less than
1, where f i is the frequency of task i. They provide
an algorithm for computing a P -fair solution to their
problem. Their problem fails to capture our situation
due to two reasons. First, we would like to constrain
the sets of tasks that can be scheduled concurrently
according to the topology of the con
ict graph and
not according to their cardinality. Moreover, in their
problem every \feasible" frequency requirement can
be scheduled in a P -fair manner. For our scheduling
problem we show that such a P -fair schedule cannot
always be achieved. To deal with feasible frequencies
that cannot be scheduled in a P -fair manner, we dene
weaker versions of \regularity".
The dependency property captures most of the
work done based on the well-known \Dining Philoso-
phers" paradigm, see for example [9], [18], [6], [1], [8],
and [4]. In this setting, Lynch [18] was the rst to explicitly
consider the response time for each task. The
goal of successive works was to make the response time
of a node to depend only on its local neighborhood in
the con
ict graph. (See, e.g., [4].) While response time
in terms of a node's degree is adequate for \one-shot"
tasks, it does not capture our requirement that a task
Guaranteeing Fair Service to Persistent Dependent Tasks 3
should be scheduled in a regular and fair fashion over
a period of time.
1.3 Notations and denitions
A schedule S is an innite sequence of independent
sets I 1 ; I We use the notation S(i; t) to
represent the schedule: S(i;
lim inf t!1 ff (t)
g. We refer to f i as the frequency of
the i-th task in schedule S.
Definition 1.1. A vector of frequencies ^
feasible if there exists a schedule S such
that the frequency of the i-th task under schedule S is
at least f i .
Definition 1.2. A schedule S realizes a vector of
f if the frequency of the i-th task under
schedule S is at least f i . A schedule S c-approximates
a vector of frequencies ^
f if the frequency of the i-th
task under schedule S is at least f i =c.
A measure of fairness Fairness is determined via a
partial order  that we dene on the set of frequency
vectors.
Definition 1.3. Given two frequency vectors ^
f is less fair
there exists an index j and a threshold f
such that f j < f  g j and for all i such that g i  f ,
Definition 1.4. A vector of frequencies ^
f is max-min
fair if no feasible vector ^
g.
Less formally, in a max-min fair frequency vector
one cannot increase the frequency of some task at
the expense of more frequently scheduled tasks. This
means that our goal is to let task i have more of the
resource as long as we have to take the resource away
only from tasks which are better o, i.e., they have
more of the resource than task i.
Measures of regularity Here, we provide two measures
by which one can evaluate a schedule for its reg-
ularity. We call these measures the response time and
the drift.
Given a schedule S, the response time for task i,
denoted r i , is the largest interval of time for which the
i-th task waits between successive schedulings. More
precisely,
For any time t, the number of expected occurrences
of task i can be expressed as f i t. But note that if r i is
larger than 1=f i , it is possible that, for some period of
time, a schedule allows a task to \drift away" from its
expected number of occurrences. In order to capture
this, we introduce a second measure for the regularity
of a schedule. We denote by d i the drift of a task
i. It indicates how much a schedule allows task i to
drift away from its expected number of scheduled units
(based on its frequency):
Note that if a schedule S achieves drift d i < 1 for all
then it is P-fair as dened in [2].
Finally, a schedule achieves its strongest form of
regularity if each task i is scheduled every 1=f i time-units
(except for its rst appearance). Hence we say
that a schedule is rigid if for each task i there exists
a starting point s i such that the task is scheduled on
exactly the time units
1.4 Results
In Section 2 we motivate our denition of max-min
fairness and show several of its properties. First, we
provide an equivalent alternate denition of feasibility
which shows that deciding feasibility of a frequency
vector is computable. We prove that every graph has a
unique max-min fair frequency vector. Then, we show
that the task of even weakly-approximating the max-min
fair frequencies on general graphs is NP-hard.
As we mentioned above many practical applications
of this problem arise from simpler networks, such
as buses and rings (i.e., interval con
ict graphs and
circular-arc con
ict graphs). For the case of perfect-
graphs (and hence for interval graphs), we describe
an e-cient algorithm for computing max-min fair
frequencies. We prove that the period T of a schedule
realizing such frequencies satises and that
there exist interval graphs such that
n) .
The rest of our results deal with the problem of
nding the most \regular" schedule (under the above
mentioned measures) that realizes any feasible frequency
vector. Section 3 shows the existence of interval
graphs for which there is no P -fair schedule
that realizes their max-min fair frequencies. In Section
4 we introduce an algorithm for computing a
schedule that realizes any given feasible frequencies
on interval graphs. The schedule computed by the
algorithm achieves response-time of d4=f i e and drift
of O(
log slight modication of this algorithm
yields a schedule that 2-approximates the given
frequencies. The advantage of this schedule is that
4 A. Bar-Noy, A. Mayer, B. Schieber, and M. Sudan
it achieves a bound of 1 on the drift and hence a
bound of d2=f i e on the response time. In Section 5 we
present an algorithm for computing a schedule that
12-approximates any given feasible frequencies on interval
graphs and has the advantage of being rigid.
All algorithms run in polynomial time. In Section 6
we show how to transform any algorithm for computing
a schedule that c-approximates any given feasible
frequencies on interval graphs into an algorithm
for computing a schedule that 2c-approximates any
given feasible frequencies on circular-arc graphs. (The
response-time and drift of the resulting schedule are
doubled as well.) Finally, in Section 7 we list a number
of open problems and sketch what additional properties
are required to obtain solutions for actual net-
works. Due to space constraints some of the proofs are
either omitted or sketched in this extended summary.
Allocation
Our denition for max-min fair allocation is based
on the denition used by Jae [14] and Bertsekas
and Gallager [3], but diers in one key ingredient
{ namely our notion of feasibility. We study some
elementary properties of our denition in this section.
In particular, we show that the denition guarantees a
unique max-min fair frequency vector for every con
ict
graph. We also show the hardness of computing the
frequency vector for general graphs. However, for the
special case of perfect graphs our notion turns out to
be the same as of [3].
The denition of [14] and [3] is considered the
traditional way to measure throughput fairness and
is also based on the partial order  as used in
our denition. The primary dierence between our
denition and theirs is in the denition of feasibility.
Bertsekas and Gallager [3] use a denition, which we
call clique feasible, that is dened as follows:
A vector of frequencies (f
feasible for a con
ict graph G, if
for all cliques C in the graph G.
The notion of max-min fairness of Bertsekas and
Gallager [3] is now exactly our notion, with feasibility
replaced by clique feasibility.
The denition of [3] is useful for capturing the
notion of fractional allocation of a resource such as
bandwidth in a communication networks. However, in
our application we need to capture a notion of integral
allocation of resources and hence their denition does
not su-ce for our purposes. It is easy to see that every
frequency vector that is feasible in our sense is clique
feasible. However, the converse is not true. Consider
the case where the con
ict graph is the ve-cycle. For
this graph the vector (1=2; 1=2; 1=2; 1=2; 1=2) is clique
feasible, but no schedule can achieve this frequency.
2.1 An alternate denition of feasibility
Given a con
ict graph G, let I denote the family of
all independent sets in G. For I 2 I, let (I) denote
the characteristic vector of I .
Proposition 2.1. A vector of frequencies ^
f is
feasible if and only if there exist weights f I g I2I , such
that
I2I  I
f .
The main impact of this assertion is that it shows
that the space of all feasible frequencies is well behaved
(i.e., it is a closed, connected, compact space).
Immediately it shows that determining whether a frequency
vector is feasible is a computable task (a fact
that may not have been easy to see from the earlier
denition). We now use this denition to see the following
connection:
Proposition 2.2. Given a con
ict graph G, the
notions of feasibility and clique feasibility are equivalent
if and only if G is perfect.
Proof (sketch): The proof is follows directly from well-known
polyhedral properties of perfect graphs. (See
[12], [16].) In the notation of Knuth [16] the space
of all feasible vectors is the polytope STAB(G) and
the space of all clique-feasible vectors is the polytope
QSTAB(G). The result follows from the theorem on
page 38 in [16] which says that a graph G is perfect if
and only if
2.2 Uniqueness and computability of max-min
fair frequencies
In the full paper we prove the following theorem.
Theorem 2.3. There exists a unique max-min fair
frequency vector.
Now, we turn to the issue of the computability
of the max-min fair frequencies. While we do not
know the exact complexity of computing max-min fair
frequencies 2 it does seem to be a very hard task in gen-
eral. In particular, we consider the problem of computing
the smallest frequency assigned to any vertex
by a max-min allocation and show the following:
Theorem 2.4. There exists an  > 0, such that
given a con
ict graph on n vertices approximating the
In particular, we do not know if deciding whether a frequency
vector is feasible is in NP [ coNP
Guaranteeing Fair Service to Persistent Dependent Tasks 5
smallest frequency assigned to any vertex in a max-min
fair allocation, to within a factor of n  , is NP-hard.
Proof (sketch): We relate the computation of max-min
fair frequencies in a general graph to the computation
of the fractional chromatic number of a graph. The
fractional chromatic number problem (cf. [17]) is
dened as follows: To each independent set I in the
graph, assign a weight w I , so as to minimize the
quantity
I w I , subject to the constraint that for
every vertex v in the graph, the quantity
I3v w I is
at least 1. The quantity
I w I is called the fractional
chromatic number of the graph. Observe that if the
w I 's are forced to be integral, then the fractional
chromatic number is the chromatic number of the
graph.
The following claim shows a relationship between
the fractional chromatic number and the assignment
of feasible frequencies.
2.5. Let (f be a feasible assignment
of frequencies to the vertices in a graph G. Then
is an upper bound on the fractional chromatic
number of the graph. Conversely, if k is the
fractional chromatic number of a graph, then a schedule
that sets the frequency of every vertex to be 1=k is
feasible.
The above claim, combined with the hardness of
computing the fractional chromatic number [17], suf-
ces to show the NP-hardness of deciding whether a
given assignment of frequencies is feasible for a given
graph. To show that the claim also implies the hardness
of approximating the smallest frequency in the
max-min fair frequency vector we inspect the Lund-
Yannakakis construction a bit more closely. Their construction
yields a graph in which every vertex participates
in a clique of size k such that deciding if the
(fractional) chromatic number is k or kn  is NP-hard.
In the former case, the max-min fair frequency assignment
is 1=k to every vertex. In the latter case at least
some vertex will have frequency smaller that 1=(kn  ).
Thus this implies that approximating the smallest frequency
in the max-min fair frequencies to within a
factor of n  is NP-hard. 2
2.3 Max-min fair frequencies on perfect
graphs
We now turn to perfect graphs. We show how to compute
in polynomial time max-min fair frequencies for
this class of graphs and give bounds on the period of
a schedule realizing such frequencies. As our main focus
of the subsequent sections will be interval graphs,
we will give our algorithms and bounds rst in terms

Figure

1: An interval graph for which
n) .
of this subclass and then show how to generalize the
results to perfect graphs.
We start by describing an algorithm for computing
max-min fair frequencies on interval graphs. As
we know that clique-feasibility equals feasibility (by
Proposition 2.2), we can use an adaptation of [3]:
Algorithm 1: Let C be the collection of maximal
cliques in the interval graph. (Notice that C has at
most n elements and can be computed in polynomial
time.) For each clique C 2 C the algorithm maintains
a residual capacity which is initially 1. To each vertex
the algorithm associates a label assigned/unassigned.
All vertices are initially unassigned. Dividing the
residual capacity of a clique by the number of unassigned
vertices in this clique yields the relative residual
capacity. Iteratively, we consider the clique with the
smallest current relative residual capacity and assign
to each of the clique's unassigned vertices this capacity
as its frequency. For each such vertex in the clique we
mark it assigned and subtract its frequency from the
residual capacity of every clique that contains it. We
repeat the process till every vertex has been assigned
some frequency.
It is not hard to see that Algorithm 1 correctly
computes max-min fair frequencies in polynomial-
time. We now use its behavior to prove a tight bound
on the period of a schedule for an interval graph. The
following theorem establishes this bound. (See also

Figure

1.)
Theorem 2.6. Let f be the frequencies
in a max-min fair schedule for an interval graph G,
are relatively prime. Then, the period
for the schedule
Furthermore, there exist interval graphs for which T =n) .
6 A. Bar-Noy, A. Mayer, B. Schieber, and M. Sudan
It is clear that Algorithm 1 works for all graphs
where clique feasibility determines feasibility, i.e., perfect
graphs. However, the algorithm does not remain
computationally e-cient. Still, Theorem 2.6 can be
directly extended to the class of perfect graphs. We
now use this fact to describe a polynomial-time algorithm
for assigning max-min fair frequencies to perfect
graphs.
Algorithm 2: This algorithm maintains the labelling
procedure assigned/unassigned of Algorithm 1. At
each phase, the algorithm starts with a set of assigned
frequencies and tries to nd the largest f such that
all unassigned vertices can be assigned the frequency
f . To compute f in polynomial time, the algorithm
uses the fact that deciding if a given set of frequencies
is feasible is reducible to the task of computing the
size of the largest weighted clique in a graph with
weights on vertices. The latter task is well known to
be computable in polynomial-time for perfect graphs.
Using this decision procedure the algorithm performs
a binary search to nd the largest achievable f . (The
binary search does not have to be too rened due
to Theorem 2.6). Having found the largest f , the
algorithm nds a set of vertices which are saturated
under f as follows: Let  be some small number, for
instance
is su-cient. Now it raises, one at a
time, the frequency of each unassigned vertex to f +,
while maintaining the other unassigned frequencies
at f . If the so obtained set of frequencies is not
feasible, then it marks the vertex as assigned and its
frequency is assigned to be f . The algorithm now
repeats the phase until all vertices have been assigned
some frequency.
3 Non-existence of P-fair allocations
Here we show that a P -fair scheduling realizing max-min
fair frequencies need not exist for every interval
graph.
Theorem 3.1. There exist interval graphs G for
which there is no P-fair schedule that realizes their
max-min frequency assignment.
In order to prove this theorem we construct such
a graph G as follows. We choose a parameter k and
for every permutation  of the elements
dene an interval graph G  . We show a necessary condition
that  must satisfy if G  has a P-fair schedule.
Lastly we show that there exists a permutation  of
12 elements which does not satisfy this condition.
Given a permutation  on k elements, G  consists
of 3k intervals. For the

Figure

2: The graph G  for
that the max-min
frequency assignment to G  is the following: All the
tasks B(i) have frequency 1=k; all the tasks A(i) have
frequency all the tasks C(i) have
frequency i=k. (See Figure 2.)
We now observe the properties of a P-fair schedule
for the tasks in G  . (i) The time period is k. (ii)
The schedule is entirely specied by the schedule for
the tasks B(i). (iii) This schedule is a permutation
of k elements, where (i) is the time unit for which
B(i) is scheduled. To see what kind of permutations
constitute P-fair schedules of G  we dene the notion
of when a permutation is fair for another permutation.
Definition 3.1. A permutation  1 is fair for a
permutation  2 if for all
the conditions cond ij dened as follows:
3.2. If a permutation  is a P-fair schedule
for G  then  is fair for the identity permutation and
for permutation .
be a permutation
on 12 elements. In the full paper we show that
no permutation  is fair to both  and the identity.
Realizing frequencies exactly
In this section we rst show how to construct a
schedule that realizes any feasible set of frequencies
(and hence in particular max-min frequencies) exactly
on an interval graph. We prove its correctness and
demonstrate a bound of d4=f i e on the response time
for each interval i. We then proceed to introduce
a potential function that is used to yield a bound
of O(n 1+ ) on the drift for every interval. We also
prove that if the feasible frequencies are of the form
then the drift of the schedule can be bounded
by 1 and thus the waiting time can be bounded by
We use this property to give an algorithm for
Guaranteeing Fair Service to Persistent Dependent Tasks 7
computing a schedule that 2-approximates any feasible
set of frequencies with high regularity.
Input to the Algorithm: A unit of time t and a con
ict
graph G which is an interval graph. Equivalently, a set
of intervals on the unit interval [0; 1]
of the x-coordinate, where I
Every interval I i has a frequency f with the
following constraint:
I
For simplicity, we assume from now on that these
constraints on the frequencies are met with equality
and that t  g.
Output of the Algorithm: An independent set I t which
is the set of tasks scheduled for time t such that the
scheduled S, given by fI t g T
realizes frequencies f i .
The algorithm is recursive. Let s i denote the
number of times a task i has to appear in T time
units, i.e., s . The algorithm has log T levels
of recursion. (Recall that log T is O(n) for max-min
fair frequencies.) In the rst level we decide on the
occurrences of the tasks in each half of the period.
That is, for each task we decide how many of its
occurrences appear in the rst half of the period and
how many in the second half. This yields a problem
of a recursive nature in the two halves. In order to
nd the schedule at time t, it su-ces to solve the
problem recursively in the half which contains t. (Note
that in case T is odd one of the halves is longer than
the other.) Clearly, if a task has an even number of
occurrences in T it would appear the same number of
times in each half in order to minimize the drift. The
problem is with tasks that have an odd number of
occurrences s i . Clearly, each half should have at least
bs i c of the occurrences. The additional occurrence
has to be assigned to a half in such a way that both
resulting sub-problems would still be feasible. This is
the main di-culty of the assignment and is solved in
the procedure Sweep.
Procedure Sweep: In this procedure we compute
the assignment of the additional occurrence for all
tasks that have an odd number of occurrences. The
input to this procedure is a set of intervals I
(with odd s i 's) with the restriction that each clique in
the resulting interval graph is of even size. (Later, we
show how to overcome this restriction.) The output
is a partition of these intervals into two sets such
that each clique is equally divided among the sets.
This is done by a sweep along the x-coordinate of
the intervals. During the sweep every interval will
be assigned a variable which at the end is set to 0
or 1 (i.e., rst half of the period or second half of the
period). Suppose that we sweep point x. We say that
an interval I i is active while we sweep point x if x 2 I i .
The assignment rules are as follows.
For each interval I i that starts at x:
If the current number of active intervals is even:
A new variable is assigned to I i (I i is unpaired).
If the current number of active intervals is odd:
I i is paired to the currently unpaired interval I j
and it is assigned the negation of I j 's variable.
Thus no matter what value is later assigned to this
variable, I i and I j will end up in opposite halves.
For each interval I i that ends at x:
If the current number of active intervals is even:
Nothing is done.
If the current number of active intervals is odd:
If I i is paired with I
I j is now being paired with the currently unpaired
interval I k . Also, I j 's variable is matched
with the negation of I k 's variable. This will ensure
that I j and I k are put in opposite halves,
or equivalently, I i and I k are put in the same
halves.
If I i is unpaired:
Assign arbitrarily 0 or 1 to I i 's variable.
These operations ensure that whenever the number
of active intervals is even, then exactly half of the
intervals will be assigned 0 and half will be assigned
this will be proven later.
Recall that we assumed that the size of each clique
is even. Let us show how to overcome this restriction.
For this we need the following simple lemma. For
by C x the set of all the input intervals
(with odd and even s i 's) that contain x; C x will be
referred to as a clique.
Lemma 4.1. The period T is even if and only if
is oddgj is even for every clique C.
This lemma implies that if T is even then the size of
each clique in the input to procedure Sweep is indeed
even. If T is odd, then a dummy interval I n+1 which
extends over all other intervals and which has exactly
one occurrence is added to the set I before calling
Sweep. Again, by Lemma 4.1, we are sure that in
this modied set I the size of all cliques is even. This
would increase the period by one. The additional time
unit will be allotted only to the dummy interval and
thus can be ignored. We note that to produce the
schedule at time t we just have to follow the recursive
calls that include t in their period. Since there are
no more than log T such calls, the time it takes to
produce this schedule is polynomial in n for max-min
fair frequencies.
8 A. Bar-Noy, A. Mayer, B. Schieber, and M. Sudan
Lemma 4.2. The algorithm produces a correct
schedule for every feasible set of frequencies.
Lemma 4.3. If the set of frequencies is of the form
then the drift can be bounded by 1 and hence the
response time can be bounded by d2=f i e.
Proof: Since our algorithm always divides even s i into
equal halves, the following invariant is maintained: At
any recursive level, whenever s i > 1, then s i is even.
Also note that thus
we can express each f i as 2 i k . Now, following the
algorithm, it can be easily shown that there is at least
one occurrence of task i in each time interval of size
Hence
c and P -fairness
Lemma 4.4. The response time for every interval
I i is bounded by d4=f i e.
Proof: The proof is based on the Lemma 4.3. This
lemma clearly implies the case in which the frequencies
are powers of two. Moreover, in case the frequencies
are not powers of two, we can virtually partition
each task into two tasks with frequencies p i and r i
respectively, so that f a power of
two, and r i < p i . Then, the schedule of the task with
frequency p i has drift 1. This implies that its response
time is d2=p i e  d4=f i e. 2
We remark that it can be shown that the bound of
the above lemma is tight for our algorithm.
We summarize the results in this section in the
following theorem:
Theorem 4.5. Given an arbitrary interval graph
as con
ict graph, the algorithm exactly realizes any
feasible frequency-vector and guarantees that r i
4.1 Bounding the drift
Since the algorithm has O(log T ) levels of recursion
and each level may increase the drift by one, clearly
the maximum drift is bounded by O(log T ). In this
section we prove that we can decrease the maximum
drift to be O(
log xed , where n is the
number of tasks. By Theorem 2.6 this implies that in
the worst case the drift for a max-min fair frequencies
is bounded by O(n 1+ ).
Our method to get a better drift is based on the
following observation: At each recursive step of the
algorithm two sets of tasks are produced such that
each set has to be placed in a dierent half of the
time-interval currently considered. However, we are
free to choose which set goes to which half. We are
using this degree of freedom to decrease the drift. To
make the presentation clearer we assume that T is a
power of two and that the time units are
Consider a sub-interval of size T=2 j starting after
time and ending at t
for 1. In the rst j recursion levels we
already xed the number of occurrences of each task
up to t ' . Given this number, the drift d ' at time t ' is
xed. Similarly, the drift d r at time t r is also xed.
At the next recursion level we split the occurrences
assigned to the interval thus xing
the drift dm at time t Optimally,
we would like the drifts after the next recursion level
at each time unit to be the weighted
average of the drifts d ' and d r . In other words, let
would like the drift
at time t to be d r In particular, we
would like the drift at t m to be (d ' This drift
can be achieved for t m only if the occurrences in the
interval can be split equally. However, in
case we have an odd number of occurrences to split,
the drift at t m is (d ' depending on
our decision in which half interval to put the extra
occurrence. Note that the weighted average of the
drifts of all other points changes accordingly. That
is, if the new dm is (d '
then the weighted average in t 2
d r +(1 )d ' +2x, where
and the weighted average in t 2 [(t r
d r +(1 )d ' +(2 2)x, where
1=2.
Consider now the two sets of tasks S 1 and S 2 that
we have to assign to the two sub-intervals (of the
same size) at level k of the recursion. For each of the
possible two assignments, we compute a \potential"
based on the resulting drifts at time t m . For a given
possibility let D[tm ; i; k] denote the resulting drift of
the i-th task at t m after k recursion levels. Dene
the potential of t m after k levels as
xed even constant . We
choose the possibility with the lowest potential.
Theorem 4.6. Using the policy described above
the maximum drift is bounded by O(
log T  n  ), for
any xed .
Realizing frequencies rigidly
In this section we show how to construct a schedule
that 12-approximates any feasible frequency-vector in
a rigid fashion on an interval graph. We reduce
our Rigid Schedule problem to the Dynamic Storage
Allocation problem. The Dynamic Storage Allocation
Guaranteeing Fair Service to Persistent Dependent Tasks 9
problem is dened as follows. We are given objects to
be stored in a computer memory. Each object has
two parameters: (i) its size in terms of number of
cells needed to store it, (ii) the time interval in which
it should be stored. Each object must be stored in
adjacent cells. The problem is to nd the minimal
size memory that can accommodate at any given time
all of the objects that are needed to be stored at that
time. The Dynamic Storage Allocation problem is a
special case of the multi-coloring problem on intervals
graphs which we now dene.
A multi-coloring of a weighted graph G with the
weight function
such that for all v 2 V the size of F (v) is w(v), and
such that if (v; u) 2 E then F (v) \ F ;. The
multi-coloring problem is to nd a multi-coloring with
minimal number of colors. This problem is known to
be an NP-Hard problem [10].
Two interesting special cases of the Multi-Coloring
problem are when the colors of a vertex either must
be adjacent or must be \spread well" among all colors.
We call the rst case the AMC problem and the second
case the CMC problem. More formally, in a solution
to AMC if F
for all 1  i < k. Whereas in a solution to CMC which
uses T colors, if F
divides T , and (ii) x
and
It is not hard to verify that for interval graphs the
AMC problem is equivalent to the Dynamic Storage
Allocation problem described above. Simply associate
each object with a vertex in the graph and give it a
weight equal to the number of cells it requires. Put an
edge between two vertices if their time intervals inter-
sect. The colors assigned to a vertex are interpreted
as the cells in which the object is stored.
On the other hand, the CMC problem corresponds
to the Rigid Schedule problem as follows. First, we
replace the frequency f(v) by a weight w(v). Let
Now, assume that the output for the CMC problem
uses T colors and let the colors of v be fx 1 <    < x k g
We interpret this as follows: v
is scheduled in times x It is not
di-cult to verify that this is indeed a solution to the
Rigid Scheduling problem.
Although Dynamic Storage Allocation problem is
a special case of the multi-coloring problem it is
still known to be an NP-Hard problem [10] and
for similar reasons the Rigid Scheduling problem is
also NP-Hard. Therefore, we are looking for an
approximation algorithm. In what follows we present
an approximation algorithm that produces a rigid
scheduling that 12-approximates the given frequencies.
For this we consider instances of the AMC and CMC
problems in which the input weights are powers of two.
Definition 5.1. A solution for an instance of
AMC is both aligned and contiguous if for all
In [15], Kierstead presents an algorithm for AMC
that has an approximation factor 3. A careful inspection
of this algorithm shows that it produces solutions
that are both aligned and contiguous for all instances
in which the weights are power of two.
We show how to translate a solution for such an
instance of the AMC problem that is both aligned and
contiguous into a solution for an instance of the CMC
problem with the same input weights.
For be the k-bit number whose
binary representation is the inverse of the binary
representation of x.
Lemma 5.1. For
1)g.
Consider an instance of the CMC problem in which
all the input weights are powers of two. Apply the
solution of Kierstead [15] to solve the AMC instance
with the same input. This solution is both aligned and
contiguous, and uses at most 3T 0 colors where T 0 is the
number of colors needed by an optimal coloring. Let
be the smallest power of 2 that is greater
than T 0 . It follows that T  6T 0 . Applying the
transformation of Lemma 5.1 on the output of the
solution to AMC yields a solution to CMC with at
most T colors. This in turn, yields an approximation
factor of at most 12 for the Rigid Scheduling problem,
since w(v)=T  f(v)=2.
Theorem 5.2. The above algorithm computes a
rigid schedule that 12-approximates any feasible
frequency-vector on an interval graph.
6 Circular-Arc graphs
In this section we show how to transform any algorithm
A for computing a schedule that c-approximates
any given feasible frequency-vector on interval graphs
into an algorithm A 0 for computing a schedule that
2c-approximates any given feasible frequencies on
circular-arc graphs.
A. Bar-Noy, A. Mayer, B. Schieber, and M. Sudan
f be a feasible frequency-vector on a circular-arc
graph G.
1: Find the maximum clique C in G.
is an interval graph.
2 be the frequency-vectors resulting from
restricting
f to the vertices of G 0 and C, respectively.
Note that ^
are feasible on G 0 and C, respectively

Step 2: Using A, nd schedules S 1 and S 2 that c-
g 2 on G 0 and C, respectively.
Step 3: Interleave S 1 and S 2 .
Clearly, the resulting schedule 2c-approximates ^
f
on the circular-arc graph G.
7 Future research
Many open problems remain. The exact complexity
of computing a max-min fair frequency assignment in
general graphs is not known and there is no characterization
of when such an assignment is easy to compute.
All the scheduling algorithms in the paper use the inherent
linearity of interval or circular-arc graphs. It
would be interesting to nd scheduling algorithms for
the wider class of perfect graphs. The algorithm for interval
graphs that realizes frequencies exactly exhibits
a considerable gap in its drift. It is not clear from
which direction this gap can be closed.
Our algorithms assume a central scheduler that
makes all the decisions. Both from theoretical and
practical point of view it is important to design
scheduling algorithms working in more realistic environments
such as high-speed local-area networks and
wireless networks (as mentioned in Section 1.1). The
distinguishing requirements in such an environment
include a distributed implementation via a local signaling
scheme, a con
ict graph which may change with
time, and restrictions on space per node and size of a
signal. The performance measures and general setting,
however, remain the same. A rst step towards such
algorithms has been recently carried out by Mayer,
Ofek and Yung in [19].

Acknowledgment

. We would like to thank Don
Coppersmith and Moti Yung for many useful discussions



--R

A Dining Philosophers Algorithm with Polynomial Response Time.
A Notion of Fairness in Resource Allocation.
Data Networks.
Distributed Resource Allocation Algorithms.
A Local Fairness Algorithm for Gigabit LANs/MANs with Spatial Reuse.
The Drinking Philosophers Problem.


Hierarchical Ordering of Sequential Processes.
Computers and Intractability
Algorithmic Graph Theory and Perfect Graphs.

Cellular Packet Communica- tions
Bottleneck Flow Control.
A Polynomial Time Approximation Algorithm for Dynamic Storage Allocation.
The Sandwich Theorem
On the Hardness of Approximating Minimization Problems.
Fast Allocation of Nearby Resources in a Distributed System.
Distributed Scheduling Algorithm for Fairness with Minimum Delay.
Matrix characterizations of circular-arc graphs
--TR

--CTR
Sanjoy K. Baruah , Shun-Shii Lin, Pfair Scheduling of Generalized Pinwheel Task Systems, IEEE Transactions on Computers, v.47 n.7, p.812-816, July 1998
Francesco Lo Presti, Joint congestion control: routing and media access control optimization via dual decomposition for ad hoc wireless networks, Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 10-13, 2005, Montral, Quebec, Canada
Sandy Irani , Vitus Leung, Scheduling with conflicts on bipartite and interval graphs, Journal of Scheduling, v.6 n.3, p.287-307, May/June
Ami Litman , Shiri Moran-Schein, On distributed smooth scheduling, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
Tracy Kimbrel , Baruch Schieber , Maxim Sviridenko, Minimizing migrations in fair multiprocessor scheduling of persistent tasks, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Tracy Kimbrel , Baruch Schieber , Maxim Sviridenko, Minimizing migrations in fair multiprocessor scheduling of persistent tasks, Journal of Scheduling, v.9 n.4, p.365-379, August    2006
Violeta Gambiroza , Edward W. Knightly, Congestion control in CSMA-based networks with inconsistent channel state, Proceedings of the 2nd annual international workshop on Wireless internet, p.8-es, August 02-05, 2006, Boston, Massachusetts
dining philosophers problem;fairness;interval graphs;scheduling