The Pa allel Complexi y o Posi i e Linea
P og amming
Luca T e isan

Cen e Uni e si ai e d'In o ma ique
Uni e si e de Gene e
Rue Gene al-Du ou 24, 1211, Gene e, CH
Email:
e [email protected] oma1.i
Fa os Xha a
y
Depa amen de LSI
Facul a d'In o ma ica, UPC
Pau Ga gallo 5, 08028 Ba celona, Spain
Email:
a os@golia .upc.es
Janua y 18, 1997
Abs ac
In his pap e we s udy he pa allel complexi y o Posi i e Linea P og amming (PLP), i.e.
he sp ecial case o Linea P og amming in packing/co e ing o m whe e he inpu cons ain
ma ix and cons ain ec o consis en i ely o p osi i e en ies. We show ha he p oblem o
exac ly sol ing PLP is P-comple e.
1 In o duc ion
Linea P og amming (LP) is one o he mos cen al p oblems in combina o ial op imiza ion. I is
he p oblem o op imizing a linea unc ion
c
T
x
o e a con ex p olyhed on
x
:
A
x

b
;
x

0
g
,
whe e
x
2
R
n
+
,
A
is an
m

n
-ma ix and
b
;
c
2
R
n
. The pa allel complexi y o his p oblem is,
by now, well unde s o o d. Dobkin, Lip on, Reiss and Khachyan [4, 8] showed ha ( he gene al) LP
was comple e, in he s ong sense, o P unde
logspace
educ ions. La e on, i was shown ha
e en he p oblem o app oxima ing he alue o a gene al linea p og am is P-comple e [13, 12].
The e o e, he e is no as pa allel algo i hm o sol ing LP o o app oxima ing i , unless P=NC.
Howe e , hese esul s do no ule ou he exis ence o NC algo i hms
1
o sp ecial cases o LP.
Indeed, Luby and Nisan [11] ga e an NC app oxima ion algo i hm o he es ic ed e sion o
linea p og amming called Posi i e Linea P og amming (PLP). An ins ance o PLP has all he
en ies o he ma ix
A
and hose o
b
and
c
non-nega i e, and i is in he
packing
( esp.
co e ing
)
o m, i.e., he linea es ic ions a e gi en by
A
x

b
and he ob jec i e unc ion is o b e maximized
( esp.
A
x

b
, he ob jec i e unc ion is o b e minimized). Luby and Nisan's algo i hm compu es a
easible (1 +
"
)-app oxima e solu ion in ime p olynomial in 1
="
and log
N
, using
O
(
N
) p o cesso s
(whe e
N
is he size o he inpu ). An algo i hm wi h such a ade-o b e ween app oxima ion
gua an ee and eciency is usually called an NCAS (NC App oxima ion Scheme) (see, e.g., [3]).
PLP is o a pa icula in e es since many imp o an combina o ial p oblems can b e cas ed by
p osi i e linea p og ams and he e o e Luby and Nisan algo i hm can b e used o app oxima e hem
in NC. Thus, Maximum Ma ching in bipa i e g aphs [5, 6] is mo deled by a p osi i e 0
=
1 linea

Resea ch done while isi ing he Depa amen de Llengua ges i Sis emes In o ma ics de la UPC.
y
The esea ch o his au ho was supp o ed by ESPRIT Long Te m Resea ch P o jec 20244-ALCOM-IT.
1
i.e., algo i hms ha un in
polylog
ime and use a
polynomial
numb e o p o cesso s
1
Elec onic e sion o an a icle published as: T e isan, L., Xha a, F. The pa allel complexi y o posi i e linea
p og amming. "Pa allel p ocessing le e s", Desemb e 1998, ol. 8, núm. 4, p. 527-533.
DOI: 10.1142/S0129626498000511. © 1998 Wo ld Scien i ic Publishing Company.
h p://www.wo ldscien i ic.com. ecu sos.biblio eca.upc.edu/doi/pd /10.1142/S0129626498000511
p og am, and i we elax he condi ion o 0
=
1 a iables b e simply p osi i e he op imum alue is no
changed. The e o e, Luby and Nisan's algo i hm can b e used o app oxima e he size o a la ges
ma ching, and as indica ed in [11], his is essen ially he esul o [2]. Also, Minimum Se Co e
can b e o mula ed as a 0
=
1 p osi i e linea p og am [10]. In his case, elaxing he condi ion o
he in eg ali y o a iables dec eases he op imum by a ac o o ln , whe e  is he maximum
deg ee in he se sys em. The e o e, he algo i hm o PLP app oxima es he op imum size o he
se co e wi hin a ac o o (1 +
"
) ln . The use o PLP in he design o pa allel app oxima ion
algo i hms has b een u he explo ed in [14]. Among o he esul s, a PLP elaxa ion o Maximum
Sa isabili y (Max SAT) is p esen ed whose op imum is a mos 4/3 imes he op imum o he Max
SAT p oblem. In combina ion wi h Luby and Nisan's algo i hm and a p op e ounding scheme,
his gi es an NC (3
=
4
?
"
)-app oxima e algo i hm o Max SAT.
Un o una ely, Luby and Nisan's algo i hm canno b e used o exac ly sol e an ins ance o PLP
in NC. In his no e we add ess he p oblem o he pa allel complexi y o PLP. We show ha
he p oblem o exac ly sol ing PLP is P-comple e. Ou esul is based on he obse a ion ha
he
Ci cui Value P oblem
(CVP), which is P-comple e [9], can b e logspace educed o PLP. The
educ ion ollows ha o [7] bu we ake ca e o he linea cons ain s and he ob jec i e unc ion
o ha e non-nega i e co ecien s. An imp o an implica ion o ou esul is ha , by using he LP
echnique, we canno exac ly compu e in NC he ca dinali y o Maximum Ma ching in bipa i e
g aphs o nding a (ln )-app oxima ion o Minimum Se Co e , o a 3
=
4-app oxima ion o an
ins ance o Maximum SAT, unless P=NC.
P elimina ies
An ins ance o CVP is: Gi en an enco ding o a Bo olean ci cui ha consis s o compu a ional
ga es
NOT
and
OR
2
oge he wi h an inpu assignmen , de e mine whe he he ou pu ga e e alua es
o 0 o 1." We assume ha he eade is amilia wi h he no ion o logspace educ ions, and is
e e ed o [1, 7] o deni ions. We deno e by (
A;
b
;
c
) an ins ance o PLP in he packing o m.
The co esp onding decision e sion o his p oblem is: Gi en an ins ance (
A;
b
;
c
) and
d
2
R
+
,
is he e any ec o
x
2
R
n
+
, such ha
A
x

b
and
c
T
x

d
?" We will deno e by (
A;
b
;
c
; d
) an
ins ance o his p oblem. We will use b old ace cha ac e (e.g.
) o deno e ec o s; some imes we
will use
1
o deno e a ec o all whose en ies a e equal o 1. Finally, o a se
I
, we deno e by
j
I
j
i s ca dinali y.
2 The P-comple eness o F ac ional Packing P oblems
We ecall he s anda d educ ion om he CVP o Linea P og amming. Le
g
1
;:::;g
m
b e he
ga es o he ci cui , we use a a iable
i
o any ga e
g
i
. The in ended meaning o such a iables
will b e ha
i
2
0
;
1
g
and ha
i
= 1 i he ou pu o
g
i
is one. We asso cia e one o mo e linea
cons ain s o any ga e: he cons ain s will b e such ha only one easible solu ion exis s (namely,
he solu ion in which he alues o
i
a e consis en wi h hei in ended meaning). I
g
k
is an inpu
ga e whose alue is ze o ( esp. one), hen he co esp onding cons ain will b e
k
= 0 ( esp.
k
= 1).
I
g
k
is a
NOT
ga e whose inpu comes om ga e
g
j
, hen he cons ain will b e
k
= 1
?
j
. Finally,
i
g
k
is an
OR
ga e whose inpu s come om ga e
g
i
and
g
j
, hen he cons ain s will b e
k

i
,
k

j
,
k

i
+
j
. Fo all he ga e a iables we also ha e 0

x
i

1 [7]. I is easy o p o e
by induc ion on he dep h o he ci cui ha such linea p og am has only one easible solu ion,
2
This e sion o CVP has also b een shown o b e P-comple e.
2
namely he solu ion ha co esp onds o he co ec se ings o he ga es. Thus, i we use
m
as
ob jec i e unc ion, he op imum alue will b e ze o o one, and will b e one i he ci cui ou pu s
one.
The ab o e desc ib ed linea p og am can b e exp essed as
max
m
sub jec o
k
= 1
8
k
2
I n
1
k
= 0
8
k
2
I n
0
k

i
8
(
i; j; k
)
2
O R
k

j
8
(
i; j; k
)
2
O R
k

i
+
j
8
(
i; j; k
)
2
O R
k
= 1
?
j
8
(
j; k
)
2
N eg
0

i

1
8
i
2
1
;:::;m
g
(LP1)
whe e we used he no a ion
I n
0 ( esp.
I n
1) o deno e he se o indices o inpu ga es whose alue
is ze o ( esp. one), he no a ion
N eg
o deno e he se o pai o indices (
j; k
) such ha
g
k
is a
NOT
ga e aking i s inpu om
g
j
, and
O R
o deno e he se o iples (
i; j; k
) such ha
g
k
is an
OR
ga e
aking i s inpu s om ga es
g
i
and
g
j
.
Clea ly, he p og am (LP1) is no an ins ance o PLP. No ice ha in (LP1) we ha e some
cons ain s which a e equali ies and also he e a e a iables wi h nega i e co ecien s. We will deal
wi h b o h o hem in wo sepa a e s eps. We  s in o duce new a iables
1
;:::;
m
such ha
i
= 1
?
i
. The p og am b ecomes
max
m
sub jec o
k
= 1
8
k
2
I n
1
k
= 1
8
k
2
I n
0
k
+
i

1
8
(
i; j; k
)
2
O R
k
+
j

1
8
(
i; j; k
)
2
O R
i
+
j
+
k

2
8
(
i; j; k
)
2
O R
k
+
j
= 1
8
(
j; k
)
2
N eg
i
+
i
= 1
8
i
2
1
;:::;m
g
i
;
i

0
8
i
2
1
;:::;m
g
(LP2)
I should b e clea ha he e is a co esp ondence b e ween he unique easible solu ion o (LP1)
and he unique easible solu ion o (LP2), mo e o mally, we ha e he ollowing esul .
Fac 1
I
is a easible solu ion o (LP1), hen
(
;
1
?
)
is a easible solu ion o (LP2), and he
cos o he solu ions a e equal. I
(
;
)
is a easible solu ion o (LP2), hen
is a easible solu ion
o (LP1) and he cos o he solu ions a e equal.
3
No e ha (LP1) is no ye a packing p oblem, since he e a e equali y cons ain s. The nal
s ep will b e o elax hem in o inequali y cons ain s and o mo di y he ob jec i e unc ion in such
a way ha i will ne e b e con enien " o s ic ly sa is y he elaxed cons ain s. We no e ha
ou echnique b ea s some simila i y o he me ho d o Lag angean elaxa ions.
max
m
+
P
k
2
I n
1
k
+
P
k
2
I n
0
k
+
P
(
k ;j
)
2
N eg
(
k
+
j
) +
P
m
i
=1
(
i
+
i
)
sub jec o
k
+
i

1
8
(
i; j; k
)
2
O R
k
+
j

1
8
(
i; j; k
)
2
O R
i
+
j
+
k

2
8
(
i; j; k
)
2
O R
k
+
j

1
8
(
j; k
)
2
N eg
i
+
i

1
8
i
2
1
;:::;m
g
i
;
i

0
8
i
2
1
;:::;m
g
(LP3)
Lemma 1
The e exis s a solu ion o (LP3) o cos
1 +
j
I n
1
j
+
j
I n
0
j
+
j
N eg
j
+
m
i and only i
he e exis s a solu ion o (LP2) o cos 1.
P oo :
Le
K
= 1 +
j
I n
1
j
+
j
I n
0
j
+
j
N eg
j
+
m
. I is immedia e o e i y ha a easible solu ion
o (LP2) o cos 1 is easible o (LP3) and i s cos is
K
. Assume now ha (
;
) is easible o
(LP3) and i s cos is
K
; we claim ha (
;
) is easible o (LP2) and ha
m
= 1. Indeed, he cos
o a solu ion o (LP3) is he sum o
K
e ms, and each one is cons ained o b e a mos one. I
he e exis s a easible solu ion whose cos is
K
, hen i ollows ha all such e ms a e equal o one,
and hus he solu ion is easible o (LP2) and
m
= 1.
2
Theo em 2
PLP in packing o m is P-comple e.
P oo :
I is immedia e o check ha , gi en he desc ip ion o a ci cui , he PLP ins ance (LP3)
can b e cons uc ed using loga i hmic space. The heo em hus ollows om Lemma 1.
2
The P-ha dness o op imally sol ing PLP co e ing p oblems immedia ely ollows om he du-
ali y heo em o linea p og amming (co e ing p oblems a e he duals o packing p oblems). The
P-comple eness o he decision e sion can b e es ablished di ec ly by mino changes o he ab o e
p o o .
Rema k 3
Ano he consequence o ou esul is ha he ex ension o PLP whe e equali y con-
s ain s a e admi ed is P-ha d o app oxima e wi hin any cons an ac o . This obse a ion im-
plies ha , o a ce ain ex en , PLP is he mo e gene al e sion o LP admi ing NC app oxima ion
algo i hms.
2.1 On FNCASs o PLP
A Fully NC App oxima ion Scheme (FNCAS) o a combina o ial op imiza ion p oblem is an
algo i hm ha nds (1 +
"
)-app oxima e solu ions in ime p oly-loga i hmic in
n
(size o he inpu )
and 1
="
and using a p olynomial numb e o p o cesso s (in
n
and
"
).
One would b e emp ed o conjec u e he ollowing s onge s a emen o Lemma 1:
I we le
Z

2
( esp.
Z

3
) be he op imum solu ion o (LP2) ( esp. (LP3)), hen
Z

3
=
Z

2
+
j
I n
1
j
+
j
I n
0
j
+
j
N eg
j
+
m
.
4
g
1
g
2
g
3
g
4
_ _
_
_
g
2
k
?
1
g
2
k
_
_
g
2
k
?
3
g
2
k
?
2
:::
n
n
n
n
n
n
0 0
@
@
?
?
? @
P
P
P
P
P





@
@
#
#
#
_
n
g
2
k
+1
Figu e 1: A pa ological case o ou educ ion.
The s onge s a emen would imply ha PLP admi s no FNCAS unless P = NC. Un o una ely,
he e a e coun e examples o such s a emen . Conside he ci cui and he assignmen depic ed in
Figu e 1.
No e ha he assignmen do es no sa is y he ci cui . The co esp onding (LP3) o mula ion is
max
2
k
+1
+
1
+
2
+
P
2
k
+1
i
=1
(
i
+
i
)
sub jec o
k
+
i

1
8
(
i; j; k
)
2
O R
k
+
j

1
8
(
i; j; k
)
2
O R
i
+
j
+
k

2
8
(
i; j; k
)
2
O R
i
+
i

1
8
i
2
1
;:::;m
g
i
;
i

0
8
i
2
1
;:::;m
g
(LP3)
Whe e
m
= 2
k
+ 1. Conside he assignmen such ha
2
i
?
1
=
2
i
= 1
=
2
k
+1
?
i
o
i
= 1
;:::;k
(so,
in pa icula ,
2
k
= 1
=
2);
2
k
+1
= 1; and
i
= 1
?
i
o
i
= 1
;:::;
2
k
+ 1. I is easily seen ha his
assignmen sa ises all he cons ain s and ha i s cos is 1 +
j
I n
1
j
+
j
I n
0
j
+
j
N eg
j
+
m
?
2
1
?
k
.
Since
k
( he dep h o he ci cui ) is linea in he size o he ci cui , i ollows ha , in o de o
exac ly sol e he ins ance p o duced by ou educ ion, only an exp onen ially small app oxima ion
can b e admi ed.
3 Conclusions
Ou esul shows ha Luby and Nisan's algo i hm canno b e imp o ed o he p oin o compu ing
op imum solu ions in NC o ac ional packing and co e ing p oblems. I is s ill an op en ques ion
whe he a FNCAS exis s o PLP.
5

Re e ences
[1] J.L. Balcaza , J. Daz, and J. Gaba o.
S uc u al Complexi y I.
Sp inge Ve lag, 1995.
[2] E. Cohen. App oxima e maxow on small dep h ne wo ks. In
P oceedings 37 h IEEE Sympo-
sium on Founda ions o Compu ing Science
, pages 648{658, 1992.
[3] J. Daz, M.J. Se na, P. Spi akis, and J. To an.
Pa adigms o as pa al lel app oxima ions.
Camb idge Uni e si y P ess (To app ea ).
[4] D. Dobkin, J.R. Lip on, and S. Reiss. Linea P og amming is logspace ha d o P.
In o ma ion
P ocessing Le e s
, 8:96{97, 1979.
[5] J. Edmonds. Maximum ma ching and a p olyhed on wi h 0,1- e ices.
Jou nal o Resea ch o
he Na ional Bu eau o S anda ds B
, 69B:125{130, 1965.
[6] J. Edmonds and E. Johnson. Ma ching: A well-sol ed class o in ege linea p og ams. In
P oceedings o he Calga y In e na ional Con e ence on Combina o ial S uc u es and hei
Applica ions
, pages 82{92, 1970.
[7] R. G eenlaw, H.J. Ho o e , and W.L. Ruzzo.
Limi s o pa al lel compu a ion: P{comple eness
heo y.
Ox o d Uni e si y P ess, 1995.
[8] L.G. Khachyan. A p olynomial algo i hm in linea p og amming.
T ansla ed in So ie Ma he-
ma ics Doklady
, 20:191{194, 1979.
[9] R.E. Ladne . The ci cui alue p oblem is logspace comple e o P.
SIGACT News
, 7:18{20,
1975.
[10] L. Lo asz. On he a io o op imal in eg al and ac ional co e s.
Disc e e Ma hema ics
,
13:383{390, 1975.
[11] M. Luby and N. Nisan. A Pa allel App oxima ion Algo i hm o Posi i e Linea P og amming.
In
P oceedings 25 h ACM Symposium on Theo y o Compu ing
, pages 448{457, 1993.
[12] N. Megiddo. A no e on app oxima e linea p og amming.
In o ma ion P ocessing Le e s
,
42:53, 1992.
[13] M.J. Se na. App oxima ing linea p og amming is log-space comple e o P.
In o ma ion
P ocessing Le e s
, 37:233{236, 1991.
[14] L. T e isan. Posi i e Linea P og amming, Pa allel App oxima ion and PCP's. In
Fou h
Eu opean Symposium on Algo i hms
, olume 1136 o
Lec u e No es in Compu e Science
,
pages 62{75. Eds. J. Daz, and M. Se na, Sp inge -Ve lag, 1996.
6
View publica ion s a sView publica ion s a s