A CONSTANT FACTOR APPROXIMATION ALGORITHM FOR
UNSPLITTABLE FLOW ON PATHS
PAUL BONSMA*, JENS SCHULZ**, AND ANDREAS WIESE**
Abstract. We study the unsplittable flow problem on a path
P
. We are
given a set of
n
tasks. Each task is specified by a sub path of
P
, a demand,
and a profit. Moreover, each edge of
P
has a given capacity. The aim is to find
a subset of the tasks with maximum profit, for which the given demands can be
simultaneously routed along
P
, subject to the capacities. The best known poly-
nomial time approximation algorithm for this problem achieves a performance
ratio of
O
(log
n
)
and the best known hardness result is weak NP-hardness. In
this paper, we firstly show that the problem is strongly NP-hard, even when the
capacities are constant, and all demands are chosen from
f
1
;
2
;
3
g
. Secondly,
we present the first polynomial time constant-factor approximation algorithm
for this problem, achieving an approximation factor of
7 +
for any
>
0
.
This answers an open question from Bansal et al. (SODA’09). We employ a
novel framework which reduces the problem to instances where the capacities
of the edges differ by at most a constant factor. Moreover, for the difficult
“large” tasks – for which in particular the straightforward linear program has
an integrality gap of
(
n
)
– we present a new geometrically inspired dynamic
program.
Our techniques yields several other results which are of independent inter-
est: for any
>
0
and
>
0
, we give an
(3 +
)
-approximation algorithm for
the case that each task uses at most a
(1
)
-fraction of the capacities of its
edges. Furthermore, we give a
(2 +
)
-approximation algorithm that violates
the capacities by at most a factor
(1+
)
(resource augmentation). Finally, we
show that already a running time of
O
(
n
4
log
n
)
suffices to obtain a constant
factor approximation algorithm for the general case.
1. Introduction
In the Unsplittable Flow Problem on a Path (UFPP), we are given a path
P
=
(
V;E
)
with a capacity
u
e
for each edge
e
2
E
. In addition, we are given a set of
n
tasks
T
where each task
i
2
T
is characterized by a start vertex
s
i
2
V
, an end
vertex
t
i
2
V
, a demand
d
i
2
N
, and a profit
w
i
2
N
. The aim is to compute a set
of tasks
F
T
with maximum total profit
P
i
2
F
w
i
such that for each edge, the
demand sum of the tasks in
F
using this edge does not exceed its capacity.
Date: February 17, 2011.
*Humboldt Universität zu Berlin, Computer Science Department, Unter den Linden 6, 10099
Berlin. [email protected].
**Technische Universität Berlin, Institute of Mathematics, Straße des 17. Juni 136, 10623
Berlin. {jschulz,wiese}@math.tu-berlin.de.
The first author was supported by DFG grant BO 3391/1-1. The second author was supported
by the DFG Research Center Matheon Mathematics for key technologies in Berlin. The third
authors was supported by DFG project “Algorithm Engineering for Real-time Scheduling and
Routing” within DFG focus program 1307.
1
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 2
The name of this problem is motivated by an interpretation as a multicommodity
flow problem, where each task corresponds to a commodity. The term “unsplittable”
means that the total amount of flow
d
i
from each commodity
i
has to flow com-
pletely along the path from the source
s
i
to the sink
t
i
or not at all. There are
several settings and applications in which this problem occurs, and several other
interpretations of the problem. Therefore, this problem, and close variants thereof,
have also been studied under the names bandwidth allocation,resource contrained
scheduling,call admission control,temporal knapsack,maximum demand flow, and
resource allocation. In many applications, the vertices correspond to time points,
and tasks have fixed start and end times. Within this time interval they consume a
given amount of a common resource, of which the available amount varies over time.
For instance, this occurs when scheduling tasks in a uniform machine environment
with possible down-times for each machine. Jobs have fixed start and end times,
may migrate to different machines, and require a certain number
d
i
of machines
when selected.
This problem is known to be weakly NP-hard, since it contains the Knapsack
problem as a special case (the case where there is just a single edge). In addition,
Darmann et al. [13] recently showed that the special case where all profits and
all capacities are uniform remains weakly NP-hard. This implies that the problem
admits no Fully Polynomial Time Approximation Scheme (FPTAS) unless
P
=
NP
,
but does not exclude pseudopolynomial time algorithms. While the special case of a
single edge admits an FPTAS, no constant-factor approximation algorithm is known
for UFPP. The best known polynomial time algorithm achieves an approximation
factor of
O
(log
n
)
[4]. In addition, there is a
(1 +
)
-approximation algorithm
known with quasi-polynomial running time which additionally requires that the
capacities and the demands are quasi-polynomial, i.e. bounded by
2
polylog
n
[3].
One special case which has been intensively studied is given by the no-bottleneck-
assumption [8, 9, 12, 11], where it is required that
max
i
d
i
min
e
u
e
holds. For
this case there is a
(2+
)
-approximation algorithm known [11]. However, it turned
out that there are several obstacles that prevent these algorithms to be generalized
to the general case, see e.g. [9] and the discussion below.
In conclusion, even though the UFPP has been intensively studied, in terms of
polynomial time approximation algorithms for the general case, the best known
algorithm is a
O
(log
n
)-approximation algorithm [4], and the best negative result
is that there cannot be an FPTAS (unless
P
=
NP
) [13]. It is not known whether
the problem can be solved optimally with a pseudopolynomial time algorithm.
1.1. Our Contribution. In this paper we significantly diminish the gap between
positive and negative results for UFPP: First, we present the first polynomial time
constant-factor approximation for the general case. Secondly, we prove that the
problem is strongly NP-hard even for the restricted case where all demands are
chosen from
f
1
;
2
;
3
g
and capacities are uniform. Note that in this case even the no-
bottleneck-assumption holds. The result implies that unless
P
=
NP
, the problem
admits no pseudopolynomial time algorithm, and it yields a different proof that
there can be no FPTAS (see e.g. [28]).
Our main algorithmic result is a
(7+
)
-approximation algorithm for the UFPP,
for every
>
0
. For practical purposes, we also provide a constant factor approx-
imation algorithm with a reasonable running time of only
O
(
n
4
log
n
)
. Along the
way, our techniques yield several algorithmic results which are interesting in their
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 3
own right: For a task
i
, denote by
b
(
i
)
the minimum capacity among all edges used
by task
i
, and call the ratio
d
i
=b
(
i
)
its relative demand. For every
>
0
and
>
0
,
if for every task its relative demand is at most
1
, then we obtain a
(3 +
)
-
approximation algorithm. For the setting of resource augmentation, we show how
to compute a
(2 +
)
-approximative solution that is feasible when the capacities
are incremented by only a modest factor of
1+
. Finally, we present a polynomial
time algorithm for finding maximum weight independent sets in certain types of
rectangle intersection graphs.
We now go into more detail about the new techniques we introduce, and give
an outline of the paper. Similar to many previous papers, for our main algorithm
we partition the tasks into groups, depending on their relative demand. We use
three groups, called the small,medium and large tasks. In Section 2 we define this
precisely. In Section 3 we introduce a novel framework to handle the small and
medium tasks. Here these tasks are first partitioned into smaller sets, which can be
solved via dynamic programming, LP-rounding and network flow techniques. (This
is similar to many previous papers, such as [8].) Solutions to these smaller sets
leave a small amount of the capacity of each edge unused. This allows to recombine
these sets, yielding a
(3 +
)
-approximation for all small and medium tasks (i.e.
tasks with relative demand at most
1
). If we do not leave a small amount of
the capacity unused, we obtain a
(2 +
)
-approximative solution for all tasks this
way (i.e., small, medium, and large), at the cost of violating the capacities by at
most a factor of
1 +
.
The remaining large tasks (those with relative demand larger than
(1
)
) are
treated in Section 4. For those, we present a polynomial time 4-approximation
algorithm. We interpret UFPP instances geometrically, by drawing a curve in the
plane determined by the capacities, and representing tasks by axis-parallel rect-
angles, that are drawn as high as possible under this curve. The demand of a
task determines the height of the rectangle. Using a novel geometrically inspired
dynamic program, we show that in polynomial time, a maximum weight set of pair-
wise non-intersecting rectangles can be found. Such a set corresponds to a feasible
UFPP solution. In addition, we show that when for every task the relative demand
is at least
1
=k
, a maximum weight set of pairwise non-intersecting rectangles yields
a
2
k
-approximative solution for UFPP .
Section 5 finally combines the results of Sections 3 and 4 to our
(7+
)
-approximation
algorithm. In addition, we obtain an algorithm with only a running time of
O
(
n
4
log
n
)
which still achieves a (constant) approximation ratio of
25
:
12
. In Section 6, we
present our strong NP-hardness proof. In Section 7 we conclude with a discussion.
1.2. Background and Related Work. UFPP has been studied from different
perspectives, and many special cases under various assumptions were considered. In
the following, we will give an overview of the main results. As mentioned above, the
UFPP is weakly NP-hard due to the contained Knapsack problem. In fact, UFPP
is a special case of Multi-Dimensional Knapsack, which is obtained by allowing
the tasks to have different demands for every edge. Therefore, if the number of
edges
m
is constant, the problem admits a PTAS, see [17]. If all edge capacities are
bounded by a constant
C
, then a straightforward dynamic programming algorithm
solves the problem in polynomial time
n
O
(
C
)
(recall that all demands are integers).
The special case of UFPP in which all capacities are equal has received a lot of
study, and is often called the Resource Allocation Problem (RAP). If all demands
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 4
are
1
, the RAP can be solved in time
O
(
n
2
log
n
)
by minimum-cost flow computa-
tions since the coefficient matrix corresponds to a network flow matrix, as shown
by Arkin and Silverberg [2]. RAP admits a straightforward 0/1 integer linear pro-
gramming formulation. Calinescu et al. [8] mention how its LP relaxation can be
solved similarly in time
O
(
n
2
log
2
n
)
, using a minimum cost flow algorithm [25]
(even with arbitrary demands).
We mentioned before that for the special case of UFPP where the no-bottleneck
assumption holds (i.e.
max
i
d
i
min
e
u
e
), a
(2 +
)
-approximation algorithm has
been given by Chekuri et al. [11]. Note that the no-bottleneck assumption holds
in particular for RAP. Before this, a
(2+
)
-approximation algorithm for RAP was
given by Calinescu et al. [8]. Although Darmann et al. [13] rule out the existance
of an FPTAS for RAP (unless
P
=
NP
), it remains open whether there exists a
PTAS.
Phillips et al [27] obtain a
6
-approximation algorithm for RAP by using LP-
rounding techniques. They consider a more general version of the problem in which
the start and end times are not fixed, so the tasks are allowed to slide in their
time window
[
s
i
;t
i
)
. A similar generalization, where for each task one out of a set
of alternatives needs to be selected, Bar-Noy et al. [5] provide a constant factor
approximation algorithm using the local ratio technique.
The Unsplittable Flow Problem (UFP) has also been considered for other graph
classes than just paths. In general graphs, for every task selected in a solution one
additionally needs to select a path from
s
i
to
t
i
. Many results for UFP again use
the no-bottleneck assumption. Chakrabarti et al [9] give the first constant factor
approximation for UFP on a path or cycle under this assumption, with a factor
of
78
:
51
. For the cycle, they reduce the problem to two UFP problems on a path,
by splitting the cycle at a special edge. Chekuri et al. [11] improve this result for
UFP to
(2+
)
. In addition, they give constant factor approximation algorithms for
UFP on trees. UFP on general graphs has been studied by Chakrabarti et al. [9],
who give non-constant factor approximation in this setting.
Recall that for our main algorithm, we develop a polynomial time algorithm to
find a maximum weight set of pairwise non-intersecting rectangles, for sets of rect-
angles drawn as high as possible under a certain curve. This is closely related to
the Maximum Independent Set of Rectangles (MISR) problem, studied by
Chalermsook and Chuzhoy [10]. In this problem, a collection of
n
axis-parallel rect-
angles is given and the task is to find a maximum-cardinality subset of disjoint rect-
angles. They provide a randomized
O
(loglog
n
)
-approximation. For the weighted
case, there are several
O
(log
n
)
-approximation algorithms known [1, 20, 24]. For
geometric intersection graphs of disks, squares and similar objects, Erlebach, Jansen
and Seidel [16] give polynomial time approximation schemes for the Maximum
Weight Independent Set and the Minimum Weight Vertex Cover prob-
lem. Unfortunately, their approach does not carry over to rectangles if the ratio
between their height and width can be arbitrary.
The MISR problem is related to adjacent resource scheduling problems. In such
problems, one wants to schedule a job on several machines in parallel which must be
contiguous, i.e., adjacent to each other. Duin and van Sluis [14] prove the decision
variant of scheduling tasks on contiguous machines to be strongly NP-complete.
RAP on contiguous machines has been considered under the name storage allocation
problem (SAP), in which tasks are axis-aligned rectangles that are only allowed to
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 5
move vertically. Leonardi et al. [22] provide a
12
-approximation algorithm for SAP.
Bar-Yehuda et al. [6] present a deterministic polynomial-time
(2 +
+ 1
=
(
e
1))
-
approximation algorithm based on the local ratio technique. This result also holds
for RAP.
In this paper, we also study the UFPP problem in the setting of resource aug-
mentation. This means that we find a solution which is feasible if we increase the
capacity of each edge by a modest factor of
(1 +
)
. The paradigm of resource
augmentation is very popular in real-time scheduling. There, the augmented re-
source is the speed of the machines. For instance, it is known that the natural
earliest deadline first policy (EDF) is guaranteed to work on
m
machines with
speed
2
1
=m
if the instance can be feasibly scheduled on
m
machines with unit
speed [26]. Also, a matching feasibility test is known [7]. For further examples of
resource augmentation results in real-time scheduling see [15, 21].
1.3. Applications. We want to add a further interesting application where UFPP
occurs. In constraint programming throughout branch-and-bound search, infea-
sible subproblems occur that are analyzed in order to create new globally valid
constraints or to use non-chronological backtracking. To make these constraints as
reusable as possible one searches for minimum size explanations that are responsi-
ble for the infeasibility. In case of the cumulative constraint that models scheduling
problems, see e.g. [19], one needs to report a minimum set of jobs such that an
interval
[
a;b
)
is overloaded at each point in time. Each job has a demand
d
j
2
N
and a core
[
s
j
;t
j
)
when it must be scheduled under a capacity
C
2
N
. Using
binary variables
x
j
that model whether a job is picked or not, we need to solve
the following integer program
min
f
P
j
x
j
j
P
j
d
j
x
j
C
8
t
g
. Let
U
t
denote the
sum of all demands at time
t
, i.e.,
U
t
=
P
j
:
t
2
[
s
j
;t
j
)
d
j
. Then, the integer program
can be stated as
max
f
P
j
x
j
j
P
j
d
j
x
j
U
t
C
8
t
g
, which is exactly the UFPP
formulation with uniform profits. Arbitrary profits are introduced when the lower
and upper bounds of the variables shall be taken into account.
1.4. Discussion of the No-Bottleneck Assumption. The no-bottleneck as-
sumption requires that no demand is larger than the minimum capacity, i. e.
max
i
d
i
min
e
u
e
holds. This is a strict assumption since it removes certain complications
which are not easy to handle. For example, it was shown by Chakrabarti et al. [9]
that if the no-bottleneck assumption holds, the natural LP-relaxation of the prob-
lem has a constant integrality gap. However, without this assumption the integrality
gap can be as large as
(
n
)
. Consider the following example adapted from [4]: the
capacites of each edge
e
=
f
k;k
+ 1
g
;k
= 0
;:::;m
1
, are given by
u
e
= 2
m
k
and for each
i
= 1
;:::;m
there is a task
i
with
s
i
= 0
,
t
i
=
i
,
d
i
= 2
m
i
+1
, and
unit profit. Observe that this instance does not obey the no-bottleneck assumption.
Any integral solution can choose at most one task, but the natural LP relaxation
achieves a profit of
n=
2
. Moreover, the no-bottleneck assumption implies that if all
tasks have relative demand at least
, in any solution there can be at most
2
1
=
2
tasks
i
which use a given edge
e
, see [9]. This property is useful for setting up
a dynamic program. However, a simple modification of the above instance shows
that without the no-bottleneck assumption this no longer holds; when doubling all
capacities, all tasks have relative demand
1
=
2
, yet an optimal solution contains all
tasks. These are the main obstacles that need to be overcome in order to give a
constant factor approximation algorithm for the general case of UFPP.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 6
2. Preliminaries
In this section, we introduce some notation and terminology, and define precisely
how we partition the tasks into small, medium, and large tasks.
We assume that the vertices of the path
P
= (
V;E
)
are numbered
V
=
f
0
;:::;m
g
,
and
E
=
ff
i;i
+ 1
g j
0
i
m
1
g
. We assume that the tasks are numbered
T
=
f
1
;:::;n
g
. Recall that tasks are characterized by two vertices
s
i
and
t
i
with
s
i
< t
i
, and positive integer demand
d
i
and profit
w
i
. For each task
i
2
T
we denote
by
P
i
E
the edge set of the subpath of
P
from
s
i
to
t
i
. If
e
2
P
i
, then task
i
is
said to use
e
. For each edge
e
we denote by
T
e
T
the set of tasks which use
e
. A
set of tasks
F
T
is said to obey the capacities of the edges if
P
i
2
F
\
T
e
d
i
u
e
for
each edge
e
. For a set of tasks
F
we define its profit by
w
(
F
) :=
P
i
2
F
w
i
. Hence,
formally our objective is to find a set of tasks
F
with maximum profit which obeys
the capacities of the edges.
For each task
i
we define its bottleneck capacity
b
(
i
)
by
b
(
i
) := min
e
2
P
i
u
e
. An
edge
e
is called a bottleneck edge for the task
i
if
e
2
P
i
and
u
e
=
b
(
i
)
. In addition,
we define for every task
i
that
`
(
i
) :=
b
(
i
)
d
i
. The value
`
(
i
)
can be interpreted
as the remaining capacity of a bottleneck edge of
i
when
i
is selected in a solution.
Consider a vertex
v
2
V
and an edge
e
2
E
with
e
=
f
x;x
+ 1
g
. We write
v < e
(or
v > e
) if
v
x
(resp.
v
x
+ 1
). For two edges
e
=
f
x;x
+ 1
g
and
e
0
=
f
x
0
;x
0
+1
g
in
E
, we write
e<e
0
if
x<x
0
and
e
e
0
if
x
x
0
. In other words,
we interpret an edge
f
x;x
+ 1
g
simply as a number between
x
and
x
+ 1
. If
e<e
0
then we will also say that
e
lies before
e
0
, and
e
0
lies after
e
. If
e
=
f
x
1
;x
g
and
e
0
=
f
x;x
+ 1
g
then
e
lies immediately before
e
0
.
Without loss of generality, we will assume throughout this paper that
u
e
1
for
all edges
e
and
d
i
1
for all tasks
i
; zero demands and capacities can easily be
handled in a preprocessing step. Moreover, observe that one can easily adjust any
given instance to an equivalent instance in which each vertex is either a start or an
end vertex of a task. Such an adjustment can be implemented in linear time and
it hence does not dominate the running times of the algorithms presented in this
paper. Therefore, we will henceforth assume that
m <
2
n
.
We define an
-approximation algorithm for a maximization problem to be an
algorithm which computes a feasible solution for a given instance such that its
objective value is at least
1
times the optimal value. Unless otherwise stated,
we always assume that an approximation algorithm has polynomial running time.
Throughout, for a subset of the tasks
F
T
,
OPT
(
F
)
denotes an optimal solution
for the UFPP instance restricted to the task set
F
.
Throughout this paper, we will use the notations defined above to refer to the
UFPP instance currently under consideration; we will never consider multiple in-
stances simultaneously, so there is no cause for ambiguity.
2.1. Task classification. For our algorithms, we partition the tasks into small,
medium and large tasks. Whether a task is small, medium, or large depends on its
relative demand
d
i
=b
(
i
)
, which is a number in
(0
;
1]
. Such a grouping of the tasks
has been done by several authors before, see e.g. [3, 4, 6, 8, 9, 11].
Let
>
0
and let
>
0
with
1
=
4
and
. For technical reasons
we require that
<
1
. Choosing
and
small will give a better approximation
ratio but worse running time. In the sequel, we will need constants
`
and
q
which
depend on
and
. We define them already here to clarify matters. We choose
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 7
q
such that
2
1
q
and
`
such that
`
+
q
`
1 +
. We define the constant
such that
0
:=
=
(1
)
<
3
p
5
2
and
1+
p
0
1
p
0
0
1 +
(note that this is always
possible). The reason is that later we will invoke an algorithm by Chekuri et al. [11]
as subroutine. That algorithm assumes that the no-bottleneck-assumption holds,
i.e.,
max
i
d
i
min
e
u
e
. It computes a
1+
p
0
1
p
0
0
-approximation if for each task
i
it holds that
d
i
0
b
(
i
)
and
0
<
3
p
5
2
. For technical reasons we additionally
require that
(1
)
=
2
`
. We define a task
i
to be
small, if
d
i
b
(
i
)
,
medium, if
b
(
i
)
< d
i
(1
2
)
b
(
i
)
, and
large, if
(1
2
)
b
(
i
)
< d
i
.
We denote by
F
sml
,
F
med
, and
F
lrg
the set of small, medium, and large tasks of a
given instance. In Section 3 we present approximation algorithms for the small and
medium tasks. After that in Section 4 we present an approximation algorithm for
the large tasks. In Section 5 we show how these results can be combined to yield
our two main approximation algorithms.
3. Small and Medium Tasks
In this section we present constant-factor approximation algorithms for small
and medium tasks. To this end, we give algorithms which compute sets of tasks
ALG
F
k;`
F
k;`
(for sets
F
k;`
defined below) such that
w
(
ALG
F
k;`
)
1
w
(
OPT
F
k;`
)
(for some constant
) and
in each edge the set
ALG
F
k;`
leaves a fraction of the edge-capacity un-
used.
We feed these algorithms into a framework which then yields a constant factor
approximation algorithm for the set of all tasks which are small or medium.
For the small tasks, we obtain a
(1 +
O
(
))
-approximation algorithm, for the
medium tasks we get a
2 +
O
(
)
-approximation algorithm. Putting these two al-
gorithms together, this yields a
(3 +
O
(
))
-approximation algorithm for the set of
all tasks which are small or medium. Finally, we show that if we are allowed to
increase the capacity of each edge by a factor of
1+
(resource augmentation) our
framework even yields a
(2 +
O
(
))
-approximation algorithm for all tasks (small,
medium and large).
3.1. Framework. We define the framework mentioned above. Assume we are
given an instance of the UFPP problem. For our framework, we partition the tasks
according to their bottleneck capacities. We define
F
k;`
:=
i
2
T
j
2
k
b
(
i
)
<
2
k
+
`
for each value
k
such that the resulting set is non-empty. Note that this includes neg-
ative values for
k
. Likewise, we define
F
k;`
sml
:=
F
sml
\
F
k;`
and
F
k;`
med
:=
F
med
\
F
k;`
.
Later we will present algorithms which compute task sets
ALG
F
k;`
med
F
k;`
med
and
ALG
F
k;`
sml
F
k;`
sml
. These sets will have the property that they leave an
amount of
2
k
of the capacity of each edge unused. Also, their profit is only by
a constant
smaller than that of
OPT
F
k;`
med
and
OPT
F
k;`
sml
, respectively. We
make this precise in the following definition.
Definition 1 (
(
;
)
-approximative).Consider a set
F
k;`
. A set
F
F
k;`
is called
(
;
)
-approximative if
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 8
w
(
F
)
1
w
(
OPT
(
F
k;`
))
and,
P
i
2
F
0
\
T
e
d
i
u
e
2
k
for each edge
e
such that
T
e
\
F
k;`
6
=
;
.
An algorithm which computes
(
;
)
-approximative sets in polynomial time is called
an
(
;
)
-approximation algorithm. We call the second condition the modified ca-
pacity constraint.
Our framework consists of a procedure which turns an
(
;
)
-approximation
algorithm for each set
F
k;`
into a
-approximation algorithm for all tasks, where
is a function of
,
and
`
.
Lemma 2 (Framework).Let
>
0
and let
`;q
2
N
such that
2
1
q
. Let the
sets
F
k;`
be defined as stated above. Assume we are given an
(
;
)
-approximation
algorithm for each set
F
k;`
with running time
O
(
p
(
n
))
for a polynomial
p
. Then
there is a
`
+
q
`
-approximation algorithm with running time
O
(
m
p
(
n
))
for the
set of all tasks.
Now we describe the algorithm which yields Lemma 2. Assume that the given
(
;
)
-approximation algorithm computes sets
ALG
F
k;`
F
k;`
. The key idea is
that due to the unused edge-capacities of the sets
ALG
F
k;`
, the union of several
of these sets still yields a feasible solution. With an averaging argument and a
geometric bound we will show further that the indices
k
for the sets
ALG
F
k;`
that we want to combine can even be chosen such that the resulting set is again a
constant factor approximation (and feasible).
Formally, for each offset
c
2 f
0
;:::;`
+
q
1
g
we define
(
c
) =
f
c
+
i
(
`
+
q
)
j
i
2
Z
g
.
For each
c
2 f
0
;:::;`
+
q
1
g
we compute the set
ALG
(
c
) =
S
k
2
(
c
)
ALG
(
F
k;`
)
. In
Lemma 4 we will prove that each set
ALG
(
c
)
is feasible. We output the set
ALG
(
c
)
with maximum profit among all sets
ALG
(
c
)
. In Lemma 5 we will prove that the
resulting set is a
(
`
+
q
`
)
-approximation.
First, we prove a lemma that we will employ to bound the capacity used by the
tasks from each set
ALG
(
F
k;`
)
on each edge. Observe that the lemma is proven
for arbitrary feasible solutions of UFPP.
Lemma 3. Let
F
be a feasible UFPP solution such that for all
i
2
F
,
b
(
i
)
< c
,
and for each edge
e
,
P
i
2
F
\
T
e
d
i
max
f
u
e
c
0
;
0
g
(with
c
0
< c
). Then for each
edge
e
,
P
i
2
F
\
T
e
d
i
<
2(
c
c
0
)
.
Proof. Let
e
be an edge. If
u
e
c
, then the claim follows immediately. Now
suppose that
u
e
> c
. The idea is that any task
i
2
F
\
T
e
must use an edge whose
capacity is less than
c
. In particular, it must use either the closest edge before
e
or the closest edge after
e
whose capacity is less than
c
. Since
F
leaves an amount
of
c
0
of the capacity of each edge unused, it follows that the total capacity used by
tasks in
F
must be less than
2(
c
c
0
)
.
Formally, we define
x
to be the maximum vertex such that
x<e
and
u
f
x;x
+1
g
<
c
, if this exists. In that case, let
F
L
F
\
T
e
consist of all tasks that use
f
x;x
+1
g
. If
such an edge does not exist, then let
F
L
=
;
. Either way, we have that
P
i
2
F
L
d
i
<
c
c
0
. Similarly, we define
y
to be the minimum vertex such that
y > e
and
u
f
y;y
+1
g
< c
, if this exists. Then, let
F
R
F
\
T
e
consist of all tasks that use
f
y;y
+1
g
. Otherwise, let
F
R
=
;
. Since for every task
i
2
F
it holds that
b
(
i
)
< c
,
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 9
it follows that
F
=
F
L
[
F
R
. This implies that
X
i
2
F
\
T
e
d
i
X
i
2
F
L
d
i
+
X
i
2
F
R
d
i
<
2(
c
c
0
)
:
Now we prove that each set
ALG
(
c
)
is feasible, since we chose
2
1
q
.
Lemma 4. For each
c
2 f
0
;:::;`
+
q
1
g
the set
ALG
(
c
)
is feasible.
Proof. Let
c
2 f
0
;:::;`
+
q
1
g
and let
e
be an edge. Denote
t
=
`
+
q
. Let
k
be
the largest integer in
(
c
)
such that
2
k
u
e
. For every
x
2
(
c
)
, denote
U
x
e
=
X
j
2
T
e
\
ALG
(
F
x;`
)
d
j
:
Since
ALG
(
F
k;`
)
is an
(
;
)
-approximation and
2
1
q
,
U
k
e
u
e
2
k
u
e
2
k
+1
q
:
For every
i
1
, Lemma 3 shows that
U
k
it
e
2(2
k
it
+
`
2
k
it
)
2
k
+1
it
+
`
2
k
+2
it
q
:
Summarizing, we have that
X
j
2
T
e
\
ALG
(
c
)
d
j
=
1
X
i
=0
U
k
it
e
u
e
2
k
+1
q
+
1
X
i
=1
(2
k
+1
it
+
`
2
k
+2
it
q
)
< u
e
+
1
X
i
=1
2
k
+1
(
i
1)
t
q
1
X
i
=0
2
k
+1
it
q
=
u
e
:
Now, we use an averaging argument to prove the approximation factor of the
set
ALG
(
c
)
.
Lemma 5. We have that
w
(
ALG
(
c
))
`
`
+
q
1
w
(
F
)
, where
F
denotes an
optimal solution of the given instance.
Proof. We calculate that
`
+
q
1
X
c
=0
w
(
ALG
(
c
))
`
+
q
1
X
c
=0
X
k
2
(
c
)
1
w
OPT
F
k;`
=1
X
k
2
Z
w
OPT
F
k;`
1
X
k
2
Z
w
F
\
F
k;`
=1
X
k
2
Z
k
+
`
1
X
j
=
k
w
F
\
F
j;
1
=
`
w
(
F
)
:
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 10
Hence, there must be one value
c
such that
w
(
ALG
(
c
))
`
`
+
q
1
w
(
F
)
. Since we
defined
c
such that
w
(
ALG
(
c
))
is maximized, the claim follows.
Finally, we can prove Lemma 2 which completes our framework.
Proof of Lemma 2. Lemma 4 implies that
ALG
(
c
)
is feasible and Lemma 5 implies
that
ALG
(
c
)
is a
`
+
q
`
-approximation. For computing
ALG
(
c
)
we need to
compute the set
ALG
F
k;`
for each relevant value
k
. There are at most
m`
2
O
(
m
)
relevant values
k
. Finding the optimal offset
c
can be done in
O
(
m
)
steps.
This yields an overall running time of
O
(
m
p
(
n
))
.
We note that Bansal et al. [4] used a geometric partitioning of the tasks by
demands (rather than by bottleneck capacites like here).
3.2. Approximation for Small Tasks. We present an algorithm which computes
an
(1 +
O
(
)
;
)
-approximative solution
ALG
F
k;`
sml
for each set
F
k;`
sml
. Later, we
will feed the computed sets into the framework of Lemma 2 to get a
(1 +
O
(
))
-
approximation for the small tasks. Recall that our constants
,
,
,
`
, and
q
are
chosen according to Section 2.1.
Consider a set
F
k;`
sml
. The idea is to consider two IP formulations of the problem.
The first one is the natural formulation
IP
k;`
to solve UFPP over the set
F
k;`
sml
.
The second formulation
IP
k;`
tightens the capacity constraint and leaves
2
k
units of each edge capacity unused, which affects the gained profit only by a factor
of
(1
)
1
(1
)
1
since
. We will show in Lemma 7 that solving
IP
k;`
yields a certain approximation to the original problem. To solve
IP
k;`
we use the
algorithm by Chekuri et al. [11], which we will analyze for our purposes in Lemma 6.
The integer programming formulation for
IP
k;`
is defined as follows:
IP
k;`
: max
X
i
2
F
k;`
sml
w
i
x
i
s.t.
X
i
2
T
e
\
F
k;`
sml
x
i
d
i
u
e
8
e
2
E
x
i
2 f
0
;
1
g 8
i
2
F
k;`
sml
Next, we state
IP
k;`
, where each capacity constraint leaves a fraction
unused.
IP
k;`
: max
X
i
2
F
k;`
sml
w
i
x
i
s.t.
X
i
2
T
e
\
F
k;`
sml
x
i
d
i
u
e
2
k
8
e
2
E
x
i
2 f
0
;
1
g 8
i
2
F
k;`
sml
We denote by
LP
k;`
and
LP
k;`
the natural LP relaxations of
IP
k;`
and
IP
k;`
,
where the constraint
x
i
2 f
0
;
1
g
is replaced by
0
x
i
1
. For a given
we
define
f
(
) :=
1+
p
1
p
.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 11
Lemma 6. For a set of tasks with relative demand at most
, the algorithm of
Chekuri et al. [11] computes a feasible solution to
IP
k;`
with value at least
f
(
)
1
w
(
OPT
(
LP
k;`
))
, and can be implemented to run in time
O
(
n
3
log
n
)
.
Proof. The algorithm of Chekuri et al. assumes that all tasks have a relative demand
of at most
and that the no-bottleneck assumption holds (
max
i
d
i
min
e
u
e
).
Recall that we assumed that
(1
)
=
2
`
and for all tasks
i
2
F
k;`
it holds that
d
i
b
(
i
)
. Then,
d
i
2
k
+
`
2
k
2
k
u
e
2
k
u
e
holds for each
task
i
and each edge
e
, and hence the no-bottleneck assumption holds.
The algorithm of Chekuri et al. works as follows. The tasks are partitioned
into at most
n
groups, depending on their demands. The demands and the ca-
pacity are scaled such that a problem with uniform demands and uniform capac-
itiesSince the demands and capacities are uniform, this can be solved optimally
in time
O
(
n
2
log
n
)
, using the algorithm by Arkin and Silverberg [2]. Then the
authors show that combining the solutions of each group yields a feasible solution
to
IP
k;`
. Furthermore, Chekuri et al. have shown in [11, Corollary 3.4] that the
obtained solution is at most a factor
f
(
)
worse than the optimal LP solution.
We envoke the algorithm by Chekuri et al. on
IP
k;`
and obtain the solution
ALG
(
F
k;`
sml
)
.
In the following lemma, we bound its approximation factor.
Lemma 7. The solution
ALG
F
k;`
sml
is
1+
p
0
1
p
0
0
1
1
;
-approximative with
0
1
.
Proof. First, observe that if every task
i
has a relative demand of at most
in
LP
k;`
, then in
LP
k;`
each task has a relative demand of at most
0
with
0
=
1
since
d
i
b
(
i
) =
(1
)
(1
)
b
(
i
)
(1
)
(
b
(
i
)
2
k
)
:
According to the proof of Lemma 6 the no-bottleneck assumption also holds for
IP
k;`
.
Hence, the algorithm returns a
f
(
0
) =
1+
p
0
1
p
0
0
-approximative solution
ALG
F
k;`
sml
to
IP
k;`
. Observe that
OPT
LP
k;`
(1
)
OPT
LP
k;`
holds, since we can
scale the capacity constraints from
LP
k;`
with a factor of
(1
)
and conclude that
every feasible solution of
LP
k;`
scaled down by a factor of
(1
)
corresponds to
a feasible solution of
LP
k;`
. This gives that
w
(
ALG
F
k;`
sml
)
Lemma 6
f
(
0
)
1
w
(
OPT
LP
k;`
)
f
(
0
)
1
(1
)
w
(
OPT
LP
k;`
)
f
(
0
)
1
1
1
w
(
OPT
F
k;`
sml
)
:
We summarize this section in the following lemma.
Lemma 8. Let
;;;`;
and
q
be as defined in Section 2.1. Then there is an algo-
rithm with running time
O
(
n
3
log
n
)
which computes a
(1 +
O
(
)
;
)
-approximative
set
ALG
F
k;`
sml
for each set
F
k;`
sml
.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 12
Proof. Recall that we chose
such that
1+
p
0
1
p
0
0
1 +
with
0
=
1
and
.
Hence, by Lemma 7, the computed set
ALG
F
k;`
sml
is
(1+
O
(
)
;
)
-approximative,
since
1+
p
0
1
p
0
0
1
1
1+
1
=
1+2
+
2
1
2
2
1 +
O
(
)
(as
goes to zero).
At this point we have all necessary techniques for an approximation algorithm
for the special case that all tasks are small. We will need this later for a separate
result which shows that already with a running time of
O
(
n
4
log
n
)
we can obtain
a constant factor approximation. For that result we define the constants
;;;`;
and
q
differently. Therefore, we state the needed constants and their dependencies
explicitly in the following lemma and give the approximation factor depending on
them.
Lemma 9. Let
;;q;`
be constants such that
(1
)
=
2
`
,
2
1
q
,
0
:=
=
(1
)
<
3
p
5
2
, and
<
1
. Consider the UFPP problem with the restriction
that there is a value
such that
d
i
b
(
i
)
for each task
i
. For this problem there
is a polynomial time approximation algorithm with running time
O
(
n
4
log
n
)
and
approximation factor
1 +
p
0
1
p
0
0
1
1
`
+
q
`
Proof. Due to Lemmas 7 and 8 we can compute each
1+
p
0
1
p
0
0
1
1
;
-approximative
set
ALG
F
k;`
sml
in
O
(
n
3
log
n
)
steps. There are at most
n
such sets to compute.
The computation of the sets
ALG
F
k;`
sml
dominate the overall running time. Hence,
our algorithm needs
O
(
n
4
log
n
)
time. With Lemma 2 this yields an algorithm with
an approximation factor of
1+
p
0
1
p
0
0
1
1
`
+
q
`
.
Observe that Lemma 9 only depends on
;
and
`
. Therefore, for a given
the
optimal value of
q
can be computed to be
min
f
q
2
N
j
2
1
q
g
.
3.3. Approximation for Medium Tasks. In this section we describe a dynamic
program which computes an optimal solution for each set
F
k;`
med
. Recall that a task
i
is medium if
b
(
i
)
< d
i
(1
2
)
b
(
i
)
. Afterwards, we show how to transform
this set to obtain a
(2
;
)
-approximative solution. With our framework stated in
Lemma 2 this yields a
2
-approximation algorithm for medium tasks.
First, we derive a technical property for medium tasks which follows from Lemma 3.
Lemma 10. Let
F
be a feasible solution, and let
e
be an edge. For each set
F
k;`
med
we have that
F
\
F
k;`
med
\
T
e
2
`
+1
=
.
Proof. Applying Lemma 3 with
c
0
= 0
shows that
P
i
2
F
\
F
k;`
\
T
e
d
i
2
k
+
`
+1
for
any feasible set
F
and any set
F
k;`
. Since
d
i
>
b
(
i
)
2
k
for each
i
2
F
k;`
med
the claim follows.
Now we show that there is a dynamic program for the sets
F
k;`
med
. A similar DP
was given by Chakrabarti et al. [9].
Lemma 11. There is a dynamic program which computes
OPT
F
k;`
med
for each
set
F
k;`
med
in time
n
O
(
2
`
=
)
.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 13
Proof. We describe the dynamic program. For any edge
e
and set
S
F
k;`
med
\
T
e
,
let
W
e
(
S
)
denote the maximum possible profit for a feasible solution
F
F
k;`
med
that
contains only tasks
i
with
s
i
< e
, with
F
\
T
e
=
S
. We will show how to compute
this for every
e
and relevant
S
, which yields the solution. By Lemma 10, it suffices
to enumerate all sets
S
F
k;`
med
\
T
e
which contain at most
2
`
+1
=
tasks from each
set
F
k;`
med
\
T
e
. There can be at most
n
d
2
O
n
d
such sets, with
d
= 2
`
+1
=
. Let
S
be such a set. Let
e
0
be the edge immediately before
e
, and let
F
e
0
denote all
sets enumerated for
e
0
. We check to what sets in
F
e
0
the set
S
is compatible. A set
S
0
2 F
e
0
is compatible to
S
if all tasks in
T
e
\
T
e
0
appear either in both
S
0
and
S
or in none of the two sets. The reason for this definition is that some of the tasks
in
S
also use
e
0
. Hence, we are only interested in the configurations for
S
0
in which
those tasks appear as well. Moreover, when calculating
W
e
(
S
)
we need to bear in
mind that the profits of the tasks in
S
\
S
0
are already counted in
W
e
0
(
S
0
)
. Denote
by
Comp(
S
)
F
e
0
all sets in
F
e
0
which are compatible to
S
. Now it can be seen
that the value
W
e
(
S
)
can be computed as follows:
W
e
(
S
) := max
S
0
2
Comp(
S
)
8
<
:
W
e
0
(
S
0
) +
X
i
2
(
T
e
n
T
e
0
)
\
S
w
i
9
=
;
As seen above, the number of sets that need to be enumerated for each edge is
bounded by
n
O
(
2
`
=
)
. Hence, the calculation of
W
e
(
S
)
for each set
S
can be done
in
n
O
(
2
`
=
)
2
=
n
O
(
2
`
=
)
steps. Since the number of edges is w. l. o. g. bounded
by
2
n
(see Section 2) the claim follows.
For being able to apply our framework, we turn
OPT
F
k;`
med
into a
(2
;
)
-
approximative solution. We describe the needed procedure in the next lemma.
Lemma 12. For each set
F
k;`
med
there is a set
ALG
F
k;`
med
OPT
F
k;`
med
which is
(2
;
)
-approximative. Moreover, the set
ALG
F
k;`
med
can be found in
O
(
n
2
)
time.
Proof. We initialize two sets
H
1
:=
;
,
H
2
:=
;
. Assume that the tasks in
OPT
F
k;`
med
are ordered such that the start vertices are non-decreasing. We consider the tasks
in
OPT
F
k;`
med
in this order. In the
i
-th iteration we take the task
i
. We add
i
to
a set
H
`
with
`
2 f
1
;
2
g
such that
H
`
[f
i
g
obeys the modified capacity constraint,
i.e., it leaves a free capacity of
2
k
in each edge.
It remains to show that indeed either
H
1
[ f
i
g
or
H
2
[ f
i
g
obeys the modified
capacity constraint. Assume on the contrary that neither
H
1
[ f
i
g
nor
H
2
[ f
i
g
obey the modified capacity constraint. Then there are edges
e;e
0
on the path of
i
such that
(3.1)
X
i
0
2
(
H
1
[f
i
g
)
\
T
e
d
i
0
> u
e
2
k
and
(3.2)
X
i
0
2
(
H
2
[f
i
g
)
\
T
e
0
d
i
0
> u
e
0
2
k
:
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 14
Inequality 3.1 implies that
P
i
0
2
H
1
\
T
e
d
i
0
> u
e
2
k
d
i
. Inequality 3.2 gives
that
P
i
0
2
H
2
\
T
e
0
d
i
0
> u
e
0
2
k
d
i
. Assume w.l.o.g. that
e<e
0
or
e
=
e
0
.
Recall that we considered the tasks by non-decreasing start index. Hence, all tasks
in
(
H
2
[ f
i
g
)
\
T
e
0
use
e
as well. For the next calculation we need that
d
i
(1
2
)
b
(
i
)
u
e
0
(1
2
)
and hence
u
e
0
d
i
2
u
e
0
. Also, note that
u
e
0
2
k
since
i
2
OPT
F
k;`
F
k;`
.
We calculate that
u
e
0
@X
i
0
2
H
1
\
T
e
d
i
0
1
A
+
0
@X
i
0
2
H
2
\
T
e
0
d
i
0
1
A
+
d
i
>
u
e
2
k
d
i
+
u
e
0
2
k
d
i
+
d
i
=
u
e
+
u
e
0
d
i
2
2
k
u
e
+ 2
u
e
0
2
2
k
u
e
:
This is a contradiction. Hence, task
i
can be added to one of the sets
H
`
such that
H
`
[f
i
g
still obeys the capacity constraint. Finally, we define
ALG
F
k;`
med
to be the
set among
H
1
and
H
2
with maximum profit. This ensures that
w
ALG
F
k;`
med
1
2
w
OPT
F
k;`
med
.
When computing
ALG
F
k;`
med
we need to check for each task in
OPT
F
k;`
med
whether adding it to one of the sets violates the modified capacity constraint in
one of the edges. Since w.l.o.g.
m <
2
n
, this check can be done in
O
(
n
)
time
for each task. There are
n
tasks in total, and hence the whole procedure can be
implemented in
O
(
n
2
)
.
Now we have all necessary preparation to state our
(3 +
)
-approximation algo-
rithm for the case that for all tasks
i
it holds that
d
i
(1
2
)
b
(
i
)
, i.e., they are
either small or medium.
Theorem 13. Let
>
0
,
>
0
and consider the UFPP problem with the restriction
that all tasks
i
we have that
d
i
(1
)
b
(
i
)
. There is a polynomial time
(3 +
)
-
approximation algorithm for this problem.
Proof. Above, we defined a task
i
to be medium or small if
d
i
(1
2
)
b
(
i
)
.
Based on this definition, we show how the above procedures yield a
(3 +
O
(
))
-
approximation algorithm. By working with an appropriately chosen value
0
2
O
(
)
rather than
and a value
0
:=
=
2
instead of
, this yields an
(3+
)
-approximation
algorithm for tasks
i
with
d
i
(1
)
b
(
i
)
.
For the given
and
, we choose minimum integer values
l
and
q
such that
2
1
q
, and
l
+
q
l
1 +
. For each set
F
k;`
we compute
ALG
F
k;`
sml
and
ALG
F
k;`
med
. We define
ALG
F
k;`
to be the set of maximum profit among the
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 15
two. Due to Lemmas 8 and 12 we have that
(1 +
O
(
))
w
(
ALG
F
k;`
sml
)+2
w
(
ALG
F
k;`
med
)
w
(
OPT
F
k;`
sml
) +
w
(
OPT
F
k;`
med
)
w
(
OPT
F
k;`
)
and hence
w
(
ALG
F
k;`
)
(3 +
O
(
))
1
w
(
OPT
F
k;`
)
. With the framework of
Lemma 2 this yields an
-approximation algorithm for the UFPP problem with
the restriction that
d
i
(1
2
)
b
(
i
)
for each task
i
, where
= (3 +
O
(
))
l
+
q
l
(3 +
O
(
))(1 +
) = 3+
O
(
)+
O
(
2
) = 3+
O
(
)
, as
goes to zero.As argued above,
this implies the claim of the theorem.
3.4. Resource Augmentation. In this section we study the general UFPP prob-
lem – with small, medium, and large tasks – under resource augmentation. For
an instance
I
of the problem denote by
(1 +
)
I
a copy of
I
where the capacity
of each edge is increased by a factor of
(1 +
)
(for a small value
>
0
). We
present an algorithm that computes a set of tasks
F
whose total profit is at least
(2 +
O
(
))
1
w
(
OPT
(
I
))
and that is feasible for
(1 +
)
I
.
When we increase the capacity of each edge by a factor of
1+
O
(
)
then there are
no large tasks anymore and Theorem 13 yields a
(3+
O
(
))
-approximation algorithm.
However, we can do better. For each set
F
k;`
med
it holds that
OPT
F
k;`
med
leaves
some capacity in
(1 +
)
I
unused. (Note here that
OPT
F
k;`
med
is still defined
to be the optimal solution for
F
k;`
med
in
I
.) Hence, in our framework we can use
OPT
F
k;`
med
instead of
ALG
F
k;`
med
and obtain a
(2 +
O
(
))
-approximation.
Theorem 14. Let
>
0
,
>
0
and let
I
be an instance of the UFPP problem.
There is a polynomial time algorithm which computes a
(2 +
O
(
))
-approximative
solution which is feasible for
(1 +
)
I
.
Proof. For the setting of resource augmentation, we change the notion of
(
;
)
-
approximative sets slightly. Here, we define a set of tasks
F
F
k;`
(for some values
k;`
) to be
(
;
)
-approximative if
w
(
F
)
1
w
(
OPT
(
F
k;`
))
and
P
i
2
F
\
T
e
d
i
u
e
(1 +
)
2
k
for each edge
e
with
T
e
\
F
k;`
6
=
;
. According to this new
definition, each set
OPT
(
F
k;`
)
is
(
;
)
-approximative since
X
i
2
OPT
(
F
k;`
)
\
T
e
d
i
u
e
=
u
e
+
2
k
2
k
u
e
(1 +
)
2
k
for each edge
e
with
T
e
\
F
k;`
6
=
;
. For the purpose of this algorithm, we define
a task to be medium if it is not small. Note that even with the new definition of
medium tasks each set
OPT
F
k;`
med
can still be computed in polynomial time by
the dynamic program described in Lemma 11 (for constant
k
and
).
Consider a set
F
k;`
. We define
ALG
F
k;`
to be the set of maximum profit
among
ALG
F
k;`
sml
and
OPT
F
k;`
med
. We calculate that
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 16
0
1
2
3
4
5
6
0 1 2 4 5 873 6
i
:
d
i
:
w
i
:
s
i
:
t
i
:
1
2
3
4
0 6
1 2
3 4
5 8
2
3
2
3
2
2
2
4
1
2
3
4
Figure 4.1. A UFPP instance consisting of a path of length eight
(with capacities 2,4,4,6,6,5,3,3) and four tasks, represented using
rectangles drawn as high as possible under the capacity profile.
(1 +
O
(
))
w
(
ALG
F
k;`
sml
) +
w
(
OPT
F
k;`
med
)
w
(
OPT
F
k;`
sml
) +
w
(
OPT
F
k;`
med
)
w
(
OPT
F
k;`
)
:
Hence,
ALG
F
k;`
is
(2 +
O
(
)
;
)
-approximative. Our framework defined in Lemma 2
can easily be adapted to the setting of resource augmentation. The only difference
in the resource augmentation setting is that the profit of the computed solution is
measured in comparison to
OPT
(
I
)
rather than
OPT
((1+
)
I
)
. Hence, we obtain
a
(2 +
O
(
))
-approximation algorithm for the UFPP problem with factor
(1 +
)
resource augmentation.
4. Large Tasks
In this section we provide a polynomial time constant factor approximation for
instances consisting of only large tasks. Our main goal is to prove that for the task
set
F
lrg
defined in Section 2.1, i.e. all tasks with relative demand at least
1
=
2
, we
have a 4-approximation algorithm. However, we will prove a more general result:
We assume that for a given integer
k
2
, for all tasks
i
it holds that
d
i
b
(
i
)
=k
,
and we will give a
2
k
-approximation algorithm for this case. The main idea is to
restrict to solutions of a certain form, so-called top-drawn solutions, which will be
defined below. We will give a dynamic programming algorithm for finding optimal
top-drawn solutions in Section 4.1. This dynamic program is based on a geometric
viewpoint of the problem, where tasks are represented by rectangles, which must
not overlap in a feasible solution. In Section 4.2 we will show that if
d
i
b
(
i
)
=k
for all tasks
i
, the value of an optimal top-drawn solution is by at most a factor
2
k
worse than the value of an optimal (UFPP) solution. We will prove this by showing
that any optimal solution can be partitioned into
2
k
top-drawn solutions. Together
this gives the
2
k
-approximation algorithm.
We first explain the geometric viewpoint behind top-drawn solutions, which will
be used for the figures. A UFPP instance can be represented by a drawing in the
plane as follows, see Figure 4.1. The vertices
0
;:::;m
of the path
P
are represented
by the points
(0
;
0)
;:::;
(
m;
0)
on the
x
-axis. An edge
e
=
f
x;x
+ 1
g 2
E
(
P
)
with capacity
u
e
is represented by a horizontal line segment between
(
x;u
e
)
and
(
x
+ 1
;u
e
)
. We add vertical line segments to complete this into a closed curve
from
(0
;
0)
to
(
m;
0)
, called the capacity profile (shown in gray in the figure). The
tasks are represented by rectangles drawn in the region enclosed by the capacity
profile and the
x
-axis: the top of the rectangle is drawn at
y
-coordinate
b
(
i
)
, the
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 17
bottom at the
y
-coordinate
`
(
i
)
. (Recall that
`
(
i
) =
b
(
i
)
d
i
.) The left border of
the rectangle is drawn at
x
-coordinate
s
i
, and the right border at
t
i
. So the height
of the rectangle represents the demand of the task, and the left and right border
the start and end point. Observe that the rectangle is drawn as high as possible
under the capacity profile, which motivates the term top-drawn. A top-drawn set
is now a set of tasks such that their rectangles, when drawn this way, pairwise do
not overlap. To be precise, we say that two rectangles overlap when they share
an internal point; touching is not considered overlapping. Two tasks for which the
rectangles do not overlap are called compatible. The tasks in Figure 4.1 have profits
3, 2, 2, and 2, respectively. Therefore, an optimal UFPP solution consists of tasks
1, 3, and 4, with a total profit of 7. However, since the rectangles for the tasks 1
and 4 overlap, this is not a top-drawn set. The optimal top-drawn set consists of
tasks 2, 3 and 4, with total profit 6. We now define these notions precisely.
Definition 15. Two (distinct) tasks
i
and
j
are called compatible if at least one
of the following holds:
t
i
s
j
,
t
j
s
i
,
`
(
i
)
b
(
j
)
, or
`
(
j
)
b
(
i
)
.
Otherwise,
i
and
j
are called incompatible. A set of tasks
F
is called a top-drawn
set if all tasks in
F
are pairwise compatible.
In Section 4.1, we will consider the optimization problem of finding top-drawn
sets with maximum profit. First we observe that such sets are feasible solutions for
UFPP, and thus we will call them top-drawn solutions.
Proposition 16. Let
F
T
be a top-drawn set. Then
F
is a feasible UFPP
solution.
Proof. Consider an edge
e
2
E
(
P
)
, and all tasks
T
e
that use
e
. Consider two tasks
i;j
2
F
\
T
e
. They are compatible, but
s
i
< e < t
j
and
s
j
< e < t
i
, so either
`
(
i
)
b
(
j
)
or
`
(
j
)
b
(
i
)
must hold. It follows that all tasks in
F
\
T
e
can be
numbered
i
1
;:::;i
p
such that
b
(
i
1
)
`
(
i
2
)
,
b
(
i
2
)
`
(
i
3
)
, etc. Hence
p
X
k
=1
d
i
k
=
p
X
k
=1
(
b
(
i
k
)
`
(
i
k
))
=
b
(
i
p
)
`
(
i
1
) +
p
1
X
k
=1
(
b
(
i
k
)
`
(
i
k
+1
))
|{z }
0
u
e
:
4.1. A Dynamic Programming Algorithm for Finding Maximum Weight
Top-drawn Sets. To bound the complexity of our algorithm, it is useful to assume
that all edge capacities are different. In the next lemma we first show that by mak-
ing small perturbations to the capacities, this property can easily be guaranteed,
without changing the set of feasible solutions.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 18
Lemma 17. Let
I
be a UFPP instance with task set
T
=
f
1
;:::;n
g
. In linear time,
the capacities and demands can be modified such that for the resulting instance
I
0
:
All edge capacities are distinct, and
a set of tasks
F
T
is feasible for
I
if and only if
F
is feasible for
I
0
.
Proof. Recall that the
m
path edges are labeled
f
i;i
+ 1
g
, for
i
2 f
0
;:::;m
1
g
.
For every edge
e
=
f
i;i
+ 1
g
, we change the capacity to
u
0
e
=
mu
e
+
i
. For every
task
j
2
T
, we change the demand to
d
0
j
=
md
j
. This gives the instance
I
0
, in
which all capacities are distinct.
Suppose
F
T
is feasible for
I
0
. Then for every edge
e
=
f
i;i
+ 1
g
, since
all demands are integral,it holds that
P
i
2
T
e
\
F
d
i
=
1
m
P
i
2
T
e
\
F
d
0
i
b
1
m
u
0
e
c
=
b
u
e
+
i
m
c
=
u
e
. Hence
F
is also feasible for the original instance
I
. Clearly, every
task set
F
that is feasible for
I
remains feasible for
I
0
.
The central concept of our dynamic program is that of a corner
(
x;y;z
)
. First
we give an informal, geometric explanation of this notion, using the representation
of the problem explained before. Subsequently, we will give a formal definition.
A corner
(
x;y;z
)
corresponds to a certain region under the capacity profile,
see Figure 4.2. In our dynamic program, we will compute for every such corner
the profit of an optimal top-drawn solution that fits entirely within this region.
This will be done using previously computed values for ‘smaller’ corners. A corner
(
x
0
;y
0
;z
0
)
is smaller than the corner
(
x;y;z
)
if its region is a strict subset of the
region associated with
(
x;y;z
)
(we will make this more precise in the proof of
Lemma 30).
(
w
L
;y
)(
x;y
)
(
x;z
)(
w
R
;z
)
Figure 4.2. All (top-drawn) rectangles that fully lie in the shaded
region fit into the corner
C(
x;y;z
)
.
A corner is determined by an integer
x
-coordinate
0
x
m
(a path vertex), and
two integer
y
-coordinates
y
0
and
z
0
. If the capacity of the edge
f
x
1
;x
g 2
E
(
P
)
is more than
y
, then draw a horizontal line segment from the point
(
x;y
)
to
the left, to the first point that lies on the capacity profile curve. This point will be
called
(
w
L
;y
)
. Otherwise, if the capacity is at most
y
, then let
w
L
=
x
. Similarly, if
the capacity of
f
x;x
+1
g 2
E
(
P
)
is more than
z
, then draw a horizontal line segment
from
(
x;z
)
to the right, to the first point that lies on the capacity profile. This
point will be called
(
w
R
;z
)
. Otherwise, let
w
R
=
x
. Connect these line segments
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 19
into a single curve from
(
w
L
;y
)
to
(
w
R
;z
)
by adding a vertical line segment from
(
x;y
)
to
(
x;z
)
. This curve and the capacity profile together now enclose a bounded
region, which is shown as a shaded region in Figure 4.2. (In the special case that
u
f
x;x
+1
g
> z
u
f
x
1
;x
g
> y
or
u
f
x
1
;x
g
> y
u
f
x;x
+1
g
> z
, the corner actually
corresponds to two disjoint regions.) This is the region shown that we associate
with the corner
(
x;y;z
)
; we say that a task fits into the corner
(
x;y;z
)
when its
rectangle, drawn as explained earlier, lies fully in (the closure of) this region. Now
we give formal definitions.
Definition 18. A triple
(
x;y;z
)
of integers is called a corner if
0
x
m
,
y
0
and
z
0
. For a corner
(
x;y;z
)
, we denote by
w
L
(
x;y
)
or simply
w
L
the lowest
numbered path vertex such that for all
i
with
w
L
i<x
, it holds that
u
f
i;i
+1
g
> y
.
Similarly,
w
R
(
x;z
)
or simply
w
R
is defined to be the largest numbered path vertex
such that for all
i
with
w
R
i > x
, it holds that
u
f
i
1
;i
g
> z
. So
w
L
x
and
w
R
x
, but both may be equalities.
We denote by
u
max
= max
e
2
E
(
P
)
u
e
the maximum capacity of an edge.
Definition 19. For a corner
(
x;y;z
)
, by
C(
x;y;z
)
we denote the set of all tasks
i
2
T
for which at least one of the following holds:
w
L
(
x;y
)
s
i
,
t
i
w
R
(
x;z
)
and
`
(
i
)
max
f
y;z
g
,
w
L
(
x;y
)
s
i
,
t
i
x
and
`
(
i
)
y
, or
x
s
i
,
t
i
w
R
(
x;z
)
and
`
(
i
)
z
.
We say that task
i
fits into the corner
(
x;y;z
)
or corner
(
x;y;z
)
contains
i
if
i
2
C(
x;y;z
)
.
For a given UFPP instance and corner
(
x;y;z
)
, we denote by
P
(
x;y;z
)
the
maximum value of
w
(
F
)
over all top-drawn sets
F
with
F
C(
x;y;z
)
. A top-
drawn task set
F
with
F
C(
x;y;z
)
and
w
(
F
) =
P
(
x;y;z
)
is said to determine
P
(
x;y;z
)
. We will now show how
P
(
x;y;z
)
can be computed in various cases. First
we observe that all tasks fit into the corner
(
m;
0
;u
max
)
, so computing
P
(
m;
0
;u
max
)
yields the desired value:
Proposition 20.
P
(
m;
0
;u
max
)
equals the value of an optimal top-drawn solution,
where
m
is the path length.
We first consider two simple cases in which different corners (integer triples)
define the same region. The following two propositions follow easily from the defi-
nitions.
Proposition 21. If
y
=
z
, then
C(
x;y;z
) = C(
w
R
(
x;z
)
;y;u
max
)
.
Because of this proposition, we only have to consider corners
(
x;y;z
)
where
y < z
or
y > z
. Since these cases are symmetric, we will only consider corners
(
x;y;z
)
for which
y < z
holds, in the following definitions and lemmas. One can easily
deduce the corresponding statements for the case
y > z
. For the sake of brevity
and readability, we will however not explicitly treat this case.
Proposition 22. If
x
= 0
or
y
u
f
x
1
;x
g
then
C(
x;y;z
) = C(
x;u
max
;z
)
.
The above observations show that we may restrict our attention to standard
corners, defined as follows. Within this category we distinguish two further corner
types.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 20
Definition 23. A corner
(
x;y;z
)
is called standard if
y < z
,
x
1
and
y <
u
f
x
1
;x
g
. A standard corner
(
x;y;z
)
is called split if
u
f
x
1
;x
g
z < u
f
x;x
+1
g
, and
proper otherwise.
In the case of a split corner, we can give a simple expression for
P
(
x;y;z
)
.
Proposition 24. Let
(
x;y;z
)
be a split corner. Then
P
(
x;y;z
) =
P
(
x;y;u
max
) +
P
(
x;u
max
;z
)
.
Proof. Consider a top-drawn set
F
that determines
P
(
x;y;z
)
. Since
u
f
x
1
;x
g
z
,
every task
i
2
F
with
s
i
x
1
and
t
i
x
has
b
(
i
)
z
. Hence
F
contains
no tasks
i
with
s
i
x
1
and
t
i
x
+ 1
, and thus can be partitioned into two
top-drawn sets that fit into the corners
(
x;y;u
max
)
and
(
x;u
max
;z
)
respectively. It
follows that
P
(
x;y;z
)
P
(
x;y;u
max
) +
P
(
x;u
max
;z
)
.
Now let
F
1
and
F
2
be top-drawn sets that determine
P
(
x;y;u
max
)
and
P
(
x;u
max
;z
)
.
These are disjoint and both fit in the corner
(
x;y;z
)
, so
P
(
x;y;z
)
w
(
F
1
) +
w
(
F
2
) =
P
(
x;y;u
max
) +
P
(
x;u
max
;z
)
.
(
x;z
)
(
x;b
(
i
))
(
s
i
;y
)
w
L
(
x;b
(
i
))
(
s
i
;b
(
i
))
w
R
(
s
i
;b
(
i
))
(
x;z
)
(
x;y
)
ii
Figure 4.3. On the left, a top-drawn set
F
C(
x;y;z
)
is shown.
When choosing a special task
i
2
F
with no tasks below or to the
right of it,
F
nf
i
g
C(
s
i
;y;b
(
i
))
[
C(
x;b
(
i
)
;z
)
.
Now we will consider the more complex case where the given corner
(
x;y;z
)
is
proper. The main idea is as follows. Consider a top-drawn set
F
that determines
P
(
x;y;z
)
. Either
F
also fits into the smaller corner
(
x
1
;y;z
)
, or there exists
a task
j
with
`
(
j
)
< z
and
t
j
=
x
. In the latter case, we show that
F
can be
partitioned into two task sets that fit into smaller corners, and one single task.
Given a task
i
, we will consider the two smaller corners
(
s
i
;y;b
(
i
))
and
(
x;b
(
i
)
;z
)
.
These are illustrated in Figure 4.3. For the indicated task
i
and the depicted top-
drawn set
F
, we have the desired property that
F
nf
i
g
C(
s
i
;y;b
(
i
))
[
C(
x;b
(
i
)
;z
)
.
We will show that there always exists a task
i
for which this holds; such a task is
called special. This explains the following recursive formula.
Lemma 25. Consider a UFPP instance in which all edge capacities are distinct.
Let
(
x;y;z
)
be a proper corner. Then
P
(
x;y;z
) = max
P
(
x
1
;y;z
)
;
max
i
2
C(
x;y;z
)
;t
i
x
n
w
i
+
P
s
i
;y;b
(
i
)
+
P
x;b
(
i
)
;z
o
:
Before we can prove Lemma 25, we will define which properties are required for
a special task, and prove that such a task always exists. Informally, the essential
property of a special task
i
is that the rectangular region that is defined by the
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 21
(
x;y
)
(
x;z
)
(
s
i
;y
)
(
x;b
(
i
))
(
x;z
)
w
L
(
x;b
(
i
))
w
R
(
s
i
;b
(
i
))
(
s
i
;b
(
i
))
: to the right of
i
: below
i
i i
Figure 4.4. On the left, a top-drawn set
F
C(
x;y;z
)
is shown.
The corners
(
s
i
;y;b
(
i
))
and
(
x;b
(
i
)
;z
)
, given by a non-special can-
didate task
i
2
F
, contain all tasks in
F
that do not lie below
i
or
to the right of
i
.
horizontal interval
[
s
i
;x
]
and the vertical interval
[
y;b
(
i
)]
does not overlap with
any task rectangle other than
i
, and does not overlap with the capacity profile. In
this case we will say that there are no tasks in
F
that lie to the right of
i
or lie
below
i
. Figure 4.4 illustrates the case where a (non-special) task
i
is chosen, such
that the rectangular region does overlap with other task rectangles. We now define
this precisely.
Definition 26. Consider a proper corner
(
x;y;z
)
, and a task
i
2
C(
x;y;z
)
with
t
i
x
.
A task
j
2
C(
x;y;z
)
lies to the right of
i
if
t
i
s
j
< x
and
`
(
j
)
< b
(
i
)
.
A task
j
2
C(
x;y;z
)
lies below
i
if
b
(
j
)
`
(
i
)
and
t
j
> s
i
.
A task
i
2
C(
x;y;z
)
is called a candidate for
(
x;y;z
)
if
–
t
i
x
,
–
`
(
i
)
< z
and
–for all edges
e
2
E
(
P
)
with
s
i
< e < x
,
u
e
b
(
i
)
holds.
Definition 27. Let
(
x;y;z
)
be a proper corner and
F
C(
x;y;z
)
be a top-drawn
set. A task
i
2
F
is called special (with respect to
F
and
(
x;y;z
)
) if it is a candidate
for
(
x;y;z
)
, and there is no task
j
2
F
that lies to the right of
i
or that lies below
i
.
Lemma 28. Let
(
x;y;z
)
be a proper corner and
F
C(
x;y;z
)
be a top-drawn set.
Then at least one of the following holds:
F
C(
x
1
;y;z
)
, or
there exists a special task
i
2
F
(with respect to
F
and
(
x;y;z
)
).
Proof. From
u
f
x
1
;x
g
> y
it follows that
w
L
(
x;y
) =
w
L
(
x
1
;y
)
. Since the corner
is not split, we have that
w
R
(
x
1
;z
) =
w
R
(
x;z
)
in the case that
z < u
f
x;x
+1
g
(and
thus
z < u
f
x
1
;x
g
), and
w
R
(
x
1
;z
)
w
R
(
x;z
) =
x
in the case that
z > u
f
x;x
+1
g
.
Therefore, since
y < z
it holds that
C(
x
1
;y;z
)
C(
x;y;z
)
. Furthermore, this
shows that the only case when
F
C(
x
1
;y;z
)
does not hold is when there is a
task
j
2
F
with
t
j
=
x
and
`
(
j
)
< z
. Hence it is easily seen that
j
is a candidate (for
(
x;y;z
)
). In addition, since
t
j
=
x
, no task in
F
lies to the right of
j
. So to prove
the lemma statement, we may assume that there exists at least one candidate task
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 22
in
F
with no tasks to the right of it. Choose
i
2
F
to be such a task with minimum
value for
b
(
i
)
. We prove that no task in
F
lies below
i
, which will prove the lemma.
Suppose to the contrary that a task
j
2
F
lies below
i
, so
b
(
j
)
`
(
i
)
< b
(
i
)
and
t
j
> s
i
. It is easily checked that
j
is a candidate as well. By choice of
i
, it must then
hold that there exists a task
k
2
F
that lies to the right of
j
(otherwise
j
should
have been chosen in the role of
i
). So
t
j
s
k
< x
, and
`
(
k
)
< b
(
j
)
`
(
i
)
< b
(
i
)
.
Therefore,
s
k
< t
i
; otherwise
k
would also lie to the right of
i
. But now we can use
the fact that
i
and
k
are compatible: Recall that we have that
s
k
< t
i
,
s
i
< t
j
s
k
,
and
`
(
k
)
< b
(
j
)
< b
(
i
)
. So the only case in which
i
and
k
can be compatible is when
b
(
k
)
`
(
i
)
< b
(
i
)
. This however contradicts the fact that all edges between
s
i
and
x
have capacity at least
b
(
i
)
; the edge that determines
b
(
k
)
lies between
s
i
and
x
.
We conclude that
i
is a candidate task that satisfies the additional properties that
there are no tasks in
F
below it, or to the right of it, which therefore is special.
Now we can prove Lemma 25.
Proof of Lemma 25. Let
(
x;y;z
)
be a proper corner in a UFPP instance in which
all capacities are distinct. We will first show that
(4.1)
P
(
x;y;z
)
max
P
(
x
1
;y;z
)
;
max
i
2
C(
x;y;z
)
;t
i
x
n
w
i
+
P
s
i
;y;b
(
i
)
+
P
x;b
(
i
)
;z
o
:
Let
F
be a top-drawn set that determines
P
(
x;y;z
)
. If
F
C(
x
1
;y;z
)
then
P
(
x;y;z
)
P
(
x
1
;y;z
)
. If not, then by Lemma 28, there exists a special task
i
.
We argue that
F
nf
i
g
can be partitioned into two top-drawn sets
F
1
and
F
2
with
F
1
C
s
i
;y;b
(
i
)
and
F
2
C
x;b
(
i
)
;z
, which will prove that
P
(
x;y;z
)
n
w
i
+
P
s
i
;y;b
(
i
)
+
P
x;b
(
i
)
;z
o
, and therefore the Inequality 4.1. First we consider
the
w
L
and
w
R
vertices for both corners. Let
e
B
=
f
v;v
+ 1
g
be a bottleneck
edge for
i
, which is unique since all capacities are distinct. So
u
e
B
=
b
(
i
)
and
s
i
< e
B
< t
i
. For the corner
(
s
i
;y;b
(
i
))
, it is easy to see that
w
L
(
s
i
;y
) =
w
L
(
x;y
)
and
w
R
(
s
i
;b
(
i
)) =
v
. Now consider the corner
(
x;b
(
i
)
;z
)
. Obviously the
w
R
value
is the same as for
C(
x;y;z
)
. In addition, since
i
is special, all edges
e
with
s
i
<
e
B
<e<x
have
u
e
b
(
i
)
. Therefore, since we assumed all edge capacities are
distinct,
u
e
> b
(
i
)
holds for all such edges
e
. It follows that
w
L
(
x;b
(
i
)) =
v
+ 1
.
Now consider a task
j
2
F
nf
i
g
. We distinguish five cases.
(1)
t
j
s
i
: Since
w
L
(
x;y
) =
w
L
(
s
i
;y
)
and
`
(
j
)
y
, we have that
j
2
C(
s
i
;y;b
(
i
))
.
(2)
s
i
< t
j
< e
B
: Since
j
is compatible with
i
but does not lie below
i
,
`
(
j
)
b
(
i
)
holds. Therefore
j
2
C(
s
i
;y;b
(
i
))
.
(3)
s
j
x
: From
j
2
C(
x;y;z
)
it easily follows that
j
2
C(
x;b
(
i
)
;z
)
.
(4)
e
B
< s
j
< x
: Since
j
is compatible with
i
but does not lie to the right
of
i
,
`
(
j
)
b
(
i
)
must hold. In addition, if
t
j
> x
then
`
(
j
)
z
. Therefore
j
2
C(
x;b
(
i
)
;z
)
.
(5)
s
j
< e
B
and
e
B
< t
j
: We argue that this is not possible. We have that
b
(
j
)
u
e
B
=
b
(
i
)
. Because
i
and
j
are compatible, it then must be that
b
(
j
)
`
(
i
)
. But this contradicts that there is no task below
i
.
Since we considered all possibilities, this concludes the proof of Inequality 4.1.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 23
Next, we argue that
(4.2)
P
(
x;y;z
)
max
P
(
x
1
;y;z
)
;
max
i
2
C(
x;y;z
)
;t
i
x
n
w
i
+
P
s
i
;y;b
(
i
)
+
P
x;b
(
i
)
;z
o
:
Recall that since
(
x;y;z
)
is a standard corner,
C(
x
1
;y;z
)
C(
x;y;z
)
, so
P
(
x;y;z
)
P
(
x
1
;y;z
)
. Now consider a task
i
2
C(
x;y;z
)
with
t
i
x
. Let
F
1
and
F
2
be the top-drawn sets that determine
P
(
s
i
;y;b
(
i
))
and
P
(
x;b
(
i
)
;z
)
, re-
spectively. We will argue that
F
1
\
F
2
=
;
and
F
1
[
F
2
C(
x;y;z
)
. Since clearly
i
62
F
1
and
i
62
F
2
, it will follow that
P
(
x;y;z
)
w
i
+
P
(
s
i
;y;b
(
i
)) +
P
(
x;b
(
i
)
;z
)
,
proving Inequality 4.2.
Now let
e
B
a bottleneck edge for
i
. Then
w
R
(
s
i
;b
(
i
))
< e
B
. On the other
hand, since
t
i
x
, it holds that
w
L
(
x;b
(
i
))
> e
B
. It follows that
F
1
\
F
2
=
;
.
Finally, we prove that both sets fit in the corner
(
x;y;z
)
. Recall that
w
R
(
s
i
;b
(
i
))
<
e
B
< t
i
x
. Since in addition
b
(
i
)
> y
, it follows that
C(
s
i
;y;b
(
i
))
C(
x;y;z
)
.
(Because
w
R
(
s
i
;b
(
i
))
< x
, it is irrelevant whether
b
(
i
)
> z
or not.) It is obvious that
C(
x;b
(
i
)
;z
)
C(
x;y;z
)
, since
b
(
i
)
> y
. This concludes the proof of Inequality 4.2.
Algorithm 1:
P
(
x;y;z
)
: a recursive algorithm for computing
P
(
x;y;z
)
Input: A UFPP instance where
u
max
is the maximum edge capacity, all edge
capacities are distinct, and integers
0
x
m
,
0
y
u
max
,
0
z
u
max
.
Output:
P
(
x;y;z
)
.
if
x
= 0
or
y
u
f
x
1
;x
g
then
y
:=
u
max
1
if
x
=
m
or
z
u
f
x;x
+1
g
then
z
:=
u
max
2
Compute
w
L
:=
w
L
(
x;y
)
and
w
R
:=
w
R
(
x;z
)
3
if
w
L
=
w
R
then return 04
if
y
=
z
then
z
:=
u
max
;
x
:=
w
R
5
if
y < z
then6
if
u
f
x
1
;x
g
z < u
f
x;x
+1
g
then return (
P
(
x;y;u
max
) +
P
(
x;u
max
;z
))
7
return
max
n
P
(
x
1
;y;z
)
;
8
max
i
2
C(
x;y;z
)
;t
i
x
w
i
+
P
s
i
;y;b
(
i
)
+
P
x;b
(
i
)
;z
o
end
(In the remaining case,
y > z
holds:)
if
u
f
x;x
+1
g
y < u
f
x
1
;x
g
then return (
P
(
x;y;u
max
) +
P
(
x;u
max
;z
))
9
return
max
n
P
(
x
+ 1
;y;z
)
;
10
max
i
2
C(
x;y;z
)
;s
i
x
w
i
+
P
t
i
;b
(
i
)
;z
+
P
x;y;b
(
i
)
o
Our recursive routine
P
(
x;y;z
)
for computing
P
(
x;y;z
)
is summarized in Algo-
rithm 1. We first argue that the correct answer is returned.
Lemma 29. When given a corner
(
x;y;z
)
, Algorithm 1 returns
P
(
x;y;z
)
.
Proof. We prove the statement by induction over the total number of recursive calls.
That is, we will prove that a call
P
(
x;y;z
)
returns the value
P
(
x;y;z
)
, assuming
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 24
that this holds for recursive calls
P
(
x
0
;y
0
;z
0
)
that may be made. (Note that we
prove below in Lemma 30 that the algorithm indeed terminates.)
The modification in Line 1 yields an equivalent corner by Proposition 22. By
symmetry, the same holds for Line 2. If
w
L
=
w
R
then
C(
x;y;z
) =
;
, so the
correct answer is returned in Line 4. The modification in Line 5 is correct as well
(Proposition 21). So we may assume now that
w
L
< w
R
, and
y
6
=
z
.
Consider the case that
y < z
. This implies that
y < u
max
, so
x
1
and
y <
u
f
x
1
;x
g
, and thus
(
x;y;z
)
is a standard corner. If
u
f
x
1
;x
g
z
and
z < u
f
x;x
+1
g
,
then it is a split corner, so Proposition 24 shows that Line 7 returns the correct
answer. So if Line 8 is reached, the considered corner is proper. By Lemma 25,
Line 8 returns the correct answer.
The case that
y > z
is analog; by symmetric arguments, the answers given in
Lines 9 and 10 are correct. This shows that Algorithm 1 returns the correct answer
in every case.
Now we show that the recursion terminates, by showing that all recursive calls
are made with arguments
(
x
0
;y
0
;z
0
)
that are ‘smaller’ than the original argument
(
x;y;z
)
.
Lemma 30. Algorithm 1 terminates.
Proof. We show that when given an input
(
x;y;z
)
, all recursive calls will be with
arguments
(
x
0
;y
0
;z
0
)
such that the corner
(
x
0
;y
0
;z
0
)
is strictly smaller than
(
x;y;z
)
,
with respect to the following size measure: For a corner
(
x;y;z
)
with
y
u
max
and
z
u
max
, we define
area
(
x;y;z
)=(
x
w
L
)(
u
max
y
)+(
w
R
x
)(
u
max
z
)
:
Note that for all corners
(
x;y;z
)
that may be considered, area
(
x;y;z
)
is a non-
negative integer. Hence the lemma statement then follows.
A recursive call is made in Line 7 whenever a corner
(
x;y;z
)
is considered that
satisfies the following bounds. Firstly
y < z
u
max
, and therefore
x
1
and
y < u
f
x
1
;x
g
. Hence
(
x;y;z
)
is a standard corner, and
w
L
< x
. If the if-condition
is satisfied then
w
R
> x
holds. This shows that for both calls
P
(
x;y;u
max
)
and
P
(
x;u
max
;z
)
, the size measure area strictly decreases. Now consider Line 8, which
is reached whenever the corner is a proper corner. In this case, when considering
the corner
(
x
1
;y;z
)
, the
w
L
value does not change, and the
w
R
value may
only decrease (see the proof of Lemma 28). Since
y < z
it then follows that
area
(
x
1
;y;z
)
<
area
(
x;y;z
)
. Now consider a task
i
2
C(
x;y;z
)
with
t
i
x
. We
have that
w
R
(
s
i
;b
(
i
))
< x
and
b
(
i
)
> y
, so area
(
s
i
;y;b
(
i
))
<
area
(
x;y;z
)
. Clearly,
area
(
x;b
(
i
)
;z
)
<
area
(
x;y;z
)
. So in all recursive calls in Line 8, the area decreases.
By symmetry, the same holds for Lines 9 and 10.
Theorem 31. An optimum top-drawn set for a UFPP instance can be computed
in time
O
(
nm
3
)
O
(
n
4
)
.
Proof. The algorithm is as follows. First, in time
O
(
n
+
m
)
, we transform the
given instance into an equivalent instance, in which all edge capacities are distinct
(Lemma 17). As mentioned in Section 2 in time
O
(
n
+
m
)
we can transform
the instance to an equivalent instance in which all vertices occur as the start or
end vertex of some task, so we may assume that
m <
2
n
. This preprocessing
does not change
n
and cannot increase
m
. We call Algorithm 1, with arguments
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 25
(
x;y;z
) = (
m;
0
;u
max
)
, to obtain the total profit of an optimal top-drawn set
(Proposition 20, Lemma 29). With a straightforward extension, we can compute
an optimal top-drawn set itself.
A small modification is necessary to obtain a time complexity of
O
(
nm
3
)
: when-
ever any value
P
(
x;y;z
)
is computed during the course of computation, this value
is stored in a table. Whenever a recursive call to
P
(
x;y;z
)
would be made, the
algorithm instead returns the stored value
P
(
x;y;z
)
, if it has been computed before
(in a different recursion branch). This, together with Lemma 30, ensures that for
every corner
(
x;y;z
)
the routine
P
(
x;y;z
)
is called at most once during the course
of computation. (Lemma 30 ensures that a given corner is not considered more
than once in the same recursion branch.)
We call a corner
(
x;y;z
)
relevant if
y
= 0
or
y
is equal to the capacity of some
edge, and if the same holds for
z
. Observe that when calling Algorithm 1 with a
relevant corner as argument, then every possible recursive call is with a relevant
corner as well. So the total number of recursive calls is bounded by the total number
of relevant corners. There are at most
m
+1
possibilities for
x
, and at most
m
+1
for
y
and
z
(since these need to correspond to actual capacities), so the total number
of recursive calls is bounded by
O
(
m
3
)
. Now consider the complexity of a single
call. Line 3 can be done in time
O
(
m
)
. Ignoring recursive calls, Lines 7 and 9
take constant time. Lines 8 and 10 take time
O
(
n
)
; for every task
i
, in constant
time one can decide whether
i
2
C(
x;y;z
)
and
t
i
x
(resp.
s
i
x
), and evaluate
the given expressions. The remaining lines clearly take constant time, so it follows
that a single call of Algorithm 1 takes time
O
(
n
) +
O
(
m
)
O
(
n
)
. Hence the total
complexity becomes
O
(
nm
3
)
O
(
n
4
)
.
4.2. The Coloring Lemma. For any integer
k
2
, we call a task
i
1
=k
-large if
its relative demand is at least
1
=k
, that is,
d
i
1
=k
b
(
i
)
.Our goal in this section
is to show that if
F
is a feasible solution to an UFP instance, where all tasks in
F
are
1
=k
-large, then
F
can be partitioned into
2
k
top-drawn sets.
A partition
f
F
1
;:::;F
`
g
of a task set
F
into
`
top-drawn sets will be encoded by
an
`
-coloring
of
F
. This is a function
:
F
! f
1
;:::;`
g
such that if
(
i
) =
(
j
)
,
then
i
and
j
are compatible. (So
(
i
) =
j
means that
i
2
F
j
.) Now we can
formulate the main lemma of this section.
Lemma 32. Let
F
be a feasible UFPP solution, and let
k
2
be an integer, such
that every task in
F
is
1
=k
-large. Then there exists a
2
k
-coloring for
F
.
Before we can prove Lemma 32, we first need some more definitions and the
following proposition.
Proposition 33. Let
F
be a feasible UFPP solution, and let
k
2
be an integer,
such that every task in
F
is
1
=k
-large. Let
e
be a bottleneck edge for
i
2
F
. Then
there are at most
k
1
tasks
j
2
F
nf
i
g
that are incompatible with
i
and use
e
.
Proof. Let the set
F
0
F
nf
i
g
consist of all tasks that are incompatible with
i
and
that use
e
. Suppose
j
F
0
j
k
. Then
d
i
+
X
j
2
F
0
d
j
d
i
+1
k
X
j
2
F
0
b
(
j
)
> d
i
+1
k
j
F
0
j
(
b
(
i
)
d
i
)
b
(
i
)
u
e
;
contradicting that
F
is a feasible solution.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 26
An edge
e
is called a separator for a task set
F
if it is a bottleneck edge for
some task
i
2
F
, such that all tasks in
F
that use
e
are incompatible with
i
. So
by the above proposition, there are at most
k
tasks in
F
that use
e
, when
F
is
a UFPP solution consisting of
1
=k
-large tasks. A coloring
of
F
is called nice if
for every edge
e
and task
i
2
F
that has
e
bottleneck, all tasks that use
e
and are
incompatible with
i
are colored differently. The main idea behind these notions and
our construction of a coloring is as follows: We will identify a separator edge
e
, and
consider the set
F
0
of tasks
i
with
s
i
< e
, and
F
1
of tasks
i
with
t
i
> e
. (Note that
F
0
[
F
1
=
F
and
F
0
\
F
1
6
=
;
.) Unless
F
0
=
F
or
F
1
=
F
, we may use induction to
conclude that both admit a nice
2
k
-coloring. Then, since
e
is a separator edge and
the colorings are nice, all tasks in
F
0
\
F
1
are colored differently in both colorings.
Therefore these can be combined into a single nice
2
k
-coloring for
F
. However,
since it may occur that
F
0
=
F
or
F
1
=
F
, we need a slightly more sophisticated
argument, which we will now present in detail.
L
e
1
e
2
e
3
e
4
e
5
=
e
B
Figure 4.5. An illustration of the proof of Lemma 32 for the
case
k
= 2
(using logarithmic scale on the
y
-axis, all tasks are
1
2
-
large). The gray task is the single task in
L
, and the bold tasks
are associated with the indicated separator edges
e
1
;:::;e
5
.
Proof of Lemma 32. Now we will prove the main lemma, by induction over
j
F
j
. In
fact, we will prove that the following stronger statement holds:
Let
F
be a feasible solution consisting of
1
=k
-large tasks. Then there exists a nice
2
k
-coloring for
F
.
The statement is trivially true when
j
F
j
2
k
. Now suppose that
j
F
j
>
2
k
, and
assume that the above statement holds for every such set
F
0
with
j
F
0
j
<
j
F
j
. The
proof is illustrated in Figure 4.5. Let
e
B
be a bottleneck edge for some task in
F
,
with minimum capacity among all such edges. Let
L
F
be the set of tasks that
use
e
B
. By Proposition 33 and the choice of
e
B
,
j
L
j
k
.
Let
E
S
=
f
e
1
;:::;e
p
g
be the set of edges
e
for which there is a task
i
with
e
as bottleneck edge, such that
i
2
L
or
i
is incompatible with some
j
2
L
. (So
e
B
2
E
S
.) The edges in
E
S
are numbered such that if
x<y
, then
e
x
< e
y
.
We first argue that all edges in
E
S
are separators for
F
. For
e
B
2
E
S
, the
statement is clear since
e
B
is a bottleneck edge with minimum capacity. Now
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 27
consider an edge
e
2
E
S
nf
e
B
g
, and let
i
2
F
be a task with
e
as bottleneck, that
is incompatible with some task
i
0
2
L
. Then
`
(
i
)
< b
(
i
0
)
holds. Now suppose there
is a task
i
00
using
e
that is compatible with
i
. Since both
i
and
i
00
use
e
and
e
is a
bottleneck edge of
i
, from their compatibility it follows that
b
(
i
00
)
`
(
i
)
< b
(
i
0
) =
e
B
. But this contradicts that
e
B
is a bottleneck edge for
F
with minimum capacity.
Now, for
1
j
p
1
, define
F
j
F
to be all tasks
i
with
s
i
< e
j
+1
and
t
i
> e
j
. Similarly, define
F
0
F
to be all tasks
i
with
s
i
< e
1
, and define
F
p
F
to be all tasks
i
with
t
i
> e
p
. Observe that
F
0
[
:::
[
F
p
=
F
.
CASE 1: For every
j
,
j
F
j
j
<
j
F
j
.
In this case, we may use induction to conclude that for every
F
j
there exists a
nice
2
k
-coloring
j
. We can combine these into a nice
2
k
-coloring of
F
: all tasks
in
C
=
F
0
\
F
1
use the edge
e
1
. Since
e
1
is a separator, there exists a task
i
2
C
with
e
1
as bottleneck such that all tasks using
e
1
are incompatible with
i
. So, in
both the nice
2
k
-coloring
0
of
F
0
and the nice
2
k
-coloring
1
of
F
1
, all tasks in
C
are colored differently. Therefore, we can permute the colors of
1
such that the
tasks in
C
receive the same colors in
0
and
1
. At this point, the colorings can
be combined into a
2
k
-coloring
0
of
F
0
[
F
1
, which is again nice.
Next, we can combine the nice
2
k
-coloring
2
of
F
2
with the nice
2
k
-coloring
0
of
F
0
[
F
1
in a similar way, and continue like this with
F
3
;:::;F
p
, until a nice
2
k
-coloring of
F
=
F
0
[
:::
[
F
p
is obtained. This proves the desired statement in
this case.
CASE 2: There exists a
j
such that
F
j
=
F
.
For such a choice of
j
, define
F
0
j
=
F
j
n
L
. Since
L
is non-empty,
j
F
0
j
j
<
j
F
j
holds,
so we may again use induction to conclude that
F
0
j
admits a nice
2
k
-coloring
.
We will extend this to a nice
2
k
-coloring of
F
j
=
F
. For ease of exposition we will
assume that
1
j < p
(the cases
j
= 0
and
j
=
p
are similar but easier). So both
e
j
and
e
j
+1
are edges in
E
S
. We assume also w.l.o.g. that
e
B
e
j
+1
.
We observe that every task
i
2
F
0
j
that is incompatible with some task in
L
uses
either
e
j
or
e
j
+1
: by definition of
E
S
, such a task
i
must use some edge
e
x
2
E
S
.
If
x>j
+ 1
then by definition of
F
j
,
i
also uses
e
j
+1
. If
x<j
then similarly
i
also
uses
e
j
.
Since
e
B
e
j
+1
and
F
j
=
F
, all tasks in
L
use
e
j
+1
. Then, since
e
j
+1
is a
separator, there are at most
k
j
L
j
tasks in
F
0
j
that use
e
j
+1
(Proposition 33);
let
F
R
denote these tasks. In addition, there are at most
k
tasks in
F
0
j
that use
e
j
; denote these by
F
L
. Since
j
F
L
j
+
j
F
R
j
2
k
j
L
j
and there are
2
k
available
colors, we can choose
j
L
j
different colors that are not used for tasks in
F
L
[
F
R
,
in the coloring
. We extend the nice
2
k
-coloring
for
F
0
j
to
F
j
=
F
by using
these
j
L
j
colors for the tasks in
L
. Since we observed that all tasks in
F
0
j
that are
incompatible with some task in
L
are included in
F
L
[
F
R
, it follows that this yields
again a nice
2
k
-coloring for
L
. Since we now constructed a nice
2
k
-coloring for
F
in all cases, this concludes the proof of Lemma 32.
We observe that the bound from Lemma 32 is tight for every
k
2
: consider a
path
P
of length 5, with capacities
2
k
2
,
2
k
2
+2
k
,
2(2
k
2
+2
k
)
,
2
k
2
+2
k
and
2
k
2
, in
order along the path. (So
V
(
P
) =
f
0
;:::;
5
g
.) Introduce
k
1
tasks with
s
i
= 0
,
t
i
= 3
and
d
i
= 2
k
+1
,
k
1
tasks with
s
i
= 2
,
t
i
= 5
and
d
i
= 2
k
+1
, one task with
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 28
s
i
= 1
,
t
i
= 3
and
d
i
= 2
k
+3
, and one task with
s
i
= 2
,
t
i
= 4
and
d
i
= 2
k
+3
. All
tasks can be verified to be
1
k
-large. In addition, they all satisfy
b
(
i
)
2
k
2
> `
(
i
)
and
s
i
2
<
3
t
i
, so all are pairwise incompatible, and therefore at least
2
k
colors are needed. Finally, they constitute a feasible UFPP solution: for the first
and fifth edge this is easy to see. For the second and fourth edge, the sum of
demands using the edge is
(
k
1)(2
k
+ 1) + (2
k
+ 3) = 2
k
2
+
k
+ 2
2
k
2
+ 2
k
=
u
(1
;
2)
=
u
(3
;
4)
, since
k
2
. All tasks use the third edge, so the demand sum is
2
((
k
1)(2
k
+1)+(2
k
+3)) = 2
(2
k
2
+
k
+2) = 4
k
2
+2
k
+4
4
k
2
+4
k
=
u
f
2
;
3
g
,
since
k
2
.
We summarize the results of Section 4 in the following theorem.
Theorem 34. For every integer
k
2
, there is a
O
(
n
4
)
time
2
k
-approximation
algorithm for the UFPP problem restricted to instances where every task is
1
k
-large.
Proof. In time
O
(
n
4
)
we compute an optimum top-drawn set
F
A
for the instance
(Theorem 31). This is a feasible UFPP solution (Proposition 16). Let
F
be an
optimum UFPP solution. Then
F
can be partitioned into at most
2
k
top-drawn
sets (Lemma 32), so
w
(
F
A
)
1
2
k
w
(
F
)
.
5. Summary of the Main Approximation Algorithms
After the preparations in the previous sections we present our main
(7 +
)
-
approximation algorithm for UFPP. The algorithm calls the routines for small,
medium, and large tasks which were presented in Sections 3 and 4 and outputs the
returned set with maximum profit. After that, we show how to obtain a constant-
factor approximation algorithm with a much better running time of
O
(
n
4
log
n
)
.
Theorem 35. For every
>
0
there is a
(7 +
)
-approximation algorithm for the
UFPP problem which runs in polynomial time.
Proof. We assume that
0
<
1
2
(otherwise we simply set
:=
1
2
) and we de-
fine
:=
. Given an instance of the UFPP problem we divide the tasks into
small/medium tasks and large tasks. A task
i
is small or medium if
d
i
(1
)
b
(
i
)
and large otherwise. Due to Theorem 13 there is a
(3+
)
-approximation algorithm
for the small and medium tasks. Since
1
2
, for each large task
d
i
>
1
2
b
(
i
)
holds.
According to Theorem 34 there is then a
4
-approximation algorithm for the large
tasks. Returning the best solution of the two then yields a
(7 +
)
-approximation
algorithm for the set of all (small, medium, and large) tasks.
The running time of the above algorithm is dominated by the dynamic program
which is needed for handling the medium tasks, see Lemma 11. Unfortunately, the
exponent of the running time is quite large. However, in the following theorem
we show that already a moderate running time of
O
(
n
4
log
n
)
suffices to obtain a
constant factor approximation. The key is to avoid the expensive dynamic program
for the medium tasks. Instead, we divide the instance such that there are only small
and large tasks. At the cost of a higher approximation factor, this algorithm has a
much better running time.
Theorem 36. There is a
25
:
12
-approximation algorithm for the UFPP problem
with running time
O
(
n
4
log
n
)
.
Proof. We choose our constants differently than in the previous algorithm. We
define
=
:= 5
=
80
,
k
:= 9
,
:= 1
=k
,
`
:= 3
, and
q
:= 5
. We define a task
i
to be
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 29
: even edge
: odd edge
Independent set
Tasks
T
:
Left edges Right edgesUFPP instance:
instance
G
:
v
1
e
2
e
1
v
2
e
4
v
4
v
3
e
3
e
5
v
1
v
2
v
3
v
4
e
1
e
3
e
5
e
2
e
4
767676
2
m
+ 2
n
7 7 7 6 4 16 6 7 6 14
2
m
..... .....0 12
demand
= 1
demand
= 3
demand
= 2
demand
= 1
v
4
v
3
v
2
v
1
: short high-profit
: long high-profit
: low profit
capacity:
vertex:
corresponds to:
:
(
v
i
)=1
:
(
v
i
)=2
:
(
v
i
)=3
Path
P
:
Figure 6.1. An example of a graph
G
with coloring
and the
resulting instance ufpp
(
G
)
. (The demand of a task is indicated by
the width of its bar.)
small if
d
i
b
(
i
)
and large otherwise. Due to Lemma 9, for the small tasks there
is an
-approximation algorithm with
7
:
12
with running time
O
(
n
4
log
n
)
. For
the large tasks, due to Theorem 34, there is a
2
k
-approximation algorithm with a
running time of
O
(
n
4
)
. So the algorithm that returns the best solution of the two
is an approximation algorithm with a performance ratio of
+ 2
k
25
:
12
, and a
running time of
O
(
n
4
log
n
)
.
6. Strong NP-Hardness
In this section we prove that UFPP is strongly NP-hard for instances with de-
mands in
f
1
;
2
;
3
g
, using a reduction from Maximum Independent Set in Cubic
Graphs. Let
G;k
be an independent set instance of maximum degree 3:
G
6
=
K
4
is a graph with maximum degree 3 and the question is whether
G
contains an
independent set of size at least
k
. This problem is NP-hard [18] (even for cu-
bic graphs, in which all degrees are exactly 3). Let
V
(
G
) =
f
v
1
;:::;v
n
g
, and
E
(
G
) =
f
e
1
;:::;e
m
g
. By Brooks’ Theorem (see e.g. [23]),
G
is 3-colorable since
G
6
=
K
4
. Such a coloring can be found in polynomial time [23], so for our poly-
nomial transformation we may assume a proper 3-coloring
:
V
(
G
)
! f
1
;
2
;
3
g
is
given.
We now construct an equivalent instance of UFPP as follows, see Figure 6.1.
The path
P
has
2
m
+2
n
+1
vertices, labeled
0
;:::;
2
n
+2
m
. For the proofs below
it will be useful to distinguish four types of edges (called odd left, odd right, even
left and even right): an edge
f
i
1
;i
g 2
E
(
P
)
(with
1
i
2
n
+2
m
) is a left edge
if
i
2
m
and a right edge otherwise. It is an odd edge if
i
is odd, and an even edge
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 30
otherwise. Even left edges
f
2
k
1
;
2
k
g
(with
1
k
m
) will be associated with
edges
e
k
of
G
, and even right edges
f
2
k
1
;
2
k
g
(with
m
+ 1
k
n
+
m
) will be
associated with vertices
v
k
m
of
G
.
For every vertex
v
i
2
V
(
G
)
, introduce the following tasks: First, introduce one
long task with start vertex
0
and end vertex
2
m
+ 2
i
1
. Next, let
1
;:::;
d
be the indices of the edges incident with
v
i
, in increasing order. Introduce
d
+ 1
short tasks with the following start and end vertex pairs:
(0
;
2
1
1)
;
(2
1
;
2
2
1)
;:::;
(2
d
1
;
2
d
1)
;
(2
d
;
2
m
+ 2
i
)
. For all of these tasks for vertex
v
i
, the
demand is equal to
(
v
i
)
, and the profit is equal to
(
v
i
)
n
times the number of
odd edges used by the task. The aforementioned tasks will be called the high-profit
tasks (for
v
i
). Finally, for
v
i
we introduce one low-profit task from
2
m
+ 2
i
1
to
2
m
+ 2
i
with profit 1 and demand
(
v
i
)
.
Doing this for all vertices gives the tasks of the UFPP instance. It remains to
set the edge capacities of
P
:
For odd left edges
e
=
f
2
k
2
;
2
k
1
g 2
E
(
P
)
for integer
1
k
m
, set
u
e
=
P
v
2
V
(
G
)
(
v
)
.
For even left edges
e
=
f
2
k
1
;
2
k
g 2
E
(
P
)
for integer
1
k
m
, set
u
e
= (
P
v
2
V
(
G
)
(
v
))
1
.
For right edges
e
=
f
2
k
2
;
2
k
1
g 2
E
(
P
)
and
e
=
f
2
k
1
;
2
k
g 2
E
(
P
)
for integer
m
+ 1
k
n
+
m
, set
u
e
=
P
n
i
=
k
m
(
v
i
)
.
This gives the instance ufpp
(
G
)
of UFPP, to which we will refer in the remainder
of this section. With
T
we will denote the set of all tasks of ufpp
(
G
)
. With an
independent set
I
of
G
we associate a solution of ufpp
(
G
)
of the following form.
Definition 37. A set
F
T
of tasks of ufpp
(
G
)
is said to be in standard form if:
(1) For every
i
2 f
1
;:::;n
g
:
Either
F
contains the long high-profit task for
v
i
and the low-profit
task for
v
i
, but no short high-profit tasks for
v
i
,
or
F
contains all short high-profit tasks for
v
i
, but neither the long
high-profit task for
v
i
nor the low-profit task for
v
i
.
(2) For every
f
v
i
;v
j
g 2
E
(
G
)
,
F
does not contain both the long high-profit task
for
v
i
and the long high-profit task for
v
j
.
Now we will first show that any task set
F
that is in standard form is indeed
a feasible solution to ufpp
(
G
)
. Next we will show that the total profit of a solu-
tion
F
in standard form depends only (linearly) on the number of long high-profit
tasks in
F
. By the second property in the definition above, this corresponds to
an independent set in
G
. Subsequently we will show that any optimal solution
for ufpp
(
G
)
is in standard form. Together this will show that the instances are
equivalent (when considering them as decision problems with appropriately chosen
target objective values).
Proposition 38. Let
F
T
be in standard form. Then
F
is a feasible solution
for ufpp
(
G
)
.
Proof. Since
F
is in standard form, for every
v
i
2
V
(
G
)
, every edge of
P
is used by
at most one task for
v
i
. Therefore, for odd left edges
e
=
f
2
k
2
;
2
k
1
g 2
E
(
P
)
(with
1
k
m
), the capacity
u
e
=
P
v
2
V
(
G
)
(
v
)
is not exceeded. Similarly,
for odd right edges
e
=
f
2
k
2
;
2
k
1
g 2
E
(
P
)
(with
m
+ 1
k
n
+
m
),
the capacity
P
n
i
=
k
m
(
v
i
)
is not exceeded. Now we consider even right edges.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 31
Every edge
e
=
f
2
k
1
;
2
k
g 2
E
(
P
)
with
m
+ 1
k
n
+
m
is used by high-
profit tasks corresponding to the vertices
v
k
m
+1
;:::;v
n
, using a total capacity of
P
n
i
=
k
m
+1
(
v
i
)
. In addition, this edge is either used by one short high-profit task
for
v
k
m
, or by the single low-profit task for
v
k
m
, both with demand
(
v
k
m
)
.
This shows that for these edges the capacity bound is satisfied. Finally, consider
even left edges
e
=
f
2
k
1
;
2
k
g 2
E
(
P
)
with
1
k
m
. These correspond to
edges
e
k
2
E
(
G
)
. Let
e
k
=
f
v
i
;v
j
g
. Since
F
is in standard form, it cannot contain
high-profit tasks for both
v
i
and
v
j
. Note that no short high-profit tasks for
v
i
and
v
j
use the edge
f
2
k
1
;
2
k
g
. Hence the total capacity of
e
used by
F
is at most
max
n X
w
2
V
(
G
)
(
w
)
(
v
i
)
;
X
w
2
V
(
G
)
(
w
)
(
v
j
)
o
X
w
2
V
(
G
)
(
w
)
1 =
u
e
:
Proposition 39. Let
F
T
be a solution in standard form for ufpp
(
G
)
, which
contains
x
long high-profit tasks. Then
w
(
F
) =
x
+
P
n
i
=1
(
v
i
)
n
(
m
+
i
)
.
Proof. Recall that for high-profit tasks for a vertex
v
i
, the profit equals
(
v
i
)
n
times the number of odd edges used by the task. The long-high profit task for
v
i
(from
0
to
2
m
+2
i
1
) uses all odd edges
f
2
k
2
;
2
k
1
g
of
P
with
1
k
m
+
i
.
Hence if selected, it contributes
(
v
i
)
n
(
m
+
i
)
to the total profit. Together, the
low-profit tasks for
v
i
use exactly the same set of odd edges of
P
. So either way,
the high-profit tasks for
v
i
contribute
(
v
i
)
n
(
m
+
i
)
to the total profit. The single
low-profit task for
v
i
, with a profit of 1, is selected if and only if the long high-profit
task is selected. This yields the stated total profit.
These two propositions show that independent sets of
G
correspond to solutions
of ufpp
(
G
)
.
Lemma 40. If
G
has an independent set
I
with
j
I
j
=
x
, then ufpp
(
G
)
admits a
solution of profit
x
+
P
n
i
=1
(
v
i
)
n
(
m
+
i
)
.
Proof. Construct
F
by selecting the long high-profit task and the low-profit task for
v
i
if
v
i
2
I
, and all short high-profit tasks for
v
i
otherwise. Since
I
is an independent
set, this set
F
is in standard form. So by Proposition 38, it is a feasible solution to
ufpp
(
G
)
. Proposition 39 now gives the total profit.
Now we will show that any optimal solution to ufpp
(
G
)
is in standard form,
which will yield the converse of Lemma 40. We say that a solution
F
fully uses the
capacity of an edge
e
2
E
(
P
)
if
P
i
2
F
\
T
e
d
i
=
u
e
.
Proposition 41. Let
F
be an optimal solution for ufpp
(
G
)
. For every odd edge
e
2
E
(
P
)
,
F
uses the full capacity of
e
.
Proof. Recall that for every high-profit task with a demand of
d
, the profit equals
dnx
, where
x
is the number of odd edges used by the task. Hence the total profit of
high-profit tasks in a feasible solution
F
is bounded by
n
times the sum of capacities
of all such edges. This capacity sum is
m
n
X
i
=1
(
v
i
) +
n
X
k
=1
n
X
i
=
k
(
v
i
) =
n
X
i
=1
(
v
i
)(
m
+
i
)
:
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 32
Suppose that for at least one odd edge the full capacity is not used by
F
. The
low-profit tasks in
F
can in total only yield a profit of
n
, so then the total profit is
at most
n
n
X
i
=1
(
v
i
)(
m
+
i
)
1
+
n
=
n
n
X
i
=1
(
v
i
)(
m
+
i
)
:
Since there exists a feasible solution for ufpp
(
G
)
with strictly higher profit (Lemma 40),
this shows that
F
is not optimal.
Lemma 42. Every optimal solution
F
for ufpp
(
G
)
is in standard form.
Proof. First we will prove by (backward) induction that Property 1 of Definition 37
holds for an optimal solution
F
. The induction hypothesis will be that the following
claim holds for a given integer
x
. Note that for
x
= 0
, this claim (almost) yields
Property 1 of Definition 37.
Claim 1: An optimal solution
F
contains either
the long high-profit task for
v
i
and no short high-profit tasks for
v
i
with
end vertex
t
2
x
, or
all short high-profit tasks for
v
i
with end vertex
t
2
x
but not the long
high-profit task for
v
i
.
For the induction base (
x
=
n
+
m
), consider the odd edge
e
=
f
2
m
+2
n
2
;
2
m
+
2
n
1
g
. Its capacity is
(
v
n
)
, and the only tasks using
e
are the long (high-profit)
task for
v
n
, and one short (high-profit) task, both with demand
(
v
n
)
. Since
F
uses the full capacity of
e
(Proposition 41),
F
contains either this long task or the
short task, which proves the statement for
x
=
n
+
m
.
For the induction step, we prove Claim 1 for
x
=
k
, assuming that it holds for
x
=
k
+ 1
(the induction hypothesis).
First consider the case that
m
+ 1
k
n
+
m
1
. Consider the odd right
edge
e
=
f
2
k
2
;
2
k
1
g
. Let
e
0
=
f
2
k;
2
k
+ 1
g
. The capacity difference is
u
e
u
e
0
=
(
v
k
m
)
. All tasks using
e
0
use
e
as well. The only tasks using
e
but
not
e
0
are one long and one short task for
v
k
m
, both with demand
(
v
k
m
)
. So
F
must contain exactly one of these (Proposition 41), which proves Claim 1 for
k
m
+ 1
.
In the case that
k
=
m
, Claim 1 for
x
=
k
follows immediately from the induction
hypothesis since for all short high-profit tasks with end vertex
t
2
m
, it in fact
holds that
t
2
m
+ 2
.
Finally, consider the case that
0
k
m
1
. To prove Claim 1 it suffices to
show that for any short-high profit task with end vertex
2
k
t
2
k
+ 1
, that
corresponds to a vertex
v
i
, it is included in
F
if and only if
F
contains at least one
other short high-profit task for
v
i
. In fact, since there are no short high-profit tasks
with end vertex
t
= 2
k
, we only need to consider tasks with
t
= 2
k
+ 1
. Therefore,
consider the odd left edge
e
=
f
2
k;
2
k
+ 1
g
. Let
e
0
=
f
2
k
+ 2
;
2
k
+ 3
g
. To prove
the statement, we only need to consider tasks that use
e
but not
e
0
and tasks that
use
e
0
but not
e
. Let
e
k
+1
=
f
v
i
;v
j
g
(this is the edge of
G
associated with the
even edge between
e
and
e
0
). The only tasks that use
e
0
but not
e
are one short
high-profit task for
v
i
of demand
(
v
i
)
, and one short high profit task for
v
j
of
demand
(
v
j
)
. Similarly, there are two such tasks that use
e
but not
e
0
, of demand
(
v
i
)
and
(
v
j
)
. Since
is a proper coloring of the vertices of
G
,
(
v
i
)
6
=
(
v
j
)
.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 33
Since
F
fully uses the capacity of both
e
and
e
0
, and
u
e
=
u
e
0
,
F
includes a short
task for
v
i
that uses
e
if and only if it includes a short task for
v
i
that uses
e
0
, and
an analog statement holds for
v
j
. Since there are no tasks with end vertex
t
= 2
k
,
this proves Claim 1 for
0
k
m
1
.
For all choices of
k
we have now proved the induction step, so by induction,
Claim 1 holds for
x
= 0
. We conclude that in an optimal solution
F
, for every
v
2
V
(
G
)
, either only the long high-profit task is selected, or all short high-profit
tasks are selected and not the long one. One can always add the single low-profit
task for
v
i
to
F
, whenever no short high-profit tasks for
v
i
have been selected in
F
,
so this proves Property 1 of Definition 37 for
F
.
Now we will prove that Property 2 of Definition 37 also holds for the optimal
solution
F
. We will prove that the vertices of
G
for which
F
contains a long high-
profit task form an independent set in
G
. More precisely, for any edge
f
v
i
;v
j
g 2
E
(
G
)
,
F
does not contain both the long high-profit task for
v
i
and the long high-
profit task for
v
j
. Let
e
k
=
f
v
i
;v
j
g
(with
k
2 f
1
;:::;m
g
). According to our
construction this edge is associated with an even left edge
e
=
f
2
k
1
;
2
k
g 2
E
(
P
)
of ufpp
(
G
)
. The capacity of
e
is one less than that of its adjacent odd edge
e
0
=
f
2
k
2
;
2
k
1
g
, and yet the capacity of
e
0
is fully used by
F
(Proposition 41).
The only tasks using
e
0
but not
e
are a short task for
v
i
, and a short task for
v
j
. So
for at least one of
v
i
and
v
j
,
F
includes this short task. Since we already showed in
the first part of the proof that
F
cannot contain both a long high-profit task and
a short high-profit task for the same vertex
v
k
, it follows that for at least one of
v
i
and
v
j
,
F
does not contain the long task. Hence Property 2 of Definition 37 also
holds for
F
, and thus
F
is in standard form.
Summarizing, any optimal solution to ufpp
(
G
)
corresponds to an independent
set of
G
:
Lemma 43. If ufpp
(
G
)
admits a solution of profit at least
x
+
P
n
i
=1
(
v
i
)
n
(
m
+
i
)
,
then
G
has an independent set of size at least
x
.
Proof. Consider an optimal solution
F
, so
w
(
F
)
x
+
P
n
i
=1
(
v
i
)
n
(
m
+
i
)
. By
Lemma 42,
F
is in standard form. Let
I
be the set of vertices
v
i
of
G
for which
F
contains the long high-profit task. Since
F
is in standard form,
I
is an independent
set of
G
. Proposition 39 shows that
w
(
F
) =
j
I
j
+
P
n
i
=1
(
v
i
)
n
(
m
+
i
)
. It follows
that
j
I
j
x
, so
I
is the desired independent set.
Our construction used only polynomially bounded numbers (profits, demands
and capacities), so even if the numbers are encoded in unary, this is a polynomial
transformation. For this it is also essential that a 3-coloring
of
G
can be found
in polynomial time [23]. Lemmas 40 and 43 show that
G
has an independent
set of size at least
x
if and only if
P;F
admits a solution of profit at least
x
+
P
n
i
=1
(
v
i
)
n
(
m
+
i
)
. Since the problem of finding a maximum independent set
is NP-hard when restricted to graphs of maximum degree 3 [18], this proves that
UFPP is strongly NP-hard. The problem obviously lies in NP, which yields:
Theorem 44. UFPP is strongly NP-complete when restricted to instances with
demands in
f
1
;
2
;
3
g
.
In fact, with a small addition we can show that the problem remains NP-complete
when all edge capacities are equal. Let
u
m
be the maximum capacity used in the
instance ufpp
(
G
)
constructed above, and let
X
=
n
+
P
n
i
=1
(
v
i
)
n
(
m
+
i
)
be an
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 34
upper bound on the profit of any solution (Lemma 43). Note that
X
is bounded
by a polynomial in
n
. For every edge
e
=
f
k;k
+ 1
g
of
P
with
u
e
< u
m
, we can
increase the capacity to
u
m
, and introduce
u
m
u
e
dummy tasks: tasks from
k
to
k
+1
with demand
1
and profit
X
. For a polynomial transformation we must ensure
that the number of dummy tasks is polynomially bounded. Given an instance with
demands in
f
1
;
2
;
3
g
, a maximum capacity of
3
n
suffices, so all capacities
u
e
>
3
n
can be scaled down to
3
n
. Hence, on each edge at most
O
(
n
)
dummy tasks are
introduced. Since the number of edges is bounded by
O
(
n
)
, at most
O
(
n
2
)
dummy
tasks with profit
X
and demand
1
need to be added. In an optimal solution, clearly
all of the dummy tasks are selected, so this yields an equivalent instance. Therefore
the previous theorem can be strengthened to:
Theorem 45. UFPP is strongly NP-complete when restricted to instances with
demands in
f
1
;
2
;
3
g
, where all edges have equal capacities.
7. Conclusion and Discussion
In this paper we proved strong NP-hardness for UFPP with uniform capacities
(RAP), even if the input is restricted to demands in
f
1
;
2
;
3
g
, and gave the first
constant factor polynomial time approximation algorithm for UFPP. The main
remaining open question is whether there exists a PTAS for RAP or UFPP, or
whether the problems are APX-hard. Due to our hardness result it would be
interesting to know whether the special case of demands in
f
1
;
2
g
is also NP-hard,
or admits a polynomial time algorithm. Note that if the demands are uniform, the
problem can be solved in polynomial time with a small extension of the algorithm by
Arkin and Silverberg [2]. Since finding a PTAS for UFPP seems very challenging,
it would be interesting to see whether the factor of
7 +
can be improved.
In this paper we did not consider other graph classes than the path. Can our
techniques be used for other graph classes? In particular, extending the algorithm
to trees is not straightforward, since Lemma 3 does not apply in this case.
Finally, it may be interesting to study whether our new techniques for find-
ing maximum non-overlapping sets of rectangles can be applied to other rectangle
packing problems.
References
[1] P. K. Agarwal, M. van Kreveld, and S. Suri. Label placement by maximum independent set
in rectangles. Computational Geometry, 11:209 – 218, 1998.
[2] E. M. Arkin and E. B. Silverberg. Scheduling jobs with fixed start and end times. Discrete
Appl. Math., 18:1–8, November 1987.
[3] N. Bansal, A. Chakrabarti, A. Epstein, and B. Schieber. A quasi-PTAS for unsplittable flow
on line graphs. In Proceedings of the thirty-eighth annual ACM symposium on Theory of
computing, STOC ’06, pages 721–729, New York, NY, USA, 2006. ACM.
[4] N. Bansal, Z. Friggstad, R. Khandekar, and M. Salavatipour. A logarithmic approximation for
unsplittable flow on line graphs. In SODA ’09: Proceedings of the twentieth Annual ACM-
SIAM Symposium on Discrete Algorithms, pages 702–709, Philadelphia, PA, USA, 2009.
Society for Industrial and Applied Mathematics.
[5] Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, and Baruch Schieber.
A unified approach to approximating resource allocation and scheduling. In Proceedings of the
thirty-second annual ACM symposium on Theory of computing, STOC ’00, pages 735–744,
New York, NY, USA, 2000. ACM.
[6] R. Bar-yehuda, M. Beder, and Y. Cohen. Approximation algorithms for bandwidth and stor-
age allocation, 2005.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 35
[7] V. Bonifaci, A. Marchetti-Spaccamela, and S. Stiller. A constant-approximate feasibility test
for multiprocessor real-time scheduling. In Dan Halperin and Kurt Mehlhorn, editors, Al-
gorithms - ESA 2008, volume 5193 of Lecture Notes in Computer Science, pages 210–221.
Springer Berlin / Heidelberg, 2008.
[8] G. Calinescu, A. Chakrabarti, H. J. Karloff, and Y. Rabani. Improved approximation algo-
rithms for resource allocation. In Proceedings of the 9th International IPCO Conference on
Integer Programming and Combinatorial Optimization, pages 401–414, London, UK, 2002.
Springer-Verlag.
[9] A. Chakrabarti, C. Chekuri, A. Gupta, and A. Kumar. Approximation algorithms for the un-
splittable flow problem. In Proceedings of the 5th International Workshop on Approximation
Algorithms for Combinatorial Optimization, APPROX ’02, pages 51–66, London, UK, 2002.
Springer-Verlag.
[10] P. Chalermsook and J. Chuzhoy. Maximum independent set of rectangles. In Proceedings
of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’09, pages
892–901, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics.
[11] C. Chekuri, M. Mydlarz, and F. Shepherd. Multicommodity demand flow in a tree and
packing integer programs. ACM Trans. Algorithms, 3:27, 2007.
[12] B. Chen, R. Hassin, and M. Tzur. Allocation of bandwidth and storage. IIE Transactions,
34:501–507, 2002.
[13] A. Darmann, U. Pferschy, and J. Schauer. Resource allocation with time intervals. Theor.
Comput. Sci., 411:4217–4234, November 2010.
[14] C. W. Duin and E. Van Sluis. On the complexity of adjacent resource scheduling. J. of
Scheduling, 9:49–62, February 2006.
[15] F. Eisenbrand and T. Rothvoß. A PTAS for static priority real-time scheduling with resource
augmentation. In Automata, Languages and Programming, volume 5125 of Lecture Notes in
Computer Science, pages 246–257. Springer Berlin / Heidelberg, 2008.
[16] T. Erlebach, K. Jansen, and E. Seidel. Polynomial-time approximation schemes for geometric
graphs. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms,
SODA ’01, pages 671–679, Philadelphia, PA, USA, 2001. Society for Industrial and Applied
Mathematics.
[17] A. M. Frieze and M. R. B. Clarke. Approximation algorithms for the
m
-dimensional
0
1
knapsack problem: worst-case and probabilistic analyses. European J. Oper. Res., 15(1):100–
109, 1984.
[18] M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph prob-
lems. Theoret. Comput. Sci., 1(3):237–267, 1976.
[19] S. Heinz and J. Schulz. Explanation algorithms for the cumulative constraint: An experimen-
tal study. Technical report, TU Berlin, 2011.
[20] S. Khanna, S. Muthukrishnan, and M. Paterson. On approximating rectangle tiling and
packing. In Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms,
SODA ’98, pages 384–393, Philadelphia, PA, USA, 1998. Society for Industrial and Applied
Mathematics.
[21] T. W. Lam and K. K. To. Trade-offs between speed and processor in hard-deadline sched-
uling. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms,
SODA ’99, pages 623–632, Philadelphia, PA, USA, 1999. Society for Industrial and Applied
Mathematics.
[22] S. Leonardi, A. Marchetti-Spaccamela, and A. Vitaletti. Approximation algorithms for band-
width and storage allocation problems under real time constraints. In Proceedings of the 20th
Conference on Foundations of Software Technology and Theoretical Computer Science, FST
TCS 2000, pages 409–420, London, UK, 2000. Springer-Verlag.
[23] L. Lovász. Three short proofs in graph theory. J. Combinatorial Theory Ser. B, 19(3):269–
271, 1975.
[24] F. Nielsen. Fast stabbing of boxes in high dimensions. Theoretical Computer Science, 246(1-
2):53 – 72, 2000.
[25] J. B. Orlin. A faster strongly polynomial minimum cost flow algorithm. In Operations Re-
search, pages 377–387, 1988.
[26] C. Phillips, C. Stein, E. Torng, and J. Wein. Optimal time-critical scheduling via resource
augmentation. Algorithmica, 32:163–200, 2008. 10.1007/s00453-001-0068-9.
A CONSTANT FACTOR APPROXIMATION FOR UNSPLITTABLE FLOW ON PATHS 36
[27] C. A. Phillips, R. N. Uma, and J. Wein. Off-line admission control for general scheduling
problems. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algo-
rithms, SODA ’00, pages 879–888, Philadelphia, PA, USA, 2000. Society for Industrial and
Applied Mathematics.
[28] V. V. Vazirani. Approximation algorithms. Springer-Verlag, Berlin, 2001.
