{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:35:53Z","timestamp":1794335753710,"version":"4.9.0"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1990,12]]},"abstract":"<jats:p>The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed. Let n and m denote the number of variables and the number of inequalities, respectively, in a linear programming problem. It is assumed that all inequalities are weak. Under the concurrent-read-exclusive-write PRAM model, an $O((\\log m + \\log^2 n) \\log^2 n)$-time parallel algorithm for deciding feasibility is described. It requires $mn^{O(\\log n)}$ processors in the worst case, though it is not known whether this bound is tight. When the problem is feasible, a solution can be computed within the same complexity. Moreover, linear programming problems with at most two nonzero coefficients in the objective function can be solved in poly-log time on a similar number of processors. Consequently, all these problems can be solved sequentially with only $O((\\log m + \\log ^2 n)^2 \\log ^2 n)$ space. (These bounds assume that numbers take $O(1)$ space, and arithmetic on them takes $O(1)$ time; the problem can still be solved in poly-log space as a function of the input size even if a Turing machine model with rational input is used instead.) It is also shown that if the underlying graph has bounded tree-width and an underlying tree is given, then the feasibility problem is in the class NC.<\/jats:p>","DOI":"10.1137\/0219068","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:33:47Z","timestamp":1109226827000},"page":"1000-1010","source":"Crossref","is-referenced-by-count":5,"title":["Linear Programming with Two Variables Per Inequality in Poly-Log Time"],"prefix":"10.1137","volume":"19","author":[{"given":"George S.","family":"Lueker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nimrod","family":"Megiddo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijaya","family":"Ramachandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0209063"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0206054"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90008-X"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90152-2"},{"key":"R8","volume-title":"Flows in networks","author":"Ford, Jr. L. R.","year":"1962"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804339"},{"key":"R10","unstructured":"L. M. Goldschlager,  Synchronous parallel computation, Tech. Report, 114, Department of Computer Science, University of Toronto, Toronto, Ontario, Canada,  1977, December"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90092-5"},{"key":"R12","unstructured":"D. Helmbold, E. Mayr,  Fast scheduling problems on parallel computers, Report, STAN-CS-84-1025, Computer Science Department, Stanford University, Stanford, CA,  1984"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"R14","first-page":"191","volume":"20","author":"Khachiyan L. G.","year":"1979","journal-title":"Soviet Math. Dokl."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0212022"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322410"},{"key":"R17","unstructured":"C. G. Nelson,  An  nO(logn) algorithm for the two-variable-per-constraint linear programming satisfiability problem, Report, STAN-CS-76-689, Department of Computer Science, Stanford University, Stanford, CA,  1978, November"},{"key":"R18","first-page":"399","volume-title":"Progress in graph theory (Waterloo, Ont., 1982)","author":"Robertson Neil","year":"1984"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322288"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0213027"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0219068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:46Z","timestamp":1787337766000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0219068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,12]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1990,12]]}},"alternative-id":["10.1137\/0219068"],"URL":"https:\/\/doi.org\/10.1137\/0219068","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,12]]}}}