MATHEMATICS OF OPERATIONS RESEARCH
Nr,.
V o l 10.
I . Fehruary 1985
Pmred rn U.S A
A TWO-RESOURCE ALLOCATION PROBLEM SOLVABLE
IN LINEAR TIME*
NIMROD MEGIDDOt$ AND TETSUO ICHIMORI$
The allocation problem discussed here is as follows. The processing time of a task is a linear
function c-ax-by of amounts x , y of resources allocated to it. where t . a , h are positive
constants. Given the amounts X and Y of available resources, we wish to allocate them among
n independent tasks so as to minimize the maximal completion time. We solve this problem in
llnear time.
Introduction. The complexity of the linear programming problem is a central
question in the interface between operations research and computer science. It is still
an open question whether an m x n problem can be solved within a polynomial
number p(m, n) of arithmetic operations. Another direction of research is that of
exploring the complexities of structured linear programming problems (see [M 1, M2,
M31). It turns out that for many subproblems there exist algorithms which are more
efficient than the simplex algorithm and investigating such algorithms may eventually
lead to an alternative for the simplex algorithm in the general case.
In this paper we present a linear-time algorithm for a class of linear programming
problems which may be described as follows.
Suppose we have n independent "tasks" denoted 1,2, . . . , n, whose processing times
depend on the amounts of two resources allocated to them. More specifically, assume
we have X units of the first resource and Y units of the second resource. Given the
initial time t,, if we allocate x, units of the first resource and y , units of the second
resource to task i, then task i will process in T, = max{ t, - a,x, - b,y,, d l ) time units
( t , ,a,, b,, dl > 0). Suppose we wish to minimize makespan [B], given all tasks start at
time zero. Then our problem is to minimize Max{ T , ) subject to E x , = X , C y , = Y
and x,, y, > 0. It is easy to see that it is sufficient to minimize Max{ t, - a,x, - b,y,).
For some references on resource allocation consult [El, [GM] and [KIMI], [KIM2].
Recent results of Megiddo [Ml],[M2] establish that whenever the number of
variables (or, equivalently, the number of constraints) is fixed, a linear programming
problem is solvable in linear time. However, the problem we discuss in this paper does
not fall in this category. The methods we use are related to those used in [Ml, M2].
Our problem is also related but not equivalent to the multiple-choice linear knapsack
problem [IHTI], [Zl] recently revisited by Dyer [D3] and Zemel [Z2], the latter two
stemming from the results independently obtained by Megiddo [MI], [M2] and Dyer
[Dl],[D2]. Thus, it turns out. that these new methods lead to better algorithms than
previous ones. Apparently, the "sorting" step can be avoided in these special linear
programming problems and successive reductions in the size of the problem yield
*Received February 22, 1983; revised July 27, 1983.
AMS 1980 subjec! classification. Primary: 90C08. Secondary: 65K05.
OR/ MS Index 1978 subject classification. Primary: 637 Programming/linear/aIgorithms.
Key words. Resource allocation, linear programming with special structure, linear programming algorithms.
Carnegie-Mellon University.
$The work of Professor Megiddo was supported in part by the National Science Foundation under Grants
ECS-8218181 and ECS-8121741.
Hiroshima University.
0364-765X/85/ 1001/0007$01.25
Copyright 0 1985, The Institute of Management Sciences/Operat~onsResearch Soc~etyof America
8
N I M R O D MEGIDDO & TETSUO ICHIMORI
better performance. In a certain sense these methods are "greedy." The methods may
also apply to linear programs arising in preemptive scheduling problems where linear
programming is a fundamental tool.
Finally, we note that even though our linear-time argument follows from finding
medians in linear time (which may not be practical), the method is very practical if
instead of the exact median we pick a random element (or the median of a random
sample of three).
Some formulation considerations. We solve the following problem
minimizemaximum
X.
Y
{c,-a,x,-b,y,)
ISrSn
x,,y,20
where X, Y, a,, b,, c, > 0, i
programming problem:
minimize
x,
=
t
y. 1
s.t.
xx,=X,
xy,=Y,
r=l
,=I
(PI)
( i = l , . . . , n),
1, . . . , n. The problem can be formulated as a linear
s.t
t
+ aix, + b,yi 2 ci
( i = I,
. . . , n),
(P2)
( i = l , . . . , n).
xi,y,ZO
We will concentrate on the dual problem:
n
maximize
2 , U ,D
cizi+ Xu
+ Yv
i= l
u+aiziIO
(i=l,
. . . , n),
v+biziSO
( i = 1,
. . . , n),
n
Czi=l,
(i=l,
zi20
. . . , n).
i= l
Let us consider the latter as the problem of maximizing a function f(u,v) of two
variables, namely
(assuming Max 0 = - a).It is easy (and well known) to evaluate f(u, v) in O(n) time.
This can be accomplished by searching (employing repeated median-finding) for the
optimal value of the dual variable associated with the equality constraint. However, we
will maximize f(u, v ) in O(n) time. The procedure is based on repeated reduction in the
size of the problem.
An overview of the algorithm. The function f(u, v) is piecewise linear and concave.
In order to understand the algorithm for maximizing f, we first discuss the piecewise
linear structure of this function. The problem
maximize
2 C,Z,
i= l
s.t.
2 z, = 1,
i= l
TWO-RESOURCE ALLOCATION
9
PROBLEM SOLVABLE IN LINEAR TIME
is easy a n d its optimal solution can be described as follows. Assume, without loss of
generality, that c , 2 c, 2 . - 2 c, a n d C:=,Z, 2 1. Then there is a unique k ,
0 k k k n such that ~ f ,Zi
= 5 1 < ~ f t (assuming,
i ~ , for convenience, Z,,+ = 2). The
solution is then z = Z,, i = 1, . . . , k, Z k + I= 1 - C f = , Z , a n d zi = 0, i = k 2, . . . , n.
It follows that f(u, v) has the following description:
,
+
for u a n d
t.
such that
The domains of linearity of f(u,v) are as shown in Figure 1. The lines forming these
domains are as follows. First, there are the lines u / a j = v/b,, i = 1, . . . , n. Along any
line v = a u ( a > 0) the function f(u,u) breaks as we describe below. Let LE = j i : b,
5 a a i ) and G = { i : b , > aa,}. Thus, for iE LE (assuming v = au), - u / a , S - v / b , ,
and for i E G, - u/a, > - v/b,. A critical value of u on our line must be such that for
some k (1 S k S n) - u . C f = , m i n ( l / a , , a / b , ) = 1, i.e.,
c!=
However, given k, the curve Ck = {(u, v) :
,min(- u/a,, - v / b,) = I ) (which has
the form of a broken line) breaks only a t points where u/a, = v/b, for some i,
1 5 i ik. This implies that the map of linearity domains of f(u,v) is as shown in
Figure 1. See also Figure 2 for the curves Ck .
In the subsequent sections we develop procedures for the following problems. Let
(u*,u*) denote a maximum of f(u,v). First, given a straight line o = a u we will
recognize in O(n) time whether v* < au*, v* = au*, or u* > au*. Secondly, given one
10
NIMROD MEGIDDO & TETSUO I C H l M O R l
of the curves C, ( 1 5 k S n), we will recognize in O(n) time the position of (u*.v*)
relative to C,, i.e., whether ~ f , , m i n ( - u*/a,, -v*/b,) is less than, equal to, or
greater than 1.
The tests we have just defined enable us to reduce the problem in the following way.
First, assume c, L c, L . . . >= cn. This assumption is only for the convenience of
notation. We start by finding the median c,,/, (assume, for convenience, n is even) and
identifying the sets ( c , , . . . , c,,,~), { c , / ~ +,, . . . , c,,). W e now test the curve C,,/2. If
we find that z:i2,min( - u*/a,, - u*/bi) L 1 then the corresponding solution z*
= (zy, . . . , z,*) must satisfy z: = 0, i = n / 2
I, . . . , n. W e thus reduce problem (P3)
to the same one with n / 2 replacing n. The case of an equality is particularly easy since
then we actually obtain u* and v*. If z:i2,min(- u*/a,, -u*/b,) < 1 then z: =
min(- u*/ai, - v*/bi), i = 1, . . . , n/2. In this case our problem is reduced to the
following:
+
n/2
maximize
clzi+ Xu
i=n/2+1
+ Yv + C cimin(-
u / a i , - u/b,)
i= l
0 5 zi 5 min(- u/a, , - v/bi)
( i = n/2
(P5)
+ 1, . . . , n).
This is obviously more complicated than problem (P3) with n / 2 variables since both
the function and sum of ti's contain a piecewise linear function of u and v. However,
we also work on the front of this complication in the following way. We find the
median a, of the ratios b,/ai, i = I, . . . , n/2. Next, we test the line v = an,u, i.e.,
determine whether v* < curnu*, v* = a,u*, or v* > a,,u*. Assume, for example, v*
h a,u*. In this case for every i such that b,/a, h a , we have - u*/a, 2 - v*/b,.
Denoting T = { 1 5 i 5 n/2 : bl/a, 2 a,} we have to solve an easier problem:
maximize
i=n/2+1
ciz, + Xu
+
v
+
x
cimin( - u/a, , - v/b,)
(P6)
ie T
This problem is obviously not harder than
maximize
C cir,+ Xu +
ie T
(Y
-
2
;ET
1
2 a
bi
c.
s.t.
0I
z, 5 min{ - u / a i , - v/bi)
x
ie T
z, = I
+ ( CT I /b,)c.
(P7)
iE
(i @ T).
However, the latter is of "size" not greater than 3/4 of the original problem since
I TI 2 n/4. The only difference is the linear term on the right-hand side of the
constraint on the sum of zj's. However, the latter does not affect our ability to test lines
a n d curves as described above in linear time. The fact that the problem is reduced with
a linear-time effort to a problem of the same kind whose size is not more than 3/4 of
the original one implies that the total effort is linear in n. In view of the discussion
above we need to consider a more general problem obtained by adding a linear
TWO-RESOURCE ALLOCATION PROBLEM SOLVABLE IN LINEAR TIME
11
function of u and v to C ~ = , z ,however,
;
we later discuss the solution of problems of
the type of (P8) below only when they are derived from the original problem.
x
n
maximize
z , U ,U
c,z,+ Xu
minimize t
+ Bv = 1,
(P8)
( i = 1, . . . , n ) ,
(P9)
z,+ Au
i= l
< 0). The dual of
X.
s.t.
i= l
( i = I, . . . , n ) ,
( i = 1,. . . , n ) ,
( i = I, . . . , n )
u+a,ziSO
v+b,z,IO
tiPO
(where A , B
x
n
+ Yv
the latter is:
s.t. t
1'. I
+ a,x, + b,y, 2 c,
( i = l , . . . , n).
xi,yi20
Testing a ray. In this section we develop a procedure for testing the following:
Given the function
f ( u , v ) = Xu
n
+ Yv + max
C,Z,
i=
l
:
2 ti = I
-
AU - Bv,O 5 zi
i= 1
and a ray v = au ( a > 0), recognize whether the maximum of f, (u*,v*), satisfies
v* < au*, v * = au*, or v* > au*.
The procedure starts by maximizing f on the ray v = au. Several quantities defined
later are dependent on a ; however, we omit a from their notational description for
simplicity. Thus, we now consider the following problem
maximize
2. U
x
i= l
c,z,+ ( X
+ aY)u
s.t.
ti=1 -
( A + aB)u,
i= l
P O )
This problem is quite easy to solve. Consider the function
g(u) = (X
x
n
+ a Y ) u + max
cizi :
i= l
zi = 1 - ( A
+ aB)u,
i= l
The function g ( u ) is piecewise linear and concave. Its breakpoints are where
- u ~ : Imin(l
,
/ a , , a / b i ) = I - ( A + a B ) u for some k , 0 S k 5 n (assuming c , 1 . . .
L c,). Let u0 denote a maximum of g. Given any value u' of u we can determine
whether u' < uO,u' = uO,or u' > u0 in O ( n ) time as follows. First, compute g(u'). This
is essentially like solving (P4). Let k be such that
12
N I M R O D M E G I D D O & TETSUO ICHIMORI
(assume for convenience rnin(l/a,+,,a/b,+ ,) = a).We know that such k can be
found in O ( n ) time (even if the el's are not sorted) by repeated median finding.
Knowing the critical index k, we can express g(uf) as follows:
,
+
(assuming c,+ = 0). If - u ' ~ t = ~ m i n ( l / a ~ , a / b<, )1 - ( A aB)uf then g is linear in
the neighborhood of u', with a slope of X a Y - ( A aB)c, + ,(c, - c, ,)
min(1 /a,. a/b,). The sign of this slope tells us whether u' < uO, u' = uO,or u' > uO.If
- u'Cl, ,min(l /a,, a/b,) = 1 - (A
aB)u' then g breaks at u'. The left-hand side
derivative at u' equals the slope we have calculated in the previous case (since any
decrease in the value of u, which is assumed to be negative in any case, takes us back
to that previous case). The right-hand side derivative is similar but with k - 1
replacing k, i.e.,
+
+
, c!=
+
+
X
+aY
k-l
-
(A
+ aB)cA- 2 (ci - ck)min(l/al,a/b,).
i= l
Given the one-sided derivatives of g at u', it is easy to recognize whether u' < uO,
u' = uO,or U' > uO.
Now, maximizing g(u) is carried out by a binary search. We first let u' be equal
, a 1/ b-, )
to the median of critical values of u, i.e., where - u ~ ~ ~ ~ , m i n ( l / a ~ =
(A + aB)u; namely,
If u' = uO then we are, of course, done. If u' > u0 then our maximization problem is
now reduced to a similar problem with only n/2 variables:
fl/2
maximize
alzi+ (X
I=
+ aY )u
fl/2
zi= I - (A
s.t.
l
+ a B )u,
i= l
If u' < uOthen the variables z , , . . . , z,,, are determined to be equal to their respective
upper-bounds at the optimal solution of the problem corresponding to g(uO).In other
words, our problem is then reduced to:
fl/2
maximize
cjzi+ X
i=n/2+ 1
+ aY
-
I
x c,min(l/o,. a/bl) u
i= 1
OIz,Su.min(l/ai,a/bi)
( i = n / 2 + 1 , . . . , n).
It follows that the maximum of g(u) is found with a total effort of O(n).
We now turn to the question of recognizing the side of the ray v = au which
contains the maximum (u*, v * ) of f(u, v ) . It follows from the concavity of f(u, v) that it
is sufficient to look in the neighborhood of the point (uO,auO).More specifically,
denote h(a) = Max,f(u, au). We are seeking Maxh(a). Knowing that h increases at a
TWO-RESOURCE ALLOCATION PROBLEM SOLVABLE I N L I N E A R T I M E
13
tells us that u*/u* > a, and knowing that h decreases at a tells us that u*/u* < a ; if h
is maximized at a then u*/u* = a so that u* = u0 and u* = auO. The problem is
therefore to determine the behavior of h at a. Consider first the dependence of u0 on a .
Since g(u) is piecewise linear it follows that it attains its maximum, uO,at a breakpoint.
In other words, there exists k, 0 S k S n such that
Hence,
k
It is only a technical matter to determine the one-sided derivatives with respect to a of
the quantity on the right-hand side of the latter equation. This finally tells us the side
of the ray on which (u*, u*) lies.
Testing a curve. We describe in this section a procedure for determining the side of
the curve
which contains (u*,u*). We describe a procedure that, given (u,u), determines if
= u/a,, - u/ b,) is less than, equal to, or greater than 1. To that
Au + Bu + ~ f ,min(end, consider the dual problems (P8), (P9). Let t* denote their optimal value. We first
note that if t* < c, (1 S i S n) then at an optimal solution either xi > 0 or y, > 0. By
the complementary slackness conditions, we have either u + a,z, = 0 or u + bizi = 0. In
other words, t* < c, implies zi = min(- u/a,, - ulb,). Now, consider the following
problem:
s.t. t + aixi + by,
minimize t
x,
y, r
=
ci
(i = I, . . . , n),
(PI 1)
+ Bu = 1,
(P12)
and its dual
n
maximize
2, u , 1)
cizi+ Xu
+ Yu
x
n
s.t.
zi+ Au
i= 1
i= 1
u+aiziSO
u + biziSO
( i = 1, . . . , n),
( i = I,. . .,n).
We will later discuss an algorithm for (P11). However, we first argue that solving (P11)
is the key to testing a curve. Let us denote by cx",Y,F, ",u Coptima1 values for
(PI 1)-(P12) and let t*, x*, y*, z*, u*, U* denote optimal values for (P8)-(P9). Since
(P11) is more constrained than (P9), it follows that t"> t*. Suppose t"< cn (and recall
that cn = min{ci : i = 1, . . . , n)). It follows that t* < cn and hence for every i,
i = 1, . . . , n, either x,? > 0 or y,? > 0. By complementary sla_ckness, we haye z* =
min(- u * / a , , - v*/bi), i = 1, . . . , n . Conversely, suppos_e t 2 c,. Since t = c, anZn- b z n , our assumption here is equivalent to either t = c, or (P11) infeasible.
Consider, again, (P8)-(P9). If these problems are derived from the original (P2)-(P3)
(hence, the values of n as well as other indexes may have been updated) then,
14
NIMROD M E G ~ D D O& TETSUO ICHIMORI
necessarily, u*, v* < 0. (Here u* and u* are identical to those of (P2)-(P3).) This is
because in (P3) we have z: > 0 for some i . Now, if t* < c, (in (P8)) then we know that
z* = min(- u*/a,, - o*/ b,) > 0, i = 1, . . . , n. Using complementary slackness again,
we have t* + six: + by: = c,, i = 1, . . . , n. The interesting conclusion is that t* < c,
implies (t*,x*, y*) is feasible not only in (P9) but also in (P11) and therefore
t = t* < c,.
*
Equivalently, if t 2 c, then t* B c,. Moreover, we may assume in this case x,* = y,*
= 0. This is true not only for n but also for every i such that c; = c,.
The algorithmic implications of the above observations can now be described. Given
that we need to test the curve C,, solve the problem (P12) with n = k. In other words,
we restrict z, = 0 for i > k. Let ;denote the optimal value. If t"< c, then we know that
2: = min(- u*/a,, - v*/b,) for i = 1, . . . , k. If t L c, then for all i such that c, 5 c,,
x: = y,? = 0. In this case, denoting G = { i : c, > c,), problem (P9) reduces to
-
minimize t
x.
s.t. t
y, t
and the dual is
maximize
Z'U'U
x
iEG
+ a,xi + b,yi > C,
cizi+ XU + Yv,
x
s.t.
(iE G)
zi+ A U + BV = 1,
iEG
0
( i E G).
Thus, testing a curve can be accomplished by solving (PI 1).
We finally consider solving (P11). Actually, we are interested only in ;so we may,
instead, solve (P12). Consider a simplified problem
cizi
maximize
2 zi= 1,
st.
i= l
i= l
z,SZ,
( i = l , . . . , n).
The analysis of (P13) is easy: If C:= ,Z, < 1 then the problem is infeasible. Otherwise
(assuming c,, = min{c, : i = 1, . . . , n)), an optimal solution is zi = Z , , i = 1 , . . . , n 1, z, = 1 - C:~,'Z,, the optimal value being equal to c, + C ~ ~ , ' (-c c,)Z,.
,
It now
follows that in (P12) Au + Bv C:= ,min(- u/a,, - v/b,) 2 1. The optimal z,-values
given u and v are therefore (in (P12)):
+
and the objective function value is
$(u, v) = ( X - Acn)u + ( Y - Bcn)o
+ c, +
l
n-
(c, - c,)min(- u/a, , - u/b,).
i= l
Now problem (P12) is equivalent to
maximize +(u,v)
s.t. Au
+ Bv +
n
min(- u/a,, - v/bi) 2 1.
i= l
(P14)
TWO-RESOURCE ALLOCATION PROBLEM SOLVABLE I N LINEAR T I M E
15
It is essential to observe that +(u,v) is concave. By maximizing +(u,z;) on any straight
line we can tell (by looking in the neighborhood of the relative maximum) on which
side of the line the global maximum lies. We now apply this idea to a line of the form
v = a u where a > 0. Maximizing on such a line amounts to
It is only a technical matter to determine at the maximum fi = fi(a) whether the
function +(a) = +(E(a), aU(a)) increases, decreases, or attains its maximum. This lets
us maximize +(u,v) in O(n) time as follows. First, find the median of the ratios b,/a,,
i = 1, . . . , n. Call it a, and determine the behavior of $(a) at a,. If, for example,
+(a) is increasing at a, then at the maximum E (Z > a,) we have l / a , < Z/bi for all i
such that a, 2 b,/a,. Let L = { i : b,/a, < a,}, E = { i :bi/ai = a,) and G = ( i : b,/a,
> a,,). Note that ( L U E ( , ( GU E l 2 n/2. In the present case we can update the
function +(u, 0):
!
n-
+ ( u , v ) = X - Acn -
l
2l
!
(c, - c,,)/a, u + ( Y - Bcn)v+ c,
i=
iELUE
n- 1
+ 2 (ci - cn)min(- u / a i ,
- v/b,).
I =l
I€ G
Moreover, we need to maximize +(u, v) subject to
If +(a) attains its maximum at a, then we are done. The case of +(a) decreasing at
a, is handled in an analogous way. In any case, with an O(n) effort we reduce (P4) to
the same problem with no more than n/2 critical ratios, accumulating at least n/2
functions in the linear components. This establishes a linear-time algorithm for (P14).
References
Baker, K. (1974). Introduction to Sequencing and Scheduling. Wiley.
Dyer, M. E., Two-Variable Linear Programs Are Solvable in Linear-Time. Undated manuscript,
Teesside Polytechnic.
-.
A Linear-Time Algorithm for Three-Variable Linear Programs. Undated manuscript,
Teesside Polytechnic.
An O ( n ) Algorithm for the Multiple-choice Knapsack Linear Program. Undated
manuscript, Teesside Polytechnic.
Everett, H. (1963). Generalized Lagrange Multiplier Method for Solving Problems of Optimum
Allocation of Resources. Oper. Res. 11 399-417.
Galil, Z. and Megiddo, N. (1979). A Fast Selection Algorithm and the Problem of Optimum
Distribution of Effort. J . Assoc. Comput. Mach. 26 58-64.
Ibaraki, T., Hasegawa, T., Teranaka, K. and Iwase, J. The Multiple-Choice Knapsack Problem. J .
Oper. Res. Soc. Japan 21 59-64.
Katoh, N., Ibaraki, T. and Mine, H. (1979). Algorithms for a Variant of the Resource Allocation
Problem, J . Oper. Res. Soc. Japan 22 287-300.
--, and --. (1981). An Algorithm for the K-Best Solutions of the Resource
Allocation Problem. J . Assoc. Comput. Mach. 28 752-764.
16
[MI]
[M21
[M31
[Zl]
V21
NIMROD MEGIDDO & TETSUO ICHIMORI
Megiddo, N. (1984). Linear Programming in Linear-Time When the Dimension Is Fixed. J. Assoc.
Compur. Mach. 31 1 14- 127.
-. (1983). Linear-Time Algorithms for Linear Programming in R~ and Related Problems.
SIAM J. Comput. 12 759-776. (Also in the Proceedings of the 23rd Annual IEEE Symposium on
Foundations of Computer Science (1982), pp. 329-338.
--. (1983). Towards a Genuinely Polynomial Algorithm for Linear Programming. SIAM J.
Comput. 12 347-353.
Zemel, E. The Linear Multiple Choice Knapsack Problem. Oper. Res. 28 1412-1423.
---. (September 1982). An O ( n ) Algorithm for the Linear Multiple Choice Knapsack Problem
and Related Problems. Working Paper 752/82, Israel Institute of Business Research, Tel. Aviv
University.
MEGIDDO: IBM RESEARCH K51/281,5600COTTLE ROAD, SAN JOSE, CALIFORNIA 95193
ICHIMORI: SYSTEMS AND INDUSTRIAL ENGINEERING, HIROSHIMA UNIVERSITY.
HIROSHIMA 724. JAPAN