The parallel complexity of positive linear programming

The Parallel Complexity of Positive Linear Programming Luca Trevisan  Centre Universitaire d'Informatique Universite de Geneve Rue General-Dufour 24, 1211, Geneve, CH Email: [email protected] Fatos Xhafa y Departament de LSI Facultat d'Informatica, UPC Pau Gargallo 5, 08028 Barcelona, Spain Email: [email protected] January 18, 1997 Abstract In this pap er we study the parallel complexity of Positive Linear Programming (PLP), i.e. the sp ecial case of Linear Programming in packing/covering form where the input constraint matrix and constraint vector consist entirely of p ositive entries. We show that the problem of exactly solving PLP is P-complete. 1 Intro duction Linear Programming (LP) is one of the most central problems in combinatorial optimization. It is the problem of optimizing a linear function c T x over a convex p olyhedron f x : A x  b ; x  0 g , where x 2 R n + , A is an m  n -matrix and b ; c 2 R n . The parallel complexity of this problem is, by now, well understo o d. Dobkin, Lipton, Reiss and Khachyan [4, 8] showed that (the general) LP was complete, in the strong sense, for P under logspace reductions. Later on, it was shown that even the problem of approximating the value of a general linear program is P-complete [13, 12]. Therefore, there is no fast parallel algorithm for solving LP or for approximating it, unless P=NC. However, these results do not rule out the existence of NC algorithms 1 for sp ecial cases of LP. Indeed, Luby and Nisan [11] gave an NC approximation algorithm for the restricted version of linear programming called Positive Linear Programming (PLP). An instance of PLP has all the entries of the matrix A and those of b and c non-negative, and it is in the packing (resp. covering ) form, i.e., the linear restrictions are given by A x  b and the ob jective function is to b e maximized (resp. A x  b , the ob jective function is to b e minimized). Luby and Nisan's algorithm computes a feasible (1 + " )-approximate solution in time p olynomial in 1 =" and log N , using O ( N ) pro cessors (where N is the size of the input). An algorithm with such a trade-o b etween approximation guarantee and eciency is usually called an NCAS (NC Approximation Scheme) (see, e.g., [3]). PLP is of a particular interest since many imp ortant combinatorial problems can b e casted by p ositive linear programs and therefore Luby and Nisan algorithm can b e used to approximate them in NC. Thus, Maximum Matching in bipartite graphs [5, 6] is mo deled by a p ositive 0 = 1 linear  Research done while visiting the Departament de Llenguatges i Sistemes Informatics de la UPC. y The research of this author was supp orted by ESPRIT Long Term Research Pro ject 20244-ALCOM-IT. 1 i.e., algorithms that run in polylog time and use a polynomial numb er of pro cessors 1 Electronic version of an article published as: Trevisan, L., Xhafa, F. The parallel complexity of positive linear programming. "Parallel processing letters", Desembre 1998, vol. 8, núm. 4, p. 527-533. DOI: 10.1142/S0129626498000511. © 1998 World Scientific Publishing Company. http://www.worldscientific.com.recursos.biblioteca.upc.edu/doi/pdf/10.1142/S0129626498000511 program, and if we relax the condition for 0 = 1 variables b e simply p ositive the optimum value is not changed. Therefore, Luby and Nisan's algorithm can b e used to approximate the size of a largest matching, and as indicated in [11], this is essentially the result of [2]. Also, Minimum Set Cover can b e formulated as a 0 = 1 p ositive linear program [10]. In this case, relaxing the condition for the integrality of variables decreases the optimum by a factor of ln , where  is the maximum degree in the set system. Therefore, the algorithm for PLP approximates the optimum size of the set cover within a factor of (1 + " ) ln . The use of PLP in the design of parallel approximation algorithms has b een further explored in [14]. Among other results, a PLP relaxation of Maximum Satisability (Max SAT) is presented whose optimum is at most 4/3 times the optimum of the Max SAT problem. In combination with Luby and Nisan's algorithm and a prop er rounding scheme, this gives an NC (3 = 4 ? " )-approximate algorithm for Max SAT. Unfortunately, Luby and Nisan's algorithm cannot b e used to exactly solve an instance of PLP in NC. In this note we address the problem of the parallel complexity of PLP. We show that the problem of exactly solving PLP is P-complete. Our result is based on the observation that the Circuit Value Problem (CVP), which is P-complete [9], can b e logspace reduced to PLP. The reduction follows that of [7] but we take care of the linear constraints and the ob jective function to have non-negative co ecients. An imp ortant implication of our result is that, by using the LP technique, we cannot exactly compute in NC the cardinality of Maximum Matching in bipartite graphs or nding a (ln )-approximation for Minimum Set Cover, or a 3 = 4-approximation of an instance of Maximum SAT, unless P=NC. Preliminaries An instance of CVP is: \Given an enco ding of a Bo olean circuit that consists of computational gates NOT and OR 2 together with an input assignment, determine whether the output gate evaluates to 0 or 1." We assume that the reader is familiar with the notion of logspace reductions, and is referred to [1, 7] for denitions. We denote by ( A; b ; c ) an instance of PLP in the packing form. The corresp onding decision version of this problem is: \Given an instance ( A; b ; c ) and d 2 R + , is there any vector x 2 R n + , such that A x  b and c T x  d ?" We will denote by ( A; b ; c ; d ) an instance of this problem. We will use b oldface character (e.g. t ) to denote vectors; sometimes we will use 1 to denote a vector all whose entries are equal to 1. Finally, for a set I , we denote by j I j its cardinality. 2 The P-completeness of Fractional Packing Problems We recall the standard reduction from the CVP to Linear Programming. Let g 1 ;:::;g m b e the gates of the circuit, we use a variable t i for any gate g i . The intended meaning of such variables will b e that t i 2 f 0 ; 1 g and that t i = 1 i the output of g i is one. We asso ciate one or more linear constraints to any gate: the constraints will b e such that only one feasible solution exists (namely, the solution in which the values of t i are consistent with their intended meaning). If g k is an input gate whose value is zero (resp. one), then the corresp onding constraint will b e t k = 0 (resp. t k = 1). If g k is a NOT gate whose input comes from gate g j , then the constraint will b e t k = 1 ? t j . Finally, if g k is an OR gate whose inputs come from gate g i and g j , then the constraints will b e t k  t i , t k  t j , t k  t i + t j . For all the gate variables we also have 0  x i  1 [7]. It is easy to prove by induction on the depth of the circuit that such linear program has only one feasible solution, 2 This version of CVP has also b een shown to b e P-complete. 2 namely the solution that corresp onds to the correct settings of the gates. Thus, if we use t m as ob jective function, the optimum value will b e zero or one, and will b e one i the circuit outputs one. The ab ove describ ed linear program can b e expressed as max t m sub ject to t k = 1 8 k 2 I n 1 t k = 0 8 k 2 I n 0 t k  t i 8 ( i; j; k ) 2 O R t k  t j 8 ( i; j; k ) 2 O R t k  t i + t j 8 ( i; j; k ) 2 O R t k = 1 ? t j 8 ( j; k ) 2 N eg 0  t i  1 8 i 2 f 1 ;:::;m g (LP1) where we used the notation I n 0 (resp. I n 1) to denote the set of indices of input gates whose value is zero (resp. one), the notation N eg to denote the set of pair of indices ( j; k ) such that g k is a NOT gate taking its input from g j , and O R to denote the set of triples ( i; j; k ) such that g k is an OR gate taking its inputs from gates g i and g j . Clearly, the program (LP1) is not an instance of PLP. Notice that in (LP1) we have some constraints which are equalities and also there are variables with negative co ecients. We will deal with b oth of them in two separate steps. We rst intro duce new variables f 1 ;:::;f m such that f i = 1 ? t i . The program b ecomes max t m sub ject to t k = 1 8 k 2 I n 1 f k = 1 8 k 2 I n 0 f k + t i  1 8 ( i; j; k ) 2 O R f k + t j  1 8 ( i; j; k ) 2 O R f i + f j + t k  2 8 ( i; j; k ) 2 O R t k + t j = 1 8 ( j; k ) 2 N eg t i + f i = 1 8 i 2 f 1 ;:::;m g t i ; f i  0 8 i 2 f 1 ;:::;m g (LP2) It should b e clear that there is a corresp ondence b etween the unique feasible solution of (LP1) and the unique feasible solution of (LP2), more formally, we have the following result. Fact 1 If t is a feasible solution for (LP1), then ( t ; 1 ? t ) is a feasible solution for (LP2), and the cost of the solutions are equal. If ( t ; f ) is a feasible solution for (LP2), then t is a feasible solution for (LP1) and the cost of the solutions are equal. 3 Note that (LP1) is not yet a packing problem, since there are equality constraints. The nal step will b e to relax them into inequality constraints and to mo dify the ob jective function in such a way that it will never b e \convenient" to strictly satisfy the relaxed constraints. We note that our technique b ears some similarity to the metho d of Lagrangean relaxations. max t m + P k 2 I n 1 t k + P k 2 I n 0 f k + P ( k ;j ) 2 N eg ( t k + t j ) + P m i =1 ( t i + f i ) sub ject to f k + t i  1 8 ( i; j; k ) 2 O R f k + t j  1 8 ( i; j; k ) 2 O R f i + f j + t k  2 8 ( i; j; k ) 2 O R t k + t j  1 8 ( j; k ) 2 N eg t i + f i  1 8 i 2 f 1 ;:::;m g t i ; f i  0 8 i 2 f 1 ;:::;m g (LP3) Lemma 1 There exists a solution for (LP3) of cost 1 + j I n 1 j + j I n 0 j + j N eg j + m if and only if there exists a solution for (LP2) of cost 1. Proof: Let K = 1 + j I n 1 j + j I n 0 j + j N eg j + m . It is immediate to verify that a feasible solution for (LP2) of cost 1 is feasible for (LP3) and its cost is K . Assume now that ( t ; f ) is feasible for (LP3) and its cost is K ; we claim that ( t ; f ) is feasible for (LP2) and that t m = 1. Indeed, the cost of a solution for (LP3) is the sum of K terms, and each one is constrained to b e at most one. If there exists a feasible solution whose cost is K , then it follows that all such terms are equal to one, and thus the solution is feasible for (LP2) and t m = 1. 2 Theorem 2 PLP in packing form is P-complete. Proof: It is immediate to check that, given the description of a circuit, the PLP instance (LP3) can b e constructed using logarithmic space. The theorem thus follows from Lemma 1. 2 The P-hardness of optimally solving PLP covering problems immediately follows from the duality theorem of linear programming (covering problems are the duals of packing problems). The P-completeness of the decision version can b e established directly by minor changes to the ab ove pro of. Remark 3 Another consequence of our result is that the extension of PLP where equality constraints are admitted is P-hard to approximate within any constant factor. This observation implies that, to a certain extent, PLP is the more general version of LP admitting NC approximation algorithms. 2.1 On FNCASs for PLP A Fully NC Approximation Scheme (FNCAS) for a combinatorial optimization problem is an algorithm that nds (1 + " )-approximate solutions in time p oly-logarithmic in n (size of the input) and 1 =" and using a p olynomial numb er of pro cessors (in n and " ). One would b e tempted to conjecture the following stronger statement of Lemma 1: If we let Z  2 (resp. Z  3 ) be the optimum solution of (LP2) (resp. (LP3)), then 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 Figure 1: A patological case for our reduction. The stronger statement would imply that PLP admits no FNCAS unless P = NC. Unfortunately, there are counterexamples of such statement. Consider the circuit and the assignment depicted in Figure 1. Note that the assignment do es not satisfy the circuit. The corresp onding (LP3) formulation is max t 2 k +1 + f 1 + f 2 + P 2 k +1 i =1 ( t i + f i ) sub ject to f k + t i  1 8 ( i; j; k ) 2 O R f k + t j  1 8 ( i; j; k ) 2 O R f i + f j + t k  2 8 ( i; j; k ) 2 O R t i + f i  1 8 i 2 f 1 ;:::;m g t i ; f i  0 8 i 2 f 1 ;:::;m g (LP3) Where m = 2 k + 1. Consider the assignment such that t 2 i ? 1 = t 2 i = 1 = 2 k +1 ? i for i = 1 ;:::;k (so, in particular, t 2 k = 1 = 2); t 2 k +1 = 1; and f i = 1 ? t i for i = 1 ;:::; 2 k + 1. It is easily seen that this assignment satises all the constraints and that its cost is 1 + j I n 1 j + j I n 0 j + j N eg j + m ? 2 1 ? k . Since k (the depth of the circuit) is linear in the size of the circuit, it follows that, in order to exactly solve the instance pro duced by our reduction, only an exp onentially small approximation can b e admitted. 3 Conclusions Our result shows that Luby and Nisan's algorithm cannot b e improved to the p oint of computing optimum solutions in NC for fractional packing and covering problems. It is still an op en question whether a FNCAS exists for PLP. 5 References [1] J.L. Balcazar, J. Daz, and J. Gabarro. Structural Complexity I. Springer Verlag, 1995. [2] E. Cohen. Approximate maxow on small depth networks. In Proceedings 37th IEEE Symposium on Foundations of Computing Science , pages 648{658, 1992. [3] J. Daz, M.J. Serna, P. Spirakis, and J. Toran. Paradigms for fast paral lel approximations. Cambridge University Press (To app ear). [4] D. Dobkin, J.R. Lipton, and S. Reiss. Linear Programming is logspace hard for P. Information Processing Letters , 8:96{97, 1979. [5] J. Edmonds. Maximum matching and a p olyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards B , 69B:125{130, 1965. [6] J. Edmonds and E. Johnson. Matching: A well-solved class of integer linear programs. In Proceedings of the Calgary International Conference on Combinatorial Structures and their Applications , pages 82{92, 1970. [7] R. Greenlaw, H.J. Ho over, and W.L. Ruzzo. Limits to paral lel computation: P{completeness theory. Oxford University Press, 1995. [8] L.G. Khachyan. A p olynomial algorithm in linear programming. Translated in Soviet Mathematics Doklady , 20:191{194, 1979. [9] R.E. Ladner. The circuit value problem is logspace complete for P. SIGACT News , 7:18{20, 1975. [10] L. Lovasz. On the ratio of optimal integral and fractional covers. Discrete Mathematics , 13:383{390, 1975. [11] M. Luby and N. Nisan. A Parallel Approximation Algorithm for Positive Linear Programming. In Proceedings 25th ACM Symposium on Theory of Computing , pages 448{457, 1993. [12] N. Megiddo. A note on approximate linear programming. Information Processing Letters , 42:53, 1992. [13] M.J. Serna. Approximating linear programming is log-space complete for P. Information Processing Letters , 37:233{236, 1991. [14] L. Trevisan. Positive Linear Programming, Parallel Approximation and PCP's. In Fourth European Symposium on Algorithms , volume 1136 of Lecture Notes in Computer Science , pages 62{75. Eds. J. Daz, and M. Serna, Springer-Verlag, 1996. 6 View publication statsView publication stats