Poly-log p a r a l l e l a l g o r i t h m s f o r
LP
w i t h an
a p p l i c a t i o n t o exploding f l y i n g o b j e c t s *
Nimrod Megiddo
Carnegie-Mellon U n i v e r s i t y
and T e l Aviv U n i v e r s i t y
November 1982
Abstract
The main r e s u l t s of t h i s paper a r e t h e following:
(i)
is
LP
s o l v a b l e i n poly-log t i m e when t h e number of v a r i a b l e s i s f i x e d ( d e s p i t e
t h e g e n e r a l problem being log-space hard f o r
P).
(ii)
Probabilistic
p a r a l l e l a l g o r i t h m s a r e designed w i t h t h e a i d of a p r o b a b i l i s t i c c o n s t a n t -
time a l g o r i t h m f o r maximum-finding (on t h e WRAM model) and random s e a r c h e s .
We s o l v e d - v a r i a b l e
LP i n
0 (logn(log1ogn) d'2)
the deterministic algorithms run i n
O(logd"n
time, p r o b a b i l i s t i c a l l y ;
loglogn)
provide s e q u e n t i a l a l g o r i t h m s f o r t h e following problem:
f l y i n g a t v a r i o u s speeds on s t r a i g h t l i n e t r a j e c t o r i e s i n
time.
Given
(iii)
n
We
objects,
R ~ f i,n d the s m a l l e s t
s i z e of a bomb r e q u i r e d t o d e s t r o y a l l of them a t once, thereby determining
t h e optimal time and p l a c e f o r t h e explosion.
Relying on p a r a l l e l a l g o r i t h m s
f o r LP-type problems, w e s o l v e t h e optimal e x p l o s i o n problem with ( s e q u e n t i a l )
4
complexity a s low a s O(n l o g n loglogn) d e t e r m i n i s t i c a l l y , and
2
2
O(n l o g n (loglogn) ) p r o b a b i l i s t i c a l l y .
*Supported i n p a r t by t h e N a t i o n a l Science Foundation under g r a n t no.
ECS-8121741.
1.
Introduction
The g e n e r a l
expect t o s o l v e
whether
time.
LP
LP
problem i s log-space hard f o r
d
[DLR].
So, we do n o t
It i s i n t e r e s t i n g t o ask
i n p a r a l l e l i n poly-log time,
LP w i t h a f i x e d number
P
of v a r i a b l e s i s s o l v a b l e i n poly-log
The answer i s not t r i v i a l s i n c e ( i ) both t h e simplex a l g o r i t h m [Da]
and t h e Khachiyan-type a l g o r i t h m s [K, YL] a r e i n h e r e n t l y s e q u e n t i a l , and ( i i )
even t h e s p e c i a l c a s e of t h e max-flow problem i s log-space hard f o r
P
N e v e r t h e l e s s , we provide a n a f f i r m a t i v e answer i n t h e p r e s e n t paper.
from o u r previous ( s e q u e n t i a l ) a l g o r i t h m s f o r
LP
.
[M3]
[GSS].
T h i s stems
The obvious p a r a l l e l
v e r s i o n s of t h o s e a l g o r i t h m s a r e improved, and we a l s o i n c o r p o r a t e randomization
f o r even f u r t h e r improvements.
For
d=2 we o b t a i n a n i n t e r e s t i n g p r o b a b i l i s t i c
a l g o r i t h m which runs almost s u r e l y (a. s .) i n
to
O(1ogn) time.
~ ( l o g n ( l o g l o g n ) ~ -a~l g) o r i t h m s f o r any f i x e d
run i n
o(logd-'n
loglogn)
d.
This then g e n e r a l i z e s
The d e t e r m i n i s t i c a l g o r i t h m s
time,
An i n t e r e s t i n g f e a t u r e of t h i s paper i s t h e e x p l o i t a t i o n of a p a r a l l e l
c o n s t a n t - t i m e p r o b a b i l i s t i c a l g o r i t h m f o r t h e maximum [M4], i n a p r o b a b i l i s t i c
s e q u e n t i a l a l g o r i t h m f o r a problem of optimal explosion.
a s follows.
Given
n
The l a t t e r i s d e f i n e d
o b j e c t s , moving on s t r a i g h t l i n e t r a j e c t o r i e s i n 3-space,
f i n d t h e s m a l l e s t r a d i u s of a b a l l which c o n t a i n s a l l t h e o b j e c t s a t any one
time.
This b a l l determines t h e s m a l l e s t s i z e of a bomb t h a t i s r e q u i r e d t o
d e s t r o y a l l t h e o b j e c t s i n one s h o t , thereby i n d i c a t i n g t h e optimal time and
p l a c e f o r t h e explosion.
T h i s problem provides m o t i v a t i o n f o r studying t h e
p a r a l l e l complexity of t h e s t a t i c problem of t h e s m a l l e s t b a l l e n c l o s i n g
given p o i n t s i n 3-space.
[M2, M31).
The l a t t e r i s c l o s e l y r e l a t e d t o 4 - v a r i a b l e
n
LP
(see
A c t u a l l y , t h e a l g o r i t h m s f o r t h e two problems a r e very s i m i l a r .
The r e l a t i o n s h i p between the dynamic and t h e s t a t i c problems i s along t h e l i n e s
developed i n [MI].
We remark t h a t t h e dynamic problem i n 3-space i s
h 4-space.
not equiva-
The s t a t i c problem i s s o l v a b l e i n any
l e n t t o t h e s t a t i c problem i
.
a r e obviously much
recognizing whether any two
b
f
n
t o be s o l v a b l e ( s e q u e n t i a l l y ) i n
Even a seemingly simple problem, namely,
given l i n e s i n
R
o ( n L ) time [Do].
3
i n t e r s e c t , i s not known
It i s t h e r e f o r e i n t e r e s t i n g
t h a t o u r dynamic s m a l l e s t ba 1 problem can be solved ( s e q u e n t i a l l y ) i n
4
2
2
O(n l o g n l o g l o g n ) time
p r o b a b i l i s t i c a l l y , i n O(n l o g n ( l o g l o g n ) )
These a l g o r i t h m s
r e l y on ou
b a l l problem.
2.
R~
Problems of computational geometry i n
f i x e d dimension i n
1
p a r a l l e l algorithms f o r
E x i s t e n c e of poly-log a l d o r i t h m s f o r d - v a r i a b l e
LP
time.
and s t a t i c s m a l l e s t
LP
The e x i s t e n c e of polyelog a l g o r i t h m s f o r d - v a r i a b l e
LP
f o l l o w s from o u r
( s e q u e n t i a l ) l i n e a r - t i m e algclrithms [M3]. A p a r a l l e l implementation runs i n
d
O(1og n)
paper.
f o r any
d.
However, we improve t h i s bound s u b s t a n t i a l l y i n t h e p r e s e n t
.i,id < 3) .
Our paper on t h e seq e n t i a l c a s e [M3] i s c u r r e n t l y not i n t h e form of
a p u b l i c a t i o n ( s e e [M21 f o r
-
The r e s u l t i s c e r t a i n l y a no.-
trivial
e x t e n s i o n of [ ~ 2 ]and necessiltates a t l e a s t a b r i e f o u t l i n e h e r e .
The a l g o r i t h m r e c u r s e s on t h e dimension.
Q
the constraints a r e c l a s s i f i e
First,
i n t o t h r e e types and w i t h i n each type we a r r a n g e
t h e c o n s t r a i n t s i n d i s j o i n t pbirs.
c r i t i c a l hyperplane.
It works a s follows.
F o r each p a i r we compute a n e q u a t i o n of a
A l l t h i k work r e q u i r e s c o n s t a n t - time on
n
processors.
The next s t e p r e q u i r e s p a r t i t i o n i n g t h e hyperplanes i n t o two s e t s according t o
r
t h e s l o p e of t h e i r i n t e r s e c t i n w i t h t h e
f i n d i n g t h e median s l o p e .
time [BH, V ] .
(xl,x2)-subspace.
W e can do i t d e t e r m i n i s t i c a l l y i n
i
This i n v o l v e s
O(1ogn loglogn)
P r o b a b i l i s t i c a l y , t h e s l o p e of a random hyperplane t u r n s o u t
t o be a s y m p t o t i c a l l y a s good As t h e median.
Given t h e p a r t i t i o n of t h e
hyperplanes, we match those w i t h "high" s l o p e w i t h those w i t h "low" s l o p e
-
( t h e matching i s n o t p e r f e c t i n t h e p r o b a b i l i s t i c c a s e ) .
matched h y p e r p l a n e s , w e produce two o t h e r hyperplanes:
x1
from t h e e q u a t i o n s and a n o t h e r one by e l i m i n a t i n g
constant-time.
Let
x*
x*
x2.
This a l s o t a k e s
relative to
> 0 ) , t h e r e b y d i s c a r d i n g Ben c o n s t r a i n t s .
(B = B(d)
one by e l i m i n a t i n g
The b a s i c i d e a i s t h a t
denote t h e s o l u t i o n p o i n t .
w e o b t a i n i n f o r m a t i o n a b o u t t h e p o s i t i o n of
F o r each p a i r of
Ben
hyperplanes
Repeating t h i s procedure
times reduces t h e number of c o n s t r a i n t s i n such a way t h a t w e c a n then
O(1ogn)
s o l v e t h e problem i n one s t e p .
Ben hyperplanes i s acquired r e c u r s i v e l y ( r e l a t i v e
The i n f o r m a t i o n about
to
d).
which
We f i r s t o b t a i n information about
xl
i.e.,
was e l i m i n a t e d and then about
those w i t h
x
eliminated.
2
B ( d - l ) * n of t h e hyperplanes from
2
(B(d-1)) n
of t h e i r c o u n t e r p a r t s ,
T h i s s t e p r e q u i r e s , by i n d u c t i o n , O(1og
time, s o t h a t we c a n s o l v e t h e d-dimensional problem i n
d
O(1og n)
d- 1
n)
time.
Improvements w i l l b e d i s c u s s e d below.
Improvement of t h e two-variable a l g o r i t h m
3.
We now d e s c r i b e a p a r a l l e l a l g o r i t h m f o r 2 - v a r i a b l e
O(1ogn loglogn)
dimension,
y _> a.x+b
-
1
i
2
O(1og n)
time, and hence improves upon t h e
from t h e g e n e r a l c a s e .
LP
bound which follows
By i n d u c t i o n , t h i s a l s o improves t h e bound f o r g e n e r a l
Assume, f o r s i m p l i c i t y , o u r problem i s t o minimize
(i=l,...,n).
y
subject to
This problem encompasses t h e t y p i c a l o p e r a t i o n s
r e q u i r e d f o r s o l v i n g any 2 - v a r i a b l e LP.
s o we a r e s e e k i n g a n
which runs i n
x*
where
f
Let f ( x ) = ~ a x { a . x + b ~ :i = I , .
1
..,n],
i s minimized.
Our a l g o r i t h m i s based on V a l i a n t ' s p a r a l l e l maximum-finding [ V ] ,
u t i l i z i n g a technique we have developed i n [MI].
O(log1ogn)
phases.
i t i s known t h a t
Phase
k
The a l g o r i t h m c o n s i s t s of
s t a r t s with a subset
f (x*) = Max{aix*+bi:
irN )
k
N k c (1,.
(even though
..,n)
x*
f o r which
itself
is
n o t known).
and
n
s i n g l e e v a l u a t i o n of
w e form
k
q
=
1 ~ ~ 1
The amount of work s o f a r i s c o n s t a n t ( s e e [SV'J).
f
x r [%,Pk]
a t an
takes
Thus, we can simultaneously e v a l u a t e
[~p$
i n ~O(log1og
]
[a B ]
k' k
O(logn/log(nlnk))
time.
rj)
O(log1og nk)
f
at
n/nk
time on
A
q
p o i n t s of
T h i s i m p l i e s t h a t , once t h e i n t e r s e c t i o n p o i n t s
are sorted (requires
t i m e ) , w e can i n
O(1ogn)
s t e p s (each c o n s i s t i n g of
n/nk
f-evaluations) find a
[ u ~ + $k+l]
~ , C[%,Bk]
which c o n t a i n s x* and no i n t e r s e c t i o n
,k
S i n c e q = 0(n/2' ), i t f o l l o w s t h a t t h e e n t i r e
point l i e s i n i t s i n t e r i o r .
e f f o r t of phase
k
is
O(1ogn
+
(loglog(n/2 2k ) ) ( l o g n ) / 2 k ) . S i n c e k 5
- loglogn,
i t follows t h a t the t o t a l e f f o r t i s
4.
During phase
F o r each p a i r w e f i n d t h e i n t e r s e c t i o n p o i n t of
the participating lines.
subinterval
1.
A t t h e end of t h e phase each c l i q u e c o n t r i b u t e s p r e c i s e l y
one l i n e t o t h e next s e t
who l i e i n
k
< x* 5- Bk
a r c s , which c o n s i s t s of p a i m i s e d i s j o i n t c l i q u e s whose c a r d i n a l i t i e s
d i f f e r by a t most one.
processors.
i s known such t h a t ok
The p a i r s a r e determined by a graph on
p a i r s of l i n e s from Nk.
n
$ 1
k' k
~ c N ~f o]r a l l x r 19,B
f (x) = Max[aix+bi:
nodes and
[
Moreover, an i n t e r v a l
O(1ogn loglogn).
P r o b a b i l i s t i c two-variable a l g o r i t h m
I n t h i s s e c t i o n we i n d i c a t e a p r o b a b i l i s t i c
2-variable
LP
maximum of
n
which can r u n on t h e WRAM model.
numbers a . s .
in
we t a k e a random sample of
This t a k e s constant-time.
O(1)
O(1ogn)
algorithm f o r
It i s based on f i n d i n g t h e
time on t h e WRAM model [M4]. S p e c i f i c a l l y ,
l i n e s and f i n d a l l t h e i r p o i n t s of i n t e r s e c t i o n .
We now wish t o Locate
x*
i n an i n t e r v a l
[a,$]
t h a t c o n t a i n s no i n t e r s e c t i o n p o i n t i n i t s i n t e r i o r , s o t h a t t h e samplemaximum w i l l be known a t
#
(and i n f a c t over t h e e n t i r e
[a,?]).
This
i s c a r r i e d o u t by a random s e a r c h over t h e s e t of i n t e r s e c t i o n p o i n t s .
S p e c i f i c a l l y , pick an i n t e r s e c t i o n p o i n t
x
a t random and e v a l u a t e
f (x)
-
(a.s. in constant-time) and the one-sided derivatives f (x), f+(x)
(also
Discard a portion of the set according to the posi-
a.s. in constant-time).
tion of x relative to x*, as learned from f (x)
and
(see [M2])
f+(x)
It follows that this search will take an expected number of O(1ogn)
Knowing the line L which determines the sample-maximum over
.
evaluations.
[a,$], we now
find the intersection points of L with all the other lines, and search for
an interval
[ ~ ' , @ ' ] C [ c u ,which
~]
contains x*
and no such intersection point
in its interior. This is done essentially in the same way we do the first
search, i.e., in O(1ogn)
maxirmun at x*.
time.
Now we know which lines lie above the sample-
Their number is expected to be 0Vn)
procedure unless there are less than
approaching 1
(as n
0(logn)
lines left. However, with probability
tends to infinity), this will not repeat more than twice.
When we are left with less than
one search step (i.e.,
fi
and we repeat the entire
O(1ogn)
lines, we f-Lnd the minimum directly in
time).
The entire algorithm takes an expected
time.
5. Deterministic and probabilistic algorithms for d variables
For improving the 3-variable case we need to conkider the 2-variable
2
case with any number p(n <
- p - n ) of processors. Let r = 2pIn. The
<
maximum can be found in O(log((logn)/logr))
time [SV, V].
Using this result,
we solve 2-variable LP deterministically in O(log(n/r)loglog(n/r)
loglog (nlr) ' lognllogr)
+
time and probabilistically in simply 0(lognllogr)
time. These bounds imply that the 3-variable case is solvable deterministically
2
in O(1og n loglogn)
time and probabilistically in O(1ogn loglogn)
These bounds are then generalized to O(logd-'n
and 0(logn(loglogn)d'2)
time.
loglogn) deterministically,
probabilistically. The difference, which becomes
more and more dramatic as d
increases, is due to the fact that a random
s e a r c h (which i s a s y m p t o t i c a l l y a s good a s a d e t e r m i n i s t i c one) does n o t
r e q u i r e median-finding.
The l a t t e r i s a r e l a t i v e l y c o s t l y o p e r a t i o n when we
a r e dealing with d e t e r m i n i s t i c p a r a l l e l algorithms.
6.
The optimal e x p l o s i o n problem
We c o n s i d e r t h e following problem:
Given a r e
n
objects, flying i n
Find a time and a
3-space a t v a r i o u s speeds w i t h s t r a i g h t l i n e t r a j e c t o r i e s .
This b a l l determines
p l a c e a t which a s m a l l e s t b a l l encloses a l l t h e o b j e c t s .
t h e s i z e of t h e s m a l l e s t bomb t h a t can d e s t r o y a l l t h e o b j e c t s , and t h e optimal
time and p l a c e f o r t h e explosion.
This problem i s
finding the smallest b a l l enclosing
n
e q u i v a l e n t t o t h a t of
p o i n t s i n 4-space.
Also, a r e l a t e d
n
problem of f i n d i n g t h e s m a l l e s t b a l l t h a t touches a l l t h e
(i.e.,
trajectories
each o b j e c t touches t h e b a l l a t some time) i s e a s i e r than our p r e s e n t
problem.
The " s t a t i c " problems of s m a l l e s t b a l l s can be solved i n l i n e a r - t i m e ,
A
whenever t h e dimension i s f i x e d , by methods resembling those of [M3].
seemingly r e l a t e d problem, namely, recognizing whether any two of
n
l i n e s i n R~
o(n2)
time [Do].
i n t e r s e c t , i s c u r r e n t l y not known t o be s o l v a b l e i n
given
It i s t h u s i n t e r e s t i n g t h a t o u r optimal explosion problem c a n b e
solved i n ( s e q u e n t i a l )
2
2
O(n l o g n(1oglogn) )
4
O(n log n loglogn)
probabilistically.
follow by combining two powerful r e s u l t s :
time d e t e r m i n i s t i c a l l y and
However, t h e s e low-order c o m p l e x i t i e s
( i ) t h e g e n e r a l scheme of u s i n g
p a r a l l e l a l g o r i t h m s i n t h e d e s i g n of s e r i a l ones, a s proposed i n [MI],
and ( i i )
R
3
.
f a s t p a r a l l e l a l g o r i t h m s f o r t h e s t a t i c s m a l l e s t b a l l problem i n
The bound c a n b e improved i f randomization i s allowed.
Following i s a b r i e f s k e t c h of t h e a l g o r i t h m .
Let
r a d i u s of t h e s m a l l e s t b a l l e n c l o s i n g t h e o b j e c t s a t time
F(t)
i s convex and we know how t o e v a l u a t e i t a t any
t
F(t)
t.
denote t h e
The f u n c t i o n
i n O(n)
time IE.131.
Moreover, w e develop i n t h e p r e s e n t paper a p a r a l l e l a l g o r i t h m f o r e v a l u a t i n g
F(t)
t*.
in
3
O(1og n l o g l o g n )
t i m e with
n
processors.
Denote t h e minimum by
Simulating t h i s p a r a l l e l a l g o r i t h m , w e can run i n
with
n o t s p e c i f i e d b u t confined t o a n i n t e r v a l
t
yk(% < yk
T y p i c a l l y , t h e r e w i l l a l s o be a v a l u e
q <
and F(B ) > F(y ) (and t h e r e f o r e
k
k
t r [ ak , Y k )
i s t h e same f o r a l l
t*
<
q).
and f o r a l l
may produce a s m a l l number (independent of
3
O(1og n loglogn)
[ak,Bk]
< Bk)
during s t a g e
such t h a t
F(%)
for
is
such t h a t
j
[ak+l, Bkcl]
.., < tm= Bk,
ak = tl C
F(t
5-1
> F(t
)
= [ t j - l , tj+l]
search1' over t h e s e t
(tl,.
However, i t f o l l o w s t h a t
m
[ y ,$
I),
and
)
.
tr[yk,Pk].
However, each p r o c e s s o r
t
n) of c r i t i c a l v a l u e s of
> F(tj).
which
Denoting
A ) , w e then search
(yk = t Af o r sane
F(tj+l)
> F(yk)
The next i n t e r v a l
S i n c e F i s convex, we can perform a "Fibonacci
..,tm )
which amounts t o
<- 1811,
two p a i r s of polynomials of
a n o t h e r over
J
k.
The t a s k of each p r o c e s s o r
determine how t h e a l g o r i t h m should proceed i n t h e succeeding s t a g e .
t h e s e v a l u e s by
stages
O(1ogm)
e v a l u a t i o n s of
s i n c e each p r o c e s s o r may need t o compare
and
t h e r e b y producing a t most 18 c r i t i c a l v a l u e s .
The
k k
e f f o r t per s t a g e i s t h e r e f o r e
of d e g r e e
9
,Y )
t
F.
O(n logn)
(one p a i r over
and t h e t o t a l i s
[
ak
k
4
O(n l o g n l o g l o g n ) .
We should mention t h a t t h i s i s i n f a c t t h e number of times we may need t o s o l v e
s i n g l e - v a r i a b l e polynomial e q u a t i o n s of d e g r e e n o t g r e a t e r than
9.
t h e e f f o r t involved i n s o l v i n g a s i n g l e e q u a t i o n i s independent of
However,
n.
A p r o b a b i l i s t i c a l g o r i t h m , based on p r o b a b i l i s t i c a l l y f i n d i n g a s t a t i c
2
smallest b a l l i n
O(logn(log1ogn) )
a probabilistic
2
2
O(n l o g n(log1ogn) )
problem.
p a r a l l e l t i m e , i s u t i l i z e d i n designing
sequential algorithm f o r the explosion
8
References
A. Borodin and J. E. Hopcroft, "Routing, merging and s o r t i
p a r a l l e l models of computation," STOC 1982, 338-344.
Dantzig, L i n e a r programming and e x t e n s i o n s , P r i n c e t o n U n i v e r s i t y
P r e s s , P r i n c e t o n , N J , 1963.
G. B.
D. Dobkin, p r i v a t e communication, November 1982.
D. Dobkin, R. J. L i p t o n and S. R e i s s , "Linear programming i s log-space
h a r d f o r P," Snf. Proc. L e t t 8 (1979) 96-97.
L. M. Goldschlager, R. A. Shaw and J. S t a p l e s , "The maximum flow
problem i s l o g space complete f o r P," ~ h e b r . ~ o m p . S c i . 21 (1982)
105-111.
L. G . Khachiyan, "A polynomial a l g o r i t h m i n l i n e a r programming," S o v i e t
Math. Pokl. 20 (1979) 191-194.
N. Megiddo, "Applying p a r a l l e l computation a l g o r i t h m s i n t h e d e s i g n of
s e r i a l a l g o r i t h m s , " FOCS 1981, 399-408.
N. Megiddo, "Linear-time a l g o r i t h m s f o r l i n e a r programming i n
R~
and
r e l a t e d problems," FOCS 1982, 329-338.
N. Megiddo, "Solving l i n e a r programming i n l i n e a r time when t h e
dimension i s f i x e d , " r e s e a r c h r e p o r t , A p r i l 1982.
N. Megiddo, " P a r a l l e l a l g o r i t h m s f o r f i n d i n g t h e maximum and t h e
median almost s u r e l y i n constant-time" ( p r e l i m i n a r y r e p o r t ) October 1982.
Y. Shiloach and U. Vishkin, "Finding t h e maximum, merging and s o r t i n g
i n a p a r a l l e l computation mode1,'l J. Algorithms 2 (1981) 88-102.
L. G. V a l i a n t , " P a r a l l e l i s m i n comparison problems," S U M J. Comput. 4
(1975) 348-355.
B. Yamnitsky and L. A. Levin, "An o l d l i n e a r programming a l g o r i t h m
works i n polynomial t i m e , " FOCS 1982, 327-328.