@string{focsorg={Comp. Soc. of the IEEE}} @string{focspub={IEEE}} @string{focs1={Proc. 1st IEEE Annual Symposium on Switching and Automata Theory}} @string{focs2={Proc. 2nd IEEE Annual Symposium on Switching and Automata Theory}} @string{focs3={Proc. 3rd IEEE Annual Symposium on Switching and Automata Theory}} @string{focs4={Proc. 4th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs5={Proc. 5th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs6={Proc. 6th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs7={Proc. 7th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs8={Proc. 8th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs9={Proc. 9th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs10={Proc. 10th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs11={Proc. 11th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs12={Proc. 12th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs13={Proc. 13th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs14={Proc. 14th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs15={Proc. 15th IEEE Annual Symposium on Switching and Automata Theory}} @string{focs16={Proc. 16th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs17={Proc. 17th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs18={Proc. 18th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs19={Proc. 19th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs20={Proc. 20th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs21={Proc. 21th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs22={Proc. 22th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs23={Proc. 23th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs24={Proc. 24th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs25={Proc. 25th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs26={Proc. 26th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs27={Proc. 27th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs28={Proc. 28th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs29={Proc. 29th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs30={Proc. 30th IEEE Annual Symposium on Foundations of Computer Science}} @string{focs31={Proc. 31st IEEE Annual Symposium on Foundations of Computer Science}} @string{focs32={Proc. 32nd IEEE Annual Symposium on Foundations of Computer Science}} @string{focs33={Proc. 33rd IEEE Annual Symposium on Foundations of Computer Science}} @string{focs34={Proc. 34th IEEE Annual Symposium on Foundations of Computer Science}} @string{podcorg={ACM SIGACT and SIGOPS}} @string{podcpub={ACM}} @string{podc1={Proc. 1st Annual ACM Symposium on Principles of Distributed Computing}} @string{podc2={Proc. 2nd Annual ACM Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada}} @string{podc3={Proc. 3rd Annual ACM Symposium on Principles of Distributed Computing}} @string{podc4={Proc. 4th Annual ACM Symposium on Principles of Distributed Computing}} @string{podc5={Proc. 5th Annual ACM Symposium on Principles of Distributed Computing}} @string{podc6={Proc. 6th Annual ACM Symposium on Principles of Distributed Computing}} @string{podc7={Proc. 7th Annual ACM Symposium on Principles of Distributed Computing}} @string{podc8={Proc. 8th Annual ACM Symposium on Principles of Distributed Computing}} @string{stocorg={ACM SIGACT}} @string{stocpub={ACM}} @string{stoc1={Proc. 1st Annual ACM Symposium on Theory of Computing}} @string{stoc2={Proc. 2nd Annual ACM Symposium on Theory of Computing}} @string{stoc3={Proc. 3rd Annual ACM Symposium on Theory of Computing}} @string{stoc4={Proc. 4th Annual ACM Symposium on Theory of Computing}} @string{stoc5={Proc. 5th Annual ACM Symposium on Theory of Computing}} @string{stoc6={Proc. 6th Annual ACM Symposium on Theory of Computing}} @string{stoc7={Proc. 7th Annual ACM Symposium on Theory of Computing}} @string{stoc8={Proc. 8th Annual ACM Symposium on Theory of Computing}} @string{stoc9={Proc. 9th Annual ACM Symposium on Theory of Computing}} @string{stoc10={Proc. 10th Annual ACM Symposium on Theory of Computing}} @string{stoc11={Proc. 11th Annual ACM Symposium on Theory of Computing}} @string{stoc12={Proc. 12th Annual ACM Symposium on Theory of Computing}} @string{stoc13={Proc. 13th Annual ACM Symposium on Theory of Computing}} @string{stoc14={Proc. 14th Annual ACM Symposium on Theory of Computing}} @string{stoc15={Proc. 15th Annual ACM Symposium on Theory of Computing}} @string{stoc16={Proc. 16th Annual ACM Symposium on Theory of Computing}} @string{stoc17={Proc. 17th Annual ACM Symposium on Theory of Computing}} @string{stoc18={Proc. 18th Annual ACM Symposium on Theory of Computing}} @string{stoc19={Proc. 19th Annual ACM Symposium on Theory of Computing}} @string{stoc20={Proc. 20th Annual ACM Symposium on Theory of Computing}} @string{stoc21={Proc. 21st Annual ACM Symposium on Theory of Computing}} @string{stoc22={Proc. 22nd Annual ACM Symposium on Theory of Computing}} @string{stoc23={Proc. 23th Annual ACM Symposium on Theory of Computing}} @string{stoc24={Proc. 24th Annual ACM Symposium on Theory of Computing}} @string{stoc25={Proc. 25th Annual ACM Symposium on Theory of Computing}} @string{stoc26={Proc. 26th Annual ACM Symposium on Theory of Computing}} @string{stoc27={Proc. 27th Annual ACM Symposium on Theory of Computing}} @string{stoc28={Proc. 28th Annual ACM Symposium on Theory of Computing}} @string{soda1={Proc. 1st ACM-SIAM Symposium on Discrete Algorithms}} @string{soda2={Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms}} @string{soda3={Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms}} @string{soda4={Proc. 4th ACM-SIAM Symposium on Discrete Algorithms}} @string{soda5={Proc. 5th ACM-SIAM Symposium on Discrete Algorithms}} @string{actainf={Acta Informatica}} @string{acmtocs={ACM Trans. Comp. Syst.}} @string{acmtopls={ACM Trans. Prog. Lang. and Syst.}} @string{belltech={Bell System Tech. J.}} @string{bullams={Bull. Amer. Math. Soc.}} @string{cacm={Comm. ACM}} @string{compsurv={ACM Comp. Surveys}} @string{discmath={Discrete Math.}} @string{ibmjrd={IBM J. Res. and Devel.}} @string{ieeeac={IEEE Trans. Auto. Control}} @string{ieeec={IEEE Trans. Computers}} @string{ieeecom={IEEE Trans. Comm.}} @string{ieeeit={IEEE Trans. Inform. Theory}} @string{ieeese={IEEE Trans. Software Eng.}} @string{interfaces={Interfaces}} @string{ipl={Information Processing Letters}} @string{jacm={J. Assoc. Comput. Mach.}} @string{jalg={J. Alg.}} @string{jcss={J. Comput. Syst. Sci.}} @string{laa={Linear Algebra Appl.}} @string{mansci={Management Sci.}} @string{mathann={Mathematische Annalen}} @string{mathprog={Math. Programming}} @string{mathprogst={Math. Programming Stud.}} @string{mor={Math. of Oper. Res.}} @string{networks={Networks}} @string{or={Oper. Res.}} @string{orl={Oper. Res. Lett.}} @string{orq={Oper'l. Res. Quart.}} @string{paracomp={Parallel Computing}} @string{siamj={J. SIAM}} @string{siamalgdisc={SIAM J. Alg. and Disc. Meth.}} @string{siamapmath={SIAM J. Applied Math.}} @string{siamcomp={SIAM J. Comput.}} @string{siamdisc={SIAM J. Disc. Math.}} @string{siamcon={SIAM J. Control Optim.}} @string{siamnum={SIAM J. Numer. Anal.}} @string{siamopt={SIAM J. Optim.}} @string{siamx={SIAM J. Matrix Anal. Appl.}} @string{siamanal={SIAM J. Math. Anal.}} @string{siamrev={SIAM Rev.}} @string{siamsci={SIAM J. Scient. Comp.}} @string{sigactnews={SIGACT News}} @string{sovietmath={Soviet Math. Dokl.}} @string{theorcs={Theor. Comp. Sci.}} @string{transci={Transport. Sci.}} @string{columbiabus={Columbia Grad. Sch. of Bus.}} @string{daviscse={U. California, Davis, Dept.\ CS and Eng.}} @string{erasmusecon={Erasmus U. Econometric Inst.}} @string{mathcent={Mathematisch Centrum}} @string{mit={Massachusetts Institute of Technology}} @string{mitai={MIT AI Lab.}} @string{miteecs={MIT Dept.\ of Electrical Engineering and Computer Science}} @string{mitlcs={MIT Lab.\ for Computer Science}} @string{mitlids={MIT Lab.\ for Information and Decision Systems}} @string{mitmath={MIT Dept.\ of Mathematics}} @string{mitsloan={MIT Sloan School of Management}} @string{stanfordcs={Stanford U. Computer Science Dept.}} @string{yalecs={Yale Dept.\ Comp. Sci.}} @string{academicp={Academic Press}} @string{addison={Addison-Wesley Publishing Co.}} @string{birkhauser={Birkhauser}} @string{csp={Computer Science Press}} @string{dover={Dover Publications, Inc.}} @string{freeman={W. H. Freeman and Co.}} @string{holt={Holt, Rinehart and Winston}} @string{hopkins={The Johns Hopkins U. Press}} @string{macmillan={Macmillan Publishing Co., Inc.}} @string{mcgraw={McGraw-Hill Book Co.}} @string{mitp={MIT Press}} @string{nholland={North-Holland Publishing Co.}} @string{prentice={Prentice-Hall, Inc.}} @string{princeton={Princeton U. Press}} @string{siam={Society for Industrial and Applied Mathematics}} @string{springer={Springer-Verlag}} @string{wiley={John Wiley \& Sons}} @string{yale={Yale U. Press}} @string{ny={New York}} @STRING{IPL = "Information Processing Let."} @STRING{SJC = "SIAM J. Comput."} @inproceedings{AA-87, author = {A. Aggarwal and R. J. Anderson}, title = {{A Random {NC} Algorithm for Depth First Search}}, booktitle = stoc19, pages = {325--334}, year = 1987 } @techreport{AA-95, author = {I. Adler and F. Alizadeh}, title = {{Primal-Dual Interior Point Algorithms for Convex Quadratically Constrained and Semidefinite Optimization Problems}}, institution = {{RUTCOR, Rutgers University}}, year = {1995}, number = {RRR-111-95} } @inproceedings{AAK-89, author = {A. Aggarwal and R. J. Anderson and M.-Y. Kao}, title = {{Parallel Depth-First Search in General Directed Graphs}}, booktitle = stoc21, pages = {297--308}, year = 1989 } @inproceedings{AAPS-87, author = {Y. Afek and B. Awerbuch and S. Plotkin and M. Saks}, title = {{Local Management of a Global Resource in a Communication Network}}, booktitle = focs28, pages = {347--357}, year = 1987 } @unpublished{AB-89, author = {K. M. Anstriecher and R. A. Bosch}, title = {{Long Steps in an {$O(n^3L)$} Algorithm for linear programming}}, year = 1989, note = {Unpublished manuscript, Yale School of Management, Yale University} } @book{ADK-75, author = {G. M. Adel'son-Vel'ski and E. A. Dinits and A. V. Karzanov}, title = {Flow Algorithms}, year = 1975, publisher = {Nauka, Moscow}, note = {In Russian} } @article{AG-87, author = {B. Awerbuch and R. G. Gallager}, title = {{A New Distributed Algorithm to Find Breadth First Search Trees}}, journal = {IEEE Trans. Info. Theory}, pages = {315--322}, year = 1987, volume = {IT-33} } @incollection{AG-91, author = {F. Alizadeh and A. V. Goldberg}, editor = {David S. Johnson and Catherine C. McGeoch}, title = {{Implementing the Push-Relabel Method for the Maximum Flow Problem on a Connection Machine}}, booktitle = {Network Flows and Matching, Fisrt DIMACS Implementation Challenge}, year = 1993, publisher = {American Mathematical Society}, volume = 12, series = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science} } @inproceedings{AGLP-89, author = {B. Awerbuch and A. V. Goldberg and M. Luby and S. A. Plotkin}, title = {{Network Decomposition and Locality in Distributed Computation}}, booktitle = focs30, pages = {364--369}, year = 1989 } @techreport{AGOT-88, author = {R. K. Ahuja and A. V. Goldberg and J. B. Orlin and R. E. Tarjan}, title = {{Finding Minimum-Cost Flows by Double Scaling}}, institution = {Department of Computer Science, Stanford University}, year = 1988, number = {STAN-CS-88-1227} } @inproceedings{AHO-94a, author = {F. Alizadeh and J. P. Haeberly and M. L. Overton}, title = {A New Primal-Dual Interior Point Method for Semidefinite Programming}, booktitle = {{Proc. 5th SIAM Conference on Appl. Linear Algebra}}, year = 1994, address = {{Snowbird, Utah}} } @unpublished{AHO-94b, author = {F. Alizadeh and J. P. Haeberly and M. L. Overton}, title = {Primal-Dual Interior-Point Methods for Semidefinite Programming}, year = 1994, note = {{Presented at Mathematical Programming Symposium, Ann Arbor, MI}} } @article{AHO-96, author = {F. Alizadeh and J. P. Haeberly and M. L. Overton}, title = {Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results}, journal = siamopt, year = 1996, note = {{To appear}} } @article{AHO-97, author = {F. Alizadeh and J. P. Haeberly and M. L. Overton}, title = {Complementarity and Nondegeneracy in Semidefinite PRogramming}, journal = mathprog, year = 1997, volume = 77, number = 2 } @techreport{AS-97, Author = {F.~Alizadeh and S.~Schmieta}, title = {{Optimization with Semidefinite, Quadratic and Linear Constraints}}, institution = {{RUTCOR, Rutgers University}}, month = {November}, year = 1997, number = {rrr 23-97}, address = {{640 Bartholomew Road, Piscataway, NJ 08854-8803}}, note = {{Available at URL: {\tt http://rutcor.rutgers.edu/pub/rrr/reports97/23.ps.gz}}} } @book{AHU-74, author = {A. V. Aho and J. E. Hopcroft and J. D. Ullman}, title = {The Design and Analysis of Computer Algorithms}, year = 1974, publisher = {Addison-Wesley} } @inproceedings{AKNW-93, author = {Farid Alizadeh and Richard M. Karp and Lee A. Newberg and Deborah K. Weisser}, title = {{Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology}}, booktitle = soda4, year = 1993, note = {{(to appear in {\em Algorithmica})}} } @inproceedings{AKWZ-94, author = {Farid Alizadeh and Richard M. Karp and Deborah K. Weisser and Geoffry Zweig}, title = {{Physical Mapping of Chromosomes Using Unique Probes}}, booktitle = soda5, year = 1994 } @inproceedings{ALMSS-92a, author = {Sanjeev Arora and Carsten Lund and Rajeev Motwani and Madhu Sudan and Mario Szegedy}, title = {Proof Verification and Hardness of Approximation Problems}, booktitle = focs33, pages = {14--23}, year = 1992 } @article{AMO-91, author = {R. K. Ahuja and T. Magnanti and J. B. Orlin}, title = {{Some Recent Advances in Network Flows}}, journal = siamrev, year = 1991, volume = 33, number = 2 } @techreport{AMOT-88, author = {R. K. Ahuja and K. Mehlhorn and J. B. Orlin and R. E. Tarjan}, title = {{Faster Algorithms for the Shortest Path Problem}}, institution = {Department of Computer Science, Princeton University}, year = 1987, number = {CS-TR-154-88} } @book{AN-87, author = {E. Anderson and P. Nash}, title = {Linear Programming in Infinite Dimensional Spaces}, year = 1987, publisher = {John Wiley \& Sons}, address = {New York} } @article{ACO-94, author = {K.~D.~Andersen and E.~Christiansen and M.~L.~Overton}, title = {{Limit Analysis by Minimizing a Sum of Norms}}, journal = siamsci, year = 1994, volume = {}, number = {} } @unpublished{AO-86, author = {R. K. Ahuja and J. B. Orlin}, title = {{A Simple ${O}(nm + n^2 \log c_{max})$ Sequential Algorithm for the Maximum Flow Problem}}, year = 1986, note = {Unpublished manuscript, M.I.T.} } @unpublished{AO-87-2, author = {R. K. Ahuja and J. B. Orlin}, title = {{A Fast and Simple Algorithm for the Maximum Flow Problem}}, year = 1987, note = {Sloan Working Paper 1905-87, Sloan School of Management, M.I.T.} } @unpublished{AO-88, author = {R. K. Ahuja and J. B. Orlin}, title = {{New Scaling Algorithms for Assignment and Minimum Cycle Mean Problems}}, year = 1988, note = {Unpublished manuscript, to appear} } @techreport{AOT-87, author = {R. K. Ahuja and J. B. Orlin and R. E. Tarjan}, title = {{Improved Time Bounds for the Maximum Flow Problem}}, institution = {Department of Computer Science, Princeton University}, year = 1987, number = {CS-TR-118-87}, note = {(SIAM J. Comput., to appear)} } @inproceedings{AS-83, author = {B. Awerbuch and Y. Shiloach}, title = {New Connectivity and MSF Algorithms for Ultracomputer and PRAM}, booktitle = {Proc. of International Conference on Parallel Processing}, pages = {175--179}, year = 1983 } @article{BCK-69, author = {A. Ben-Israel and A. Charnes and K. O. Kortanek}, title = {{Duality and Asymptotic Solvability over Cones}}, journal = bullams, pages = {318--324}, year = 1969, volume = 75, number = 2 } @techreport{BDHPRS-89, author = {P. C. P. Bhatt and K. Diks and T. Hagerup and V. C. Prasad and T. Radzik and S. Saxena}, title = {{Improved Deterministic Parallel Integer Sorting}}, institution = {Univ. Saarbruecken}, year = 1989, number = {H124} } @inproceedings{BE-87, author = {D. P. Bertsekas and J. Eckstein}, title = {Distributed Asynchronous Relaxation Methods for Linear Network Flow Problems}, booktitle = {Proc. IFAC '87, Munich, Germany}, year = 1987 } @article{BE-88, author = {D. P. Bertsekas and J. Eckstein}, title = {{Dual Coordinate Step Methods for Linear Network Flow Problems}}, journal = {Math. Programming}, pages = {203--243}, year = 1988, volume = 42 } @book{BEFB-94, author = {{Boyd, Stephen and El Ghaoui, Laurent and Feron, Eric and Balakrishnan, Venkataramanan}}, title = {Linear Matrix Inequalities in System and Control Theory}, year = 1994, publisher = {SIAM}, address = {Philadelphia PA}, volume = 15, series = {SIAM Studies in Applied Mathematics} } @techreport{BG-61, author = {R. G. Busacker and P. J. Gowen}, title = {{A Procedure for Determinimg a Family of Minimal-Cost Network Flow Patterns}}, institution = {O.R.O.}, year = 1961, number = 15 } @article{BG-84, author = {R. K. Ghosh and G. P. Bhattacharjee}, title = {{A Parallel Search Algorithm for Directed Acyclic Graphs}}, journal = {BIT}, pages = {134--150}, year = 1984, volume = 24 } @article{BG-93, author = {Stephen Boyd and Laurent El Ghaoui}, title = {Method of Centers for Minimizing Generalized Eigenvalues}, journal = laa, pages = {{63--112}}, year = {1993}, volume = {{188,189}} } @inproceedings{BGI-87, author = {R. Bar-Yehuda, O. Goldreich, A. Itai}, title = {On the Time-Complexity of Broadcast in Radio Networks: An Exponential Gap Between Determinism and Randomization}, booktitle = podc6, pages = {98--108}, year = 1987 } @incollection{BH-84, author = {E. Barnes and A. J. Hoffman}, editor = {W.~E.~Pulleyblank}, title = {{Partitioning, spectra, and linear programming}}, booktitle = {Progress in Combinatorial Optimization}, year = 1984, publisher = {{Academic Press}}, address = {{New York}} } @article{BH-85, author = {A. Borodin and J. E. Hopcroft}, title = {{Routing, merging, and sorting on parallel models of computation}}, journal = jcss , pages = {130--145}, year = {1985}, volume = {30} } @inproceedings{BH-87, author = {P. Beame and J. Hastad}, title = {Optimal Bounds for Decision Problems on the {CRCW PRAM}}, booktitle = stoc19, year = 1987 } @techreport{BJ-86, author = {R. G. Bland and D. L. Jensen}, title = {{On the Computational Behavior of a Polynomial-Time Network Flow Algorithm}}, institution = {School of Operations Research and Industrial Engineering, Cornell University}, year = 1985, number = {661} } @book{BJS-90, author = {M. Bazaraa and J. Jarvis and H. Sherali}, title = {Linear Programming and Network Flows}, year = 1990, publisher = {{John Wiley \& Sons}}, address = {{New York}} } @article{BK-86, author = {J. Boyar and H. J. Karloff}, title = {Coloring planar graphs in parallel}, journal = {J. of Algorithms}, year = 1987, note = {(To appear)} } @techreport{BN-92, author = {A. Ben-Tal and A. Nemirovskii\}, title = {Interior Point Polynomial Time Methods for Truss Topology Design}, institution = {{Technion, Haifa, Israel}}, year = 1992, number = {3/92} } @book{BS-65, author = {R. G. Busacker and T. L. Saaty}, title = {{Finite Graphs and Networks: An Introduction with Applications}}, year = 1965, publisher = {Mcraw-Hill, New York, NY.} } @book{BS-79, author = {M. Bazaraa and C. Shetty}, title = {{Nonlinear Programming, Theory and Algorithms}}, year = 1979, publisher = {{John Wiley}}, address = {{New York}} } @article{BT, author = {F. Barahona and \'E. Tardos}, title = {{Note on {W}eintraub's Minimum Cost Circulation Algorithm}}, journal = {SIAM J. Comput.}, year = {to appear} } @article{BT-86, author = {D. P. Bertsekas and P. Tseng}, title = {Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems}, journal = or, year = {to appear} } @book{BT-89, author = {D. P. Bertsekas and J. N. Tsitsiklis}, title = {Parallel and Distributed Computation: Numerical Methods}, year = 1989, publisher = {Prentice Hall}, address = {{Englewood Cliffs, NJ}} } @book{ber-95, author = {D.~P.~Bertsikas}, title = {{Nonlinear Programming}}, year = 1995, publisher = {Athena Press}, optaddress= {} } @article{BW-81a, author = {J. M. Borwein and H.~Wolkowicz}, title = {Facial reduction for a cone-convex programming problem}, journal = {J. Austral. Math. Soc. Ser. A}, pages = {369--380}, year = 1981, volume = 30 } @article{BW-81b, author = {J. M. Borwein and H.~Wolkowicz}, title = {Characterization of Optimality for the abstract convex program with finite dimensional range}, journal = {J. Austral. Math. Soc. Ser. A}, pages = {390--411}, year = 1981, volume = 30 } @article{BY-89, author = {S.~Boyd and Q.~Yang}, title = {Structured and simultaneous Lyapunov functions for system stability}, journal = {Int. J. Control}, pages = {2215--2240}, year = 1989, volume = 49, number = 6 } @article{Ber-84, author = {S.~Berkowitz}, title = {{On Computing the Determinant in Small Parallel Time Using a Small Number of Processors}}, journal = ipl, pages = {147--150}, year = 1984, volume = 18 } @book{Bol-85, author = {Bella Bollobas}, title = {Random Graphs}, year = 1985, publisher = {Academic Press} } @book{CDS-79, author = {D.~M.~Cvetkovic, M.~Doob, and H.~Sachs}, title = {Spectra of Graphs}, year = 1979, publisher = {Academic Press} } @article{CDW-75, author = {J.~Cullum and W.~E.~Donath and P.~Wolfe}, title = {The minimization of certain nondifferentiable sums of eigenvalue problems}, journal = mathprogst, pages = {35--55}, year = 1975, volume = 3 } @techreport{CF-87, author = {W. Chi and S. Fujishige}, title = {{A Primal Algorithm for the Submodular Flow Problem with Minimum-Mean Cycle Selection}}, institution = {University of Tsukuba, Japan}, year = 1987, number = 350 } @inproceedings{CFL-83, author = {A. K. Chandra and S. Fortune and R. Lipton}, title = {Unbounded Fan-in Circuits and Associative Functions}, booktitle = stoc15, pages = {52--60}, year = 1983, month = apr } @article{CGST-86, author = {W. Cook and A. M. H. Gerards and A. Schrijver and \'E. Tardos}, title = {Sensitivity Theorems in Integer and Linear Programming}, journal = {Math. Programming}, pages = {251--264}, year = 1986, volume = 34 } @article{CH-82, author = {R. Cole and J. Hopcroft}, title = {{On Edge Coloring Bipartite Graphs}}, journal = SJC, pages = {540--546}, year = 1992, volume = 11 } @inproceedings{CH-89, author = {J. Cheriyan and T. Hagerup}, title = {A Randomized Maximum Flow Algorithm}, booktitle = focs30, pages = {118--123}, year = 1989 } @article{CK-77, author = {B. D. Craven and J. J. Koliha}, title = {{Generalizations of Farkas' Theorem}}, journal = siamanal , pages = {983--997}, year = 1977, volume = 8, number = 6 } @techreport{CKR-90, author = {M. Chrobak and H. Karloff and T. Radzik}, title = {{Connectivity vs. Reachability}}, institution = {Dept. of Math. and CS, University of California at Riverside}, year = 1990, number = {UCR-CS-90-3} } @article{CKS-81, author = {A. K. Chandra and D. C. Kozen and L. Stockmeyer}, title = {Alternation}, journal = jacm, pages = {114--133}, year = 1981, month = jan, volume = 28, number = 1 } @article{CKS-81a, author = {A. K. Chandra and D.C. Kozen and L. Stockmeyer}, title = {Alternation}, journal = jacm, pages = {114--133}, year = 1981, month = {January}, volume = 28, number = 1 } @book{CLR-90, author = {T. H. Cormen and C. E. Leiserson and R. L. Rivest}, title = {{Introduction to Algorithms}}, year = 1990, publisher = {MIT Press, Cambridge, MA} } @article{CM-81, author = {B. D. Craven and B. Mond}, title = {{Linear Programming with Matrix Variables}}, journal = laa, pages = {73--80}, year = 1981, volume = 38 } @unpublished{CM-87, author = {J. Cheriyan and S. N. Maheshwari}, title = {{Analysis of a Preflow Push Algorithm for Maximum Netwrok Flow}}, year = 1987, note = {Unpublished manuscript, Department of Computer Science and Engineering, Indian Institute of Technology, New Deli, India} } @inproceedings{CM-89, author = {E. Cohen and N. Megiddo}, title = {{Strongly Polynomial Time and NC Algorithms for Detecting Cycles in Dynamic Graphs}}, booktitle = stoc21, year = 1989 } @techreport{CM-90, author = {E. Cohen and N. Megiddo}, title = {{Recognizing Properties of Periodic Graphs}}, institution = {IBM Almaden}, year = 1990, number = {RJ 7246 (68013)} } @unpublished{CO-94, author = {Andrew R. Conn and Michael Overton}, title = {{A Primal-Dual Interior Point Method for Minimizing a Sum of Euclidean Distances}}, year = 1994, note = {Presented in Mathematical Programming Symposium, Ann Arbor} } @inproceedings{CSV-82, author = {A. K. Chandra and L. J. Stockmeyer and U. Vishkin}, title = {{A Complexity Theory for Unbounded Fan-in Parallelism}}, booktitle = focs23, pages = {1--13}, year = 1982 } @inproceedings{CV-86, author = {R. Cole and U. Vishkin}, title = {{Deterministic Coin Tossing and Accelerating Cascades: Micro and Macro Techniques for Designing Parallel Algorithms}}, booktitle = stoc18, pages = {206--219}, year = 1986 } @article{CV-86-2, author = {R. Cole and U. Vishkin}, title = {{Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking}}, journal = {Information and Control}, pages = {32--53}, year = 1986, volume = 70 } @article{CVS-84, author = {A. K. Chandra and L. Stockmeyer and U. Vishkin}, title = {{Constant Depth Reducibility}.}, journal = SJC, pages = {423--439}, year = 1984, month = {May}, volume = 13 } @article{ChM-89, author = {J. Cheriyan and S. N. Maheshwari}, title = {{Analysis of Preflow Push Algorithms for Maximum Netwrok Flow}}, journal = SJC, pages = {1057--1086}, year = 1989, volume = 18 } @inproceedings{DDPW-83, author = {D. Dolev and C. Dwork and N. Pippenger and A. Wigderson}, title = {Superconcentrators, Generalizers, and Generalized Connectors with Limited Depth}, booktitle = stoc15, pages = {42--51}, year = 1983, month = apr } @article{DFK-91, author = {Martin Dyer and Alan Frieze and Ravi Kannan}, title = {A Random Polynomial-Time Algorithm for Approximating the Volume of Convex Bodies}, journal = jacm, pages = {1--17}, year = 1991, volume = 38, number = 1 } @article{DH-72, author = {W.~E.~Donath and A.~J.~Hoffman}, title = {Algorithms for partitioning graphs and computer logic based on eigenvectors of connection matrices}, journal = {IBM Technical Disclosure Bulletin}, year = 1972, volume = 15 } @article{DH-73, author = {W.~E.~Donath and A.~J.~Hoffman}, title = {Lower bounds for the partitioning of graphs}, journal = ibmjrd, year = 1973, volume = 17 } @inproceedings{DHK-88, author = {E. Dahlaus and P. Hajnal and M. Karpinski}, title = {{Optimal Parallel Algorithm for the Hamiltonial Cycle Problem on Dense Graphs}}, booktitle = focs29, pages = {186--193}, year = 1988 } @article{DM-89, author = {U. Derigs and W. Meier}, title = {{Implementing Goldberg's Max-Flow-Algorithm---A Computational Investigation}}, journal = {ZOR-Methods and Models of Operations Research}, pages = {383--403}, year = 1989, volume = 33 } @article{DP-93, author = {C. Delorme and S. Poljak}, title = {Laplacian eigenvalues and the maximum cut problem}, journal = mathprog, pages = {557,574}, year = 1993, volume = 62, number = 3 } @article{DS-80, author = {E. W. Dijkstra and C. S. Scholten}, title = {Termination Detection for Diffusing Computations}, journal = IPL, pages = {1--4}, year = 1980, volume = 11 } @article{DSST-89, author = {J. R. Driscoll and N. Sarnak and D. D. Sleator and R. E. Tarjan}, title = {{Making Data Structures Persistent}}, journal = {J. Comput. Sys. Sci.}, pages = {86--124}, year = 1989, volume = 38 } @article{EGK-79, author = {J. Elam and F. Glover and D. Klingman}, title = {A Strongly Convergent Primal Simplex Algorithm for Generalized Networks}, journal = {Math. of O. R.}, pages = {39--59}, year = 1979, volume = 4 } @article{EK-72, author = {J. Edmonds and R. M. Karp}, title = {{Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems}}, journal = jacm, pages = {248--264}, year = 1972, volume = 19 } @unpublished{EM-90, author = {T. R. Ervolina and S. T. McCormick}, title = {{A Strongly Polynomial Maximum Mean Cut Cancelling Algorithm for Minimum Cost Network Flow}}, year = 1990, note = {UBC Faculty of Commerce Working Paper 90-MSC-009} } @unpublished{EM-90--2, author = {T. R. Ervolina and S. T. McCormick}, title = {{A Strongly Polynomial Dual Cancel and Tighten Algorithm for Minimum Cost Network Flow}}, year = 1990, note = {UBC Faculty of Commerce Working Paper 90-MSC-010} } @article{ES-75, author = {G. M. Engel and H. Schneider}, title = {{Diagonal Similarity and Equivalence for Matrices Over Groups with 0}}, journal = {Czech.\ Math.\ J.}, pages = {389--403}, year = 1975, volume = 25 } @article{ET-75, author = {S. Even and R. E. Tarjan}, title = {{Network Flow and Testing Graph Connectivity}}, journal = SJC, pages = {507--518}, year = 1975, volume = 4 } @book{FK-94, author = {J.~Faraut and A.~Kor\'{a}nyi}, title = {Analysis on Symmetric Cones}, year = 1994, publisher = {Oxford University Press}, address = {{Oxford, UK}} } @article{fay-97a, author = {L.~Faybusovich}, title = {{Linear systems in Jordan algebras and primal-Dual interior point algorithms}}, journal = {{Journal of Computational and Applied Mathematics}}, pages = {149--175}, year = 1997, volume = 86 } @incollection{fay-97b, author = {L.~Faybusovich}, title = {{Euclidean Jordan Algebras and Interior-Point Algorithms}}, booktitle = {{Positivity I}}, pages = {331--357}, year = 1997, publisher = {{Kluwer Academic Pubishers}} } @article{FF-56, author = {Ford, Jr., L. R. and D. R. Fulkerson}, title = {{Maximal Flow Through a Network}}, journal = {Canadian Journal of Math.}, pages = {399--404}, year = 1956, volume = 8 } @book{FF-62, author = {Ford, Jr., L. R. and D. R. Fulkerson}, title = {Flows in Networks}, year = 1962, publisher = {Princeton Univ. Press, Princeton, NJ} } @techreport{FGP-91, author = {T. Fischer and A. V. Goldberg and S. Plotkin}, title = {{Approximating Matchings in Parallel}}, institution = {Department of Computer Science, Stanford University}, year = 1991, number = {STAN-CS-91-1369} } @unpublished{FJ-94, author = {A. Frieze and M. Jerum}, title = {{Improved approximation algorithms for MAX-$k$-CUT snd MAX BISECTION}}, year = 1994, note = {{Manuscript}} } @inproceedings{FL-92, author = {U. Feige and L. Lov\'{a}sz}, title = {Two-prover one-round proof systems: their power and their problems}, booktitle = stoc24, pages = {733--744}, year = 1992 } @book{FM-68, author = {A.~Fiacco and G.~McCormick}, title = {{Nonlinear Programming, Sequential Unconstrained Minimization Techniques}}, year = 1968, publisher = {Research Analysis Corporation}, note = {{New edition, SIAM, 1990}} } @inproceedings{FMRW-85, author = {F. E. Fich and F. Meyer auf der Heide and P. Ragde and A. Wigderson}, title = {On, Two,Three \ldots Infinity: Lower Bounds for Parallel Computation}, booktitle = stoc17, pages = {48--58}, year = 1985 } @article{FNO-87, author = {S.~Friedland and J.~Nocedal and M.~ L. Overton}, title = {The Formulation and Analysis of Numerical Methods for Inverse Eigenvalue Problems}, journal = siamnum, pages = {634--557}, year = 1987, volume = 24, number = 3 } @inproceedings{FSS-81, author = {M. Furst and J. Saxe and M. Sipser}, title = {Parity,circuits, and the polynomial time hierarchy}, booktitle = focs22, pages = {260--270}, year = 1981 } @inproceedings{FT-84, author = {M. L. Fredman and R. E. Tarjan}, title = {Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms}, booktitle = focs25, pages = {338--346}, year = 1984 } @article{FT-87, author = {M. L. Fredman and R. E. Tarjan}, title = {{Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms}}, journal = jacm, pages = {596--615}, year = 1987, volume = 34 } @article{FW-71, author = {P. A. Fillmore and J. P. Williams}, title = {Some Convexity Theorems for Matrices}, journal = {Glasgow Math. J.}, pages = {110--117}, year = 1971, volume = 12 } @inproceedings{FW-78, author = {S. Fortune and J. Wyllie}, title = {{Parallelism in Random Access Machines}}, booktitle = stoc10, pages = {114--118}, year = 1978 } @article{GG-88, author = {D. Goldfarb and M. D. Grigoriadis}, title = {{A Computational Comparison of the Dinic and Network Simplex Methods for Maximum Flow}}, journal = {Annals of Oper.\ Res.}, pages = {83--123}, year = 1988, volume = 13 } @techreport{GG-90, author = {A. V. Goldberg and D. Gusfield}, title = {{Book Review: {\cyrm Potokovye Algoritmy} (Flow Algorithms) by G. M. Adel'son-Vel'ski, E. A. Dinic, and A. V. Karzanov}}, institution = {Department of Computer Science, Stanford University}, year = 1990, number = {STAN-CS-89-1313} } @article{GG-91, author = {A. V. Goldberg and D. Gusfield}, title = {{Book Review: {\cyrm Potokovye Algoritmy} (Flow Algorithms) by G. M. Adel'son-Vel'ski, E. A. Dinits, and A. V. Karzanov}}, journal = {SIAM Review}, pages = {306--314}, year = 1991, volume = 33 } @article{GGKMRS-83, author = {A. Gottlieb and R. Grishman and C. P. Kruskal and K. M. McAuliffe and L. Rudolf and M. Snir}, title = {The {NYU} Ultracomputer---Designing a {MIMD} Shared Memory Parallel Computer}, journal = {IEEE Trans. Comput}, pages = {175--189}, year = 1983, volume = 32 } @article{GGT-, author = {A. V. Goldberg and M. D. Grigoriadis and R. E. Tarjan}, title = {{The Use of Dynamic Trees in a Network Simplex Algorithm for the Maximum Flow Problem}}, journal = mathprog, pages = {277--290}, year = 1991, volume = 50 } @techreport{GGT-87, author = {G. Gallo and M. D. Grigoriadis and R. E. Tarjan}, title = {A Fast Parametric Maximum Flow Algorithm}, institution = {Laboratory for Computer Science Research, Department of Computer Science, Rutgers University}, year = 1987, number = {LCSR-TR-95} } @techreport{GGT-88, author = {A. V. Goldberg and M. D. Grigoriadis and R. E. Tarjan}, title = {{Efficiency of the Network Simplex Algorithm for the Maximum Flow Problem}}, institution = {Laboratory for Computer Science Research, Department of Computer Science, Rutgers University}, year = 1988, number = {LCSR-TR-117} } @techreport{GH-88, author = {D. Goldfarb and J. Hao}, title = {{A Primal Simplex Algorithm that Solves the Maximum Flow Problem in at Most $nm$ Pivots and {$O(n^2m)$} Time}}, institution = {Department of IE and OR, Columbia University}, year = 1988 } @article{GHKS-78, author = {F. Glover and J. Hultz and D. Klingman and J. Stutz}, title = {Generalized Networks: A fundamental Computer-Based Planning Tool}, journal = {Management Science}, year = 1978, month = {August}, volume = 24, number = 12 } @article{GHS-83, author = {R. G. Gallager and P. A. Humblet and P. M Spira}, title = {{A Distributed Algorithm for Minimum-Weight Spanning Trees}}, journal = toplas, pages = {66--77}, year = 1983, volume = 5 } @article{GK-73, author = {F. Glover and D. Klingman}, title = {{On the Equivalence of Some Generalized Network Problems \ to Pure Network Problems}}, journal = {Math. Programming}, pages = {269--278}, year = 1973, volume = 4 } @article{GK-82, author = {H. N. Gabow and O. Kariv}, title = {{Algorithms for Edge-Coloring Bipartite Graphs and Multigraphs}}, journal = {SIAM J. Comput.}, pages = {117--129}, year = 1982, volume = 11 } @inproceedings{GK-87, author = {D. Y. Grigoriev and M. Karpinski}, title = {{The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC}}, booktitle = focs28, pages = {166--172}, year = 1987 } @techreport{GK-91, author = {M. D. Grigoriadis and L. G. Khachiyan}, title = {{Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints}}, institution = {Department of Computer Science, Rutgers University}, year = 1991, number = {DCS-TR-273} } @article{GK-96, author = {Jon Kleinberg and Michel X. Goemans}, title = {{The Lov\'asz Theta Function and a Semidefinite Programming Relaxation of Vertex Cover}}, journal = siamdisc, year = 1996, note = {{(To appear).}} } @unpublished{GL-86, author = {A. V. Goldberg and C. E. Leiserson}, title = {Implementing Parallel Graph Algorithms}, year = 1986, note = {(in preparation)} } @article{GL-91, author = {D. Goldfarb and S.~Liu}, title = {{An $O(n^{3}L)$ Primal Interior point Algorithm for Convex Quadratic Programming}}, journal = mathprog, year = 1991, volume = 53 } @article{GLS-81, author = {M. Gr{\"{o}}tschel and L. Lov\'{a}sz and A. Schrijver}, title = {The Ellipsoid Method and its Consequences in Combinatorial Optimization}, journal = {Combinatorica}, year = 1981, volume = 1, number = 2 } @article{GLS-84a, author = {M. Gr{\"{o}}tschel and L. Lov\'{a}sz and A. Schrijver}, title = {Relaxations of Vertex Packing}, journal = {{Journal of Combinatorial Theory, Series B}}, year = 1986, volume = 40 } @incollection{GLS-84b, author = {M. Gr{\"{o}}tschel and L. Lov\'{a}sz and A. Schrijver}, editor = {C. Berge and V. Chvatal}, title = {Polynomial Algorithms for Perfect Graphs}, booktitle = {Perfect Graphs}, year = 1984, publisher = {North Holland}, address = {Amsterdam}, note = {{also Ann. Discrete Math., 21}} } @book{GLS-88, author = {M. Gr{\"{o}}tschel and L. Lov\'{a}sz and A. Schrijver}, title = {{Geometric Algorithms and Combinatorial Optimization}}, year = 1988, publisher = {Springer Verlag} } @article{GLW-91, author = {D. Goldfarb and S.~Liu and S.~Wang}, title = {{A Logarithmic Barrier Function Algorithm for Convex Quadratically Constrained Convex Quadratic Programming}}, journal = siamopt, pages = {252--267}, year = 1991, volume = 1, number = 2 } @book{GM-84, author = {M. Gondran and M. Minoux}, title = {Graphs and Algorithms}, year = 1984, publisher = {Wiley} } @inproceedings{GMPR-77, author = {L.J. Guibas and E.M. Plass and J.R. Roberts}, title = {A New Representation for Linear Lists}, booktitle = stoc9, pages = {49--60}, year = 1977 } @book{GMW-81, author = {P.~Gill and W.~ Murray and M.~Wright}, title = {Practical Optimization}, year = 1981, publisher = {Academic Press} } @article{GN-80, author = {Z. Galil and A. Naamad}, title = {{An ${O(E V \log^2 V)}$ Algorithm for the Maximal Flow Problem}}, journal = {J. Comput. System Sci.}, pages = {203--217}, year = 1980, volume = 21 } @article{GP-86-2, author = {A. V. Goldberg and S. A. Plotkin}, title = {{Parallel {$(\Delta + 1)$} Coloring of Constant-Degree Graphs}}, journal = IPL, pages = {241--245}, year = 1987, volume = 25 } @techreport{GP-87-1, author = {A. V. Goldberg and S. A. Plotkin}, title = {{Efficient Parallel Algorithms for {$(\Delta\!+\!1)$}-Coloring and Maximal Independent Set Problems}}, institution = {MIT}, year = 1987, number = {MIT/LCS/TM-320} } @inproceedings{GPS-87, author = {A. V. Goldberg and S. A. Plotkin and G. E. Shannon}, title = {{Parallel Symmetry-Breaking in Sparse Graphs}}, booktitle = stoc19, pages = {315--324}, year = 1987 } @article{GPS-88, author = {A. V. Goldberg and S. A. Plotkin and G. E. Shannon}, title = {{Parallel Symmetry-Breaking in Sparse Graphs}}, journal = {SIAM J. Disc. Math.}, pages = {434--446}, year = 1988, volume = 1 } @techreport{GPST-89a, author = {A. V. Goldberg and S. A. Plotkin and D. Shmoys and \'E. Tardos}, title = {{Interior-Point Methods in Parallel Computation}}, institution = {Stanford University}, year = 1989, number = {STAN-CS-89-1259} } @inproceedings{GPST-89b, author = {A. V. Goldberg and S. A. Plotkin and D. Shmoys and \'E. Tardos}, title = {{Interior-Point Methods in Parallel Computation}}, booktitle = focs30, pages = {350--356}, year = 1989 } @article{GPST-91, author = {A. V. Goldberg and S. A. Plotkin and D. Shmoys and \'E. Tardos}, title = {{Interior-Point Methods in Parallel Computation}}, journal = SJC, pages = {140--150}, year = 1991, volume = 21, number = 1 } @techreport{GPT-88, author = {A. V. Goldberg and S. A. Plotkin and \'E. Tardos}, title = {{Combinatorial Algorithms for the Generalized Circulation Problem}}, institution = {Stanford University}, year = 1988, number = {STAN-CS-88-1209}, note = {(Also available as Technical Memorandum MIT/LCS/TM-358, Laboratory for Computer Science, M.I.T., 1988.)} } @article{GPT-91, author = {A. V. Goldberg and S. A. Plotkin and \'E. Tardos}, title = {{Combinatorial Algorithms for the Generalized Circulation Problem}}, journal = mor, pages = {351--381}, year = 1991 } @techreport{GPV-88, author = {A. V. Goldberg and S. A. Plotkin and P. M. Vaidya}, title = {{Sublinear-Time Parallel Algorithms for Matching and Related Problems}}, institution = {Stanford University}, year = 1988, number = {STAN-CS-88-1211} } @inproceedings{GPV-88-2, author = {A. V. Goldberg and S. A. Plotkin and P. M. Vaidya}, title = {{Sublinear-Time Parallel Algorithms for Matching and Related Problems}}, booktitle = focs29, pages = {174--185}, year = 1988 } @inproceedings{GS-85, author = {A. V. Goldberg and M. Sipser}, title = {{Compression and Ranking}}, booktitle = stoc17, pages = {440--448}, year = 1985 } @inproceedings{GS-87, author = {M. Goldberg and T. Spencer}, title = {{A New Parallel Algorithm for the Maximal Independent Set Problem}}, booktitle = focs28, pages = {161--165}, year = 1987 } @inproceedings{GS-88, author = {S.~S.~Hochbaum and O.~Goldschmidt}, title = {Polynomial Algorithms for the k-Cut problem}, booktitle = focs29, pages = {444--450}, year = 1988 } @article{GS-?, author = {A. V. Goldberg and M. Sipser}, title = {{Compression and Ranking}}, journal = siamcomp, year = {(accepted for publication)} } @article{GSS-82, author = {L. M. Goldschlager and R. A. Shaw and J. Staples}, title = {{The Maximum Flow Problem is Log Space Complete for P}}, journal = {Theoretical Computer Sci.}, pages = {105--111}, year = 1982, volume = 21 } @inproceedings{GT-86, author = {A. V. Goldberg and R. E. Tarjan}, title = {{A New Approach to the Maximum Flow Problem}}, booktitle = stoc18, pages = {136--146}, year = 1986 } @inproceedings{GT-87, author = {A. V. Goldberg and R. E. Tarjan}, title = {{Solving Minimum-Cost Flow Problems by Successive Approximation}}, booktitle = stoc19, pages = {7--18}, year = 1987, note = {(Math. of Oper. Res., to appear)} } @techreport{GT-87-2, author = {A. V. Goldberg and R. E. Tarjan}, title = {{Finding Minimum-Cost Circulations by Successive Approximation}}, institution = {Laboratory for Computer Science, M.I.T.}, year = 1987, number = {MIT/LCS/TM-333}, note = {(Math. of Oper. Res., to appear)} } @techreport{GT-87-3, author = {A. V. Goldberg and R. E. Tarjan}, title = {{Finding Minimum-Cost Circulations by Canceling Negative Cycles}}, institution = {Laboratory for Computer Science, M.I.T.}, year = 1987, number = {MIT/LCS/TM-334}, note = {(Also available as Technical Report CS-TR 107-87, Department of Computer Science, Princeton University)} } @inproceedings{GT-88, author = {A. V. Goldberg and R. E. Tarjan}, title = {{Finding Minimum-Cost Circulations by Canceling Negative Cycles}}, booktitle = stoc20, pages = {388--397}, year = 1988 } @article{GT-88-2, author = {A. V. Goldberg and R. E. Tarjan}, title = {{A New Approach to the Maximum Flow Problem}}, journal = jacm, pages = {921--940}, year = 1988, volume = 35, note = {A preliminary version appeared in {\it Proc. 18th ACM Symp. on Theory of Comp.}, 136--146, 1986.} } @techreport{GT-88-3, author = {A. V. Goldberg and R. E. Tarjan}, title = {{A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network}}, institution = {Department of Computer Science, Stanford University}, year = 1988, number = {STAN-CS-88-1228} } @article{GT-89, author = {A. V. Goldberg and R. E. Tarjan}, title = {{A Parallel Algorithm for Finding a Blocking Flow in an Acyclic Network}}, journal = IPL, pages = {265--272}, year = 1989, volume = 31 } @article{GT-89-2, author = {A. V. Goldberg and R. E. Tarjan}, title = {{Finding Minimum-Cost Circulations by Canceling Negative Cycles}}, journal = jacm, year = 1989, volume = 36, note = {A preliminary version appeared in {\it Proc. 20th ACM Symp. on Theory of Comp.}, 388--397, 1988.} } @incollection{GT-89-3, author = {D. Goldfarb and M. J. Todd}, editor = {G. L. Nemhauser and A. H. G. Rinnooy Kan and M. J. Todd}, title = {{Linear Programming}}, booktitle = {Optimization}, year = 1989, publisher = {North-Holland}, address = {Amsterdam}, series = {Handbooks in Operations Research and Management Sciences} } @article{GT-90, author = {A. V. Goldberg and R. E. Tarjan}, title = {{Finding Minimum-Cost Circulations by Successive Approximation}}, journal = mor, pages = {430--466}, year = 1990, volume = 15, note = {A preliminary version appeared in {\it Proc. 19th ACM Symp. on Theory of Comp.}, 7--18, 1987.} } @techreport{GTT-89, author = {A. V. Goldberg and \'E. Tardos and R. E. Tarjan}, title = {{Network Flow Algorithms}}, institution = {Department of Computer Science, Stanford University}, year = 1989, number = {STAN-CS-89-1252} } @incollection{GTT-90, author = {A. V. Goldberg and \'E. Tardos and R. E. Tarjan}, editor = {B. Korte and L. Lov{\'a}sz and H. J. Pr{\"o}mel and A. Schrijver}, title = {{Network Flow Algorithms}}, booktitle = {Flows, Paths, and VLSI Layout}, pages = {101--164}, year = 1990, publisher = {Springer Verlag} } @book{GV-89, author = {G. H. Golub and C. F. Van Loan}, title = {{Matrix Computations, 2nd ed.}}, year = 1989, publisher = {{Johns Hopkins University Press, Baltimore, MD}} } @article{GW-94, author = {Michel X. Goemans and David P. Williamson}, title = {{Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming}}, journal = jacm, year = 1994, note = {{(To appear). A preliminary version appeared in Proc. 26th Annual ACM Symposium on Theory of Computing}} } @article{GaT-87-1, author = {H. N. Gabow and R. E. Tarjan}, title = {{Faster Scaling Algorithms for Network Problems}}, journal = {SIAM J. Comput.}, year = {to appear.} } @techreport{GaT-87-2, author = {H. N. Gabow and R. E. Tarjan}, title = {A Faster Scaling Algorithm for General Weighted Matching}, institution = {Department of Computer Science, Princeton University}, year = 1987, number = {CS-TR 111-87} } @unpublished{GaT-87-3, author = {H. N. Gabow and R. E. Tarjan}, title = {Almost-Optimal Speed-ups of Algorithms for Matching and Related Problems}, year = 1987, note = {Unpublished manuscript} } @inproceedings{GaT-88, author = {H. N. Gabow and R. E. Tarjan}, title = {{Almost-Optimal Speed-ups of Algorithms for Matching and Related Problems}}, booktitle = stoc20, pages = {514--527}, year = 1988 } @techreport{GaTa-86, author = {Z. Galil and \'E. Tardos}, title = {{An ${O}(n^2 \log n (m + n \log n))$ Minimum Cost Flow Algorithm}}, institution = {Mathematical Science Research Institute, Berkeley, CA}, year = 1986, number = {04518--86} } @inproceedings{GaTa-86-2, author = {Z. Galil and \'E. Tardos}, title = {{An ${O}(n^2 \log n (m + n \log n))$ Min-Cost Flow Algorithm}}, booktitle = focs27, pages = {1--9}, year = 1986 } @article{GaTa-88, author = {Z. Galil and \'E. Tardos}, title = {{An ${O}(n^2 (m + n \log n)\log n)$ Minimum Cost Flow Algorithm}}, journal = jacm, pages = {374--386}, year = 1988, volume = 35 } @article{HCS-79, author = {D.S. Hirschberg and A.K. Chandra and D.V. Sarwate}, title = {Computing Connected Components on Parallel Computers}, journal = cacm, pages = {461--464}, year = 1979, month = {August}, volume = 22, number = 8 } @book{HJ-85, author = {R.~Horn and C.~Johnson}, title = {Matrix Analysis}, year = 1985, publisher = {Cambridge University Press}, address = {Cambridge} } @book{HJ-90, author = {R.~Horn and C.~Johnson}, title = {Topics in Matrix Analysis}, year = 1990, publisher = {Cambridge University Press}, address = {Cambridge} } @techreport{HJRT-92, author = {D. den Hertog and F. Jarre and C Roos and T. Terlaky}, title = {A Unifying Investigation of Interior Point Methods for Convex Programming}, institution = {{Techische Universiteit Delft, Faculty of Technical Mathematics and Informatics}}, year = 1992, number = {{92--89}} } @article{HK-73, author = {J. E. Hopcroft and R. M. Karp}, title = {{An $n^{5/2}$ Algorithm for Maximum Matching in Bipartite Graphs}}, journal = SJC, pages = {225--231}, year = 1973, volume = 2 } @book{HLP-52, author = {G.~Hardy and J.~E.~Littlewood and G.~P{\'o}lya}, title = {{Inequalities, 2nd ed.}}, year = 1952, publisher = {{Cambridge University Press}} } @article{HRVW-96, author = {C. Helmberg and F. Rendl and R. J. Vanderbei and H. Wolkowicz}, title = {An Interior-Point Method for Semidefinite Programming}, journal = siamopt, year = 1996, volume = 6, pages = {342--361} } @article{HS-86, author = {W. D. Hillis and Steele, Jr., G. L.}, title = {Data Parallel Algorithms}, journal = {Comm. of the ACM}, pages = {1170--1183}, year = 1986, volume = 29 } @article{HaJ-85, author = {R. Hassin and D. B. Johnson}, title = {{An $O(n\log^2n)$ Algorithm for Maximum Flow in Undirected Planar Network}}, journal = SJC, pages = {612--624}, year = 1985, volume = 14 } @incollection{Hu-58, author = {L. Hurwicz}, editor = {K. J. Arrow and L. Hurwicz and H. Uzawa}, title = {{Programming in Linear Spaces}}, booktitle = {{Studies in Linear and Non-linear Programming, II}}, pages = {4--102}, year = 1958, publisher = {{Stanford University Press, Stanford, CA}} } @article{IR-85, author = {A. Itai and M. Rodeh}, title = {Sceduling Transmissions in a Network}, journal = {J. Algorithms}, pages = {409--429}, year = 1985, volume = 6 } @article{IS-79, author = {A. Itai and Y. Shiloach}, title = {{Maximum Flow in Planar Network}}, journal = SJC, pages = {135--150}, year = 1979, volume = 8 } @article{IS-86, author = {A. Israeli and Y. Shiloach}, title = {{An Improved Parallel Algorithm for Maximal Matching}}, journal = IPL, pages = {57--60}, year = 1986, volume = 22 } @book{JB-80, author = {P. A. Jensen and J. W. Barnes}, title = {Network Flow Programming}, year = 1980, publisher = {J. Wiley \& Sons} } @article{JJ-72, author = {J.J. Jarvis and A.M. Jezior}, title = {Maximal Flow with Gains through a Special Network}, journal = or, pages = {678--688}, year = 1972, volume = 20 } @inproceedings{JV-82, author = {D. B. Johnson and S. Venkatesan}, title = {{Using Divide and Conquer to Find Flows in Directed Planar Netwroks in $O(n^{1.5}\log n)$ Time}}, booktitle = {Proc. 20th Annual Allerton Conf. on Communication, Control, and Computing}, pages = {898--905}, year = 1982 } @book{Ja-92, author = {{Joseph~J\'a~J\'a}}, title = {{An Introduction to Parallel Algorithms}}, year = 1992, publisher = {{Addison Wesley, Reading, Ma}} } @article{Juh-82, author = {Ferenc Juh\'{a}sz}, title = {The Asymptotic Behavior of Lov\'{a}sz's {$\vartheta$} Function for Random Graphs}, journal = {Combinatorica}, pages = {153--155}, year = 1982, volume = 2, number = 2 } @article{KGV-83, author = {S. Kirkpatrick and C. D. Gelatt, Jr. and M. P. Vecchi}, title = {Optimization by Simulated Annealing}, journal = {Science}, pages = {671--680}, year = 1983, volume = 220 } @inproceedings{KGY-89, author = {M. Kharitonov and A. V. Goldberg and M. Yong}, title = {{Lower Bounds for Pseudorandom Number Generators}}, booktitle = focs30, pages = {242--247}, year = 1989 } @techreport{KKH-94, author = {Masakazu Kojima and Sadayoshi Kojima and and Shinji Hara}, title = {{Linear Algebra for Semidefinite Programming}}, institution = {{Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, Japan}}, year = 1994, series = {{Research Reports on Information Sciences, Series B: Operations Research}} } @article{KL-70, author = {B.~W.~Kernighan and S.~Lin}, title = {An efficient heuristic procedure for partitioning graphs}, journal = {The Bell System Technical Journal}, year = 1970, volume = 49 } @book{KMNY-91, author = {M.~Kojima and N.~Megiddo and T. Noma and A. Yoshise}, title = {A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems}, year = 1991, publisher = {Springer-Verlag}, address = {New York}, number = 538, series = {Lecture Notes in Computer Science} } @inproceedings{KMS-94, author = {David Karger and Rajeev Motwani and Madhu Sudan}, title = {{Improved Graph Coloring by Semidefinite Programming}}, booktitle = focs34, year = 1994 } @inproceedings{KMY-89, author = {M.~Kojima and S.~Mizuni and A.~Yoshise}, editor = {N. Megiddo}, title = {A Primal-Dual Interior-Point Algorithm for Linear Programming}, booktitle = {Progress in Mathematical Programming}, year = 1989, publisher = {Springer Verlag}, address = {Berlin} } @article{KMY-91, author = {M.~Kojima and S.~Mizuni and A.~Yoshise}, title = {An {$O(\sqrt n L)$} iteration potential reduction algorithm for linear complementarity problem}, journal = mathprog, pages = {331--342}, year = 1991, volume = 50, number = 3 } @article{KO-81, author = {R. M. Karp and J. B. Orlin}, title = {{Parametric Shortest Path Algorithms with an Application to Cyclic Staffing}}, journal = {Discrete Applied Math.}, pages = {37--45}, year = 1981, volume = 3 } @techreport{KPST-91, author = {P. Klein and S. A. Plotkin and C. Stein and \'E. Tardos}, title = {{Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routings and Finding Sparse Cuts}}, institution = {School of ORIE, Cornell University}, year = 1991, number = {961} } @techreport{KR-88, author = {R. M. Karp and V. Ramachandran}, title = {{A Survey of Parallel Algorithms for Shared Memory Machines}}, institution = {Computer Science Division (EECS), University of California, Berkeley, CA}, year = 1988, number = {UCB/CSD 88/408} } @inproceedings{KRS-85, author = {C. P. Kruskal and L. Rudolph and M. Snir}, title = {The Power of Parallel Prefix}, booktitle = {Proc. Int. Conf. on Parallel Processing}, pages = {180--185}, year = 1985 } @inproceedings{KRS-86, author = {C. Kruskal and L. Rudolf and M. Snir}, title = {Efficient Parallel Algorithms for Graph Problems}, booktitle = {Proc. International Conf. on Parallel Processing}, pages = {869--876}, year = 1986 } @article{KSH-94, author = {M. Kojima and S. Shindoh and S. Hara}, title = {{Interior-Point Methods for the Monotone Linear Complementarity Problem in Symmetric Matrices}}, journal = siamopt, volume = 7, number = 9, year = 1997, pages ={86--125}, optnote ={same as KSH-97} } @article{KSH-97, author = {M. Kojima and S. Shindoh and S. Hara}, title = {{Interior-Point Methods for the Monotone Linear Complementarity Problem in Symmetric Matrices}}, journal = siamopt, volume = 7, number = 9, year = 1997, pages ={86--125}, optnote ={same as KSH-97} } @techreport{KSS-96, author = {M.~Kojima and M.~Sidha and S.~Shindoh and S. Hara}, title = {{Local convergence of predictor-corrector infeasible interior-point algorithms for SDPs and SDLCPs}}, year = 1996, institution={{Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology}}, number = {{2-12-1}}, } @inproceedings{KST-90, author = {P. Klein and C. Stein and \'E. Tardos}, title = {{Leighton-Rao Might be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities}}, booktitle = stoc22, pages = {310--321}, year = 1990 } @article{KUW-86, author = {R. M. Karp and E. Upfal and A. Wigderson}, title = {{Constructing a Maximum Matching is in Random {NC}}}, journal = {Combinatorica}, pages = {35--48}, year = 1986, volume = 6 } @inproceedings{KV-86, author = {S. Kapoor and P. M. Vaidya}, title = {{Fast Algorithms for Convex Quadratic Programming and Multicommodity Flows}}, booktitle = stoc18, pages = {147--159}, year = 1986 } @inproceedings{KW-84, author = {R. M. Karp and A. Wigderson}, title = {{A Fast Parallel Algorithm for the Maximal Independent Set Problem}}, booktitle = stoc16, pages = {266--272}, year = 1984 } @article{LF-80, author = {R. E. Ladner and M. J. Fischer}, title = {{Parallel Prefix Computation}}, journal = jacm, pages = {831--838}, year = 1980, volume = 27 } @inproceedings{LM-86, author = {C. E. Leiserson and B. M. Maggs}, title = {{Communication-Efficient Parallel Graph Algorithms}}, booktitle = {Proc. of International Conference on Parallel Processing}, pages = {861--868}, year = 1986 } @inproceedings{LMPSTT-91, author = {T. Leighton and F. Makedon and S. Plotkin and C. Stein and \'E. Tardos and S. Tragoudas}, title = {Fast Approximation Algorithms for Multicommodity Flow Problems}, booktitle = stoc23, year = 1991 } @article{LMS-94, author = {J. Lustig and R. E. Marstern and D. F. Shanno}, title = {{Interior Point Methods for Linear Programming: Computational State of Art}}, journal = {ORSA Journal on Computing}, pages = {1--14}, year = {1994}, volume = 6, number = 1 } @article{LPV-81, author = {G. F. Lev and N. Pippenger and L. G. Valiant}, title = {{A Fast Parallel Algorithm for Routing in Permutation Networks}}, journal = {IEEE Trans. on Comput.}, pages = {93--100}, year = 1981, volume = {C-30} } @inproceedings{LRS-83, author = {C. Leiserson and F. Rose and J. Saxe}, title = {Optimizing Synchronous Circuitry by Retiming}, booktitle = {Third Caltech Conference on VLSI}, pages = {87--116}, year = 1983, address = {Rockville, Maryland} } @article{LS-83, author = {C. Leiserson and J. Saxe}, title = {Optimizing Synchronous Systems}, journal = {Journal of VLSI and Computer Systems}, pages = {41--67}, year = 1983, month = jan, volume = 1 } @techreport{LVBL-97, author = {M.~S.~Lobo and L.~Vandenberghe and S.~Boyd and H.~Lebret}, title = {Second Order Cone Programming}, institution = {Information Systems Laboratory, Electrical Engineering Department, Stanford University}, note = {submitted}, year = 1997 } @article{LS-91, author = {L.~Lov\'{a}sz and A.~Schrijver}, title = {{Cones of Matrices and Setfunctions, and 0-1 Optimization}}, journal = siamopt, pages = {166--190}, year = 1991, volume = 1, number = 2 } @article{LS-93, author = {L.~Lov\'{a}sz and M. Simonovits}, title = {Random Walks in a Convex Body and Improved Volume Algorithm}, journal = {Random Structures and Algorithms}, pages = {359--412}, year = 1993, volume = 4, number = 4 } @book{LT-85, author = {P. Lancaster and M. Tismenetsky}, title = {The Theory of Matrices}, year = 1985, publisher = {Academic Press}, address = {New York} } @techreport{MA-88, author = {R.~Monteiro and I.~Adler}, title = {Polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension}, institution = {Industrial Engineering and Operations Research Department, University of California--Berkeley}, year = 1988, month = Mar, number = {ESRC 88-8} } @article{MA-89a, author = {R. C. Monteiro and I. Adler}, title = {{Interior path following primal-dual algorithms. Part {\rm I}: Linear programming}}, journal = mathprog, pages = {27--41}, year = 1989, volume = 44 } @article{MA-89b, author = {R. C. Monteiro and I. Adler}, title = {{Interior path following primal-dual algorithms. Part {\rm II}: Convex quadratic programming}}, journal = mathprog, pages = {43--66}, year = 1989, volume = 44 } @unpublished{mon-96, author = {R.~Monteiro}, title = {{Polynomial Convergence of Primal-Dual Algorithms for Semidefinite Programming Based on Monteiro and Zhang Family of Directions}}, year = 1996, Note = {submitted} } @article{mon-97, author = {R. C. Monteiro}, title = {{Primal-dual path-following algorithms for semidefinite programming}}, journal = siamopt, pages = {663--678}, year = 1997, volume = 7 } @techreport{MT-96, author = {R.~Monteiro and T.~Tsuchiya}, title = {{Polynomial Convergence of a New Family of Primal-Dual Algorithms for Semidefinite Programming}}, institution = {The Institute of Statistical Mathematics}, address ={{4-6-7 Minami-Azabu, Minato-ku, Tokyo 106, Japan}}, year = 1996, month = {November}, number = {627} } @unpublished{MZ-96, author = {R.~D.~C.~Monteiro and Y.~Zhang}, title = {A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming}, year = 1996, institution={{School of ISyE, Georgia Institute of Technology}}, address = {{Atlanta, GA 30332, USA}}, note = {submitted} } @unpublished{ME-90, author = {S. T. McCormick and T. R. Ervolina}, title = {{Computing Maximum Mean Cuts}}, year = 1990, note = {UBC Faculty of Commerce Working Paper 90-MSC-011} } @article{MKM-78, author = {V. M. Malhotra and M. Pramodh Kumar and S. N. Maheshwari}, title = {{An $O(|V|^3)$ Algorithm for Finding Maximum Flows in Networks}}, journal = IPL, pages = {277--278}, year = 1978, volume = 7 } @inproceedings{MN-89, author = {G. L. Miller and J. Naor}, title = {{Flow in Planar Graphs with Multiple Sources and Sinks}}, booktitle = focs30, year = 1989 } @unpublished{MN-93, author = {K. Mints and A. Nemirovskii}, title = {{Extension of Karmarkar's Algorithm onto Convex Quadratically Constrained Quadratic Problems}}, year = 1993, note = {{to appear}}, journal = mathprog } @book{MP-71, author = {R. McNaughton and S. Papert}, title = {Counter-Free Finite Automata}, year = 1971, publisher = {MIT Press, Cambridge, Mass.} } @techreport{MS-87, author = {S.~Mehrotra and J.~Sun}, title = {An Algorithm for Convex Quadratic Programming that Requires {$O(n^{3.5}L)$} Arithmetic Operations}, institution = {{Department of IE/MS, Nothwesten University}}, year = 1987, number = {87--24} } @article{MS-91, author = {S.~Mehrotra and J.~Sun}, title = {{A method of analytic centers for quadratically constrianed convex quadratic programming}}, journal = {SIAM Journal on Numerical Analysis}, volume = 28, pages = {529--544}, year =1991 } @article{meh-92, author = {S.~Mehrotra}, title = {On the implementation of a primal-dual interior point method}, journal = siamopt, volume = 2, pages = {575--601}, year = 1992 } @inproceedings{MV-80, author = {S. Micali and V. V. Vazirani}, title = {An ${O (\sqrt{|V|}|E|)}$ Algorithm for Finding Maximum Matching in General Graphs}, booktitle = focs21, pages = {17--27}, year = 1980 } @article{MVV-87, author = {K. Mulmuley and U. V. Vazirani and V. V. Vazirani}, title = {Matching is as Easy as Matrix Inversion}, journal = {Combinatorica}, pages = {105--131}, year = 1987 } @inproceedings{NM-90, author = {G.~Narasimhan and R.~Manber}, editor = {{W. Cook, and P. D. Seymour}}, title = {{A Generalization of Lov\'asz's $\vartheta$ Function}}, booktitle = {Polyhedral Combinatorics}, pages = {{19--27}}, year = 1990, publisher = {Amer. Math. Soc. and Ass. for Computing Machinery}, volume = 1, series = {{DIMACS series in Discrete Mathematics and Theoretical Computer Science}} } @booklet{NN-90, author = {Y.~Nesterov and A.~Nemirovskii}, title = {Self-Concordant Functions and Polynomial Time Methods in Convex Programming}, year = 1990, address = {{Central Economical and Mathematical Institute, U.S.S.R Academy of Science, Moscow}} } @techreport{NN-90A, author = {Y.~Nesterov and A.~Nemirovskii}, title = {{Optimization over positive semidefinite matrices: Mathematical background and user's manual}}, institution = {{Centr. Econ. \& Math. Inst., USSR Academy of Sciences}}, year = 1990, address = {Moscow} } @techreport{NN-91a, author = {Y.~Nesterov and A.~Nemirovskii}, title = {Path-Following Polynomial Time Algorithm For Monotone Variational Inequalities}, institution = {{USSR Academy of Sciences, Central Economic {\&} Mathematical Institute, Mathematical Programming Department}}, year = 1991, month = Mar, number = {4224--2}, type = {Research Report} } @unpublished{NN-91b, author = {Y.~Nesterov and A.~Nemirovskii}, title = {{An Interior Point Method for Generalized Linear-Fractional Programming}}, year = 1991, note = {(to appear in {\em Math. Programming ser. B})} } @unpublished{NN-92, author = {Y.~Nesterov and A.~Nemirovskii}, title = {Acceleration of the path-following method for optimization over the cone of positive semidefinite matrices}, year = 1992, note = {Unpublished manuscript} } @book{NN-94, author = {Y.~Nesterov and A.~Nemirovskii}, title = {{Interior Point Polynomial Methods in Convex Programming: Theory and Applications}}, year = 1994, publisher = {{Society for Industrial and Applied Mathematics}}, address = {Philadelphia} } @inproceedings{NPT-90, author = {C. Haibt Norton and S. A. Plotkin and \'E. Tardos}, title = {{Using Separation Algorithms in Fixed Dimension}}, booktitle = soda1, year = 1990 } @article{NS-96, author = {A. Nemirovskii and K. Scheinberg}, title = {{Extension of Karmarkar's Algorithm onto convex quadratically constrained quadratic programming}}, journal = mathprog, pages = {273--289}, year = 1996, volume = 72 } @article{NT-94, author = {Y. E. Nesterov and M. J. Todd}, title = {{Self-Scaled Cones and Interior-Point Methods in Nonlinear Programming}}, journal = mor, year = 1994, month = {April}, note = {{submitted}} } @unpublished{NT-95, author = {Y. E. Nesterov and M. J. Todd}, title = {{Primal-Dual Interior-Point Methods for Self-Scaled Cones}}, year = 1995, note = {{submitted}} } @unpublished{OA-87, author = {J. B. Orlin and R. K. Ahuja}, title = {{New Distance-Directed Algorithms for Maximum-Flow and Parametric Maximum-Flow Problems}}, year = 1987, note = {Sloan Working Paper 1908-87, Sloan School of Management, M.I.T.} } @unpublished{OA-88, author = {J. B. Orlin and R. K. Ahuja}, title = {{New Scaling Algorithms for Assignment and Minimum Cycle Mean Problems}}, year = 1988, note = {Sloan Working Paper 2019-88, Sloan School of Management, M.I.T.} } @article{OW-91a, author = {M.~L. Overton and R.~S. Womersley}, title = {Optimality Conditions and Duality Theory for Minimizing sums of the Largest Eigenvalues of Symmetric Matrices}, journal = mathprog, pages = {321--357}, year = 1993, volume = 62, number = 2 } @article{OW-91b, author = {M.~L. Overton and R.~S. Womersley}, title = {On the Sum of the Largest Eigenvalues of a Symmetric Matrix}, journal = siamx, pages = {41--45}, year = 1992, volume = 13 } @techreport{PE-84, author = {P. S. Pulat and S. E. Elmaghraby}, title = {{On Maximizing Flow in Generalized Flow Networks}}, institution = {NC State University}, year = 1984, number = {202} } @article{PR-75, author = {J. C. Picard and H. D. Ratliff}, title = {Minimum Cuts and Related Problems}, journal = {Networks}, pages = {357--370}, year = 1975, volume = 5 } @inproceedings{PR-85, author = {V. Pan and J. Reif}, title = {{Efficient Parallel Solution of Linear Systems}}, booktitle = stoc17, pages = {143--152}, year = 1985 } @techreport{PR-91, author = {S. Poljak and F. Rendl}, title = {Solving the Max-cut problem using eigenvalues}, institution = {{Forschungsinstitut F\"ur Diskrete Mathematik, Institut F\"ur \"okonometrie und Operations Research, Rheinische Friedrich-Wilhelms-Universit\"at, Bonn}}, year = 1991, month = {November}, number = {91735-OR} } @techreport{PR-92, author = {S. Poljak and F. Rendl}, title = {Nonpolyhedral Relaxations of Graph-Bisection Problems}, institution = {{DIMACS}}, year = 1992, month = {November}, number = {92--55} } @book{PS-96, author = {C. H. Papadimitriou and K. Steiglitz}, title = {Combinatorial Optimization: Algorithms and Complexity}, year = 1982, publisher = {Prentice-Hall, Englewood Cliffs, NJ} } @inproceedings{PST-91, author = {S. A. Plotkin and D. Shmoys and \'E. Tardos}, title = {{Fast Approximation Algorithms for Fractional Packing and Covering}}, booktitle = focs32, year = 1991, note = {To appear} } @inproceedings{PVW-83, author = {W. Paul and U. Vishkin and H. Wagener}, title = {{Parallel Dictionary}}, booktitle = {Proc. 10th International Colloquium on Automata, Languages and Programming}, pages = {597--609}, year = 1983, publisher = {Springer-Verlag} } @techreport{RG-90, author = {T. Radzik and A. V. Goldberg}, title = {{Tight Bounds on the Number of Minimum-Mean Cycle Cancellations}}, institution = {Department of Computer Science, Stanford University}, year = 1990, number = {STAN-CS-90-1328} } @techreport{RW-93, author = {F. Rendl and H. Wolkowicz}, title = {A Projection Technique for Partitioning the Nodes of a Graph}, institution = {{Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada}}, year = 1993, number = {{90-20}}, type = {{CORR Report}} } @inproceedings{SB-90, author = {D.~Shanno and R.~Baghchi}, editor = {J. B. Rosen}, title = {A Unified View of Interior Point Methods for Linear Programming}, booktitle = {Proceedings of a Workshop on Supercomputers and Large-Scale Optimization}, year = 1990, publisher = {{J.C. Baltzer AG, Basel, Switzerland}}, volume = 22, series = {Annals of Operations Research} } @inproceedings{SM-86, author = {B. Schieber and S. Moran}, title = {{Slowing Down Sequential Algorithms for Obtaining Fast Distributed and Parallel Algorithms: Maximum Matchings}}, booktitle = podc5, year = 1986 } @article{SM-90, author = {F. Shahrokhi and D. Matula}, title = {The Maximum Concurrent Flow Problem}, journal = jacm, pages = {318--334}, year = 1990, volume = 37 } @article{ST-83, author = {D. D. Sleator and R. E. Tarjan}, title = {{A Data Structure for Dynamic Trees}}, journal = {J. Comput. System Sci.}, pages = {362--391}, year = 1983, volume = 26 } @article{ST-85, author = {{D. D. Sleator and R. E. Tarjan}}, title = {Self-adjusting Binary Search Trees}, journal = jacm, pages = {652--686}, year = 1985, volume = 32 } @article{SV-82, author = {Y. Shiloach and U. Vishkin}, title = {{An ${O}(\log n)$ Parallel Connectivity Algorithm}}, journal = {J. Algorithms}, pages = {57--67}, year = 1982, volume = 3 } @article{SV-82-2, author = {Y. Shiloach and U. Vishkin}, title = {{An ${O}(n^2 \log n)$ Parallel Max-Flow Algorithm}}, journal = {J. Algorithms}, pages = {128--146}, year = 1982, volume = 3 } @book{shi-88, author = {T.~Shimpuku}, title = {{Symmetric Algberas by Direct Product of Clifford Algebra}}, year = 1988, publisher = {Seibunsha Publishers}, address = {{Osaka, Japan}} } @book{TM-90, author = {Thinking Machine Corporation}, title = {{Connection Machine Model CM2 Technical Summary}}, year = 1990, publisher = {TMC} } @article{TV-85, author = {R.E. Tarjan and U. Vishkin}, title = {{An Efficient Parallel Biconnectivity Algorithm}}, journal = SJC, pages = {862--874}, year = 1985, volume = 14 } @article{TV-88, author = {R.E. Tarjan and C.J. Van Wyk}, title = {An ${O ( n log\log n )}$-time Algorithm for Triangulating a Simple Polygon}, journal = SJC, pages = {143--178}, year = 1988, volume = 17 } @techreport{TY-89, author = {M. J. Todd and Y. Ye}, title = {{A Centered Projective Algorithm for Linear Programming}}, institution = {School of Operations Research and industrial Engineering, Cornell University}, year = 1989, number = {763} } @unpublished{UY-89, author = {J. Ullman and M. Yannakakis}, title = {{High-Probability Parallel Transitive Closure Algorithms}}, year = 1989, note = {Unpublished manuscript} } @techreport{VB-93, author = {L. Vandenberghe and S. Boyd}, title = {Primal-dual potential reduction method for problems involving matrix inequalities}, institution = {{Information Systems Laboratory, Department of Electrical Engineering, Stanford University, Stanford, CA}}, year = {1993}, month = {January}, note = {{\em Math. Prog.} (to appear)} } @article{VKZ-77, author = {{P. {Van Emde Boas} and R. Kaas and E. Zijlstra}}, title = {Design and Implementation of an Efficient Priority Queue}, journal = {Math. Systems Theory}, pages = {99--127}, year = 1977, volume = 10 } @article{VKZ77, author = {P. Van ende Boas, R. Kaas, and E. Zijlstra}, title = {{Design and Implementation of an Efficient Priority Queue}}, journal = {Math. Sys. Theory}, pages = {99--127}, year = 1977, volume = 10 } @article{VS-84, author = {L. Stockmeyer and U. Vishkin}, title = {Simulation of Parallel Random Access Machines by Circuits.}, journal = SJC, pages = {409--422}, year = 1984, month = {May}, volume = 13, number = 2 } @article{VW-85, author = {U. Vishkin and A. Widgerson}, title = {Trade-offs Between Depth and Width in Parallel Computation}, journal = SJC, pages = {303--314}, year = 1985, month = {May}, volume = 14, number = 2 } @book{Wri-97, author = {Stephen J. Wright}, title = {Primal-Dual Interior-Point Methods}, year = 1997, publisher = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA} } @article{XY-95, author = {Y.~Ye and G.~L.~Xue}, title = {{An efficient algorithm for minimizing a sum of Euclidean norms with applications}}, journal = siamopt, year = 1995, note = {To appear} } @article{YN-76, author = {D.~Yudin and A.~Nemirovsky}, title = {Informational complexity and efficient methods for the solution of convex extermal problems}, journal = {Matekon}, year = 1977, volume = 13, number = 3, note = {translated from Russian} } @inproceedings{ali-91a, author = {F. Alizadeh}, title = {A Sublinear-Time Randomized Parallel Algorithm for the Maximum Clique Problem in Perfect Graphs}, booktitle = soda2, year = 1991 } @phdthesis{ali-91b, author = {F. Alizadeh}, title = {Combinatorial Optimization with Interior Point Methods and Semi-Definite Matrices}, year = 1991, school = {{Computer Science Department, University of Minnesota, Minneapolis, Minnesota}} } @incollection{ali-92a, author = {F. Alizadeh}, editor = {P. Pardalos}, title = {{Optimization Over Positive Semi-Definite Cone; Interior-Point Methods and Combinatorial Applications}}, booktitle = {Advances in Optimization and Parallel Computing}, year = 1992, publisher = {North-Holland}, address = {Amsterdam} } @inproceedings{ali-92b, author = {F. Alizadeh}, title = {Combinatorial Optimization with Semi-Definite Matrices}, booktitle = {proceedings of the second Integer Programming and Combinatorial Optimization (IPCO) conference}, year = 1992, publisher = {Carnegie-Mellon University} } @article{ali-95, author = {F. Alizadeh}, title = {Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization}, journal = siamopt, pages = {13--51}, year = 1995, volume = 5, number = 1 } @article{and-87, author = {R. J. Anderson}, title = {{A Parallel Algorithm for the Maximal Path Problem}}, journal = {Combinatorica}, year = 1987, volume = 7 } @article{ans-86, author = {K. M. Anstreicher}, title = {A monotone projective algorithm for fractional linear programming}, journal = {Algorithmica}, pages = {483--498}, year = 1986, volume = 1, number = 4 } @book{arb-93, author = {A. Arbel}, title = {Exploring Interior-Point Linear Programming}, year = 1993, publisher = {MIT Press}, address = {Cambridge, Massachusetts} } @inproceedings{awer-84, author = {B. Awerbuch}, title = {{An Efficient Network Synchronization Protocol}}, booktitle = stoc16, pages = {522--525}, year = 1984 } @article{awer-85, author = {B. Awerbuch}, title = {Complexity of Network Synchronization}, journal = jacm, pages = {804--823}, year = 1985, volume = 32 } @unpublished{awer-87, author = {B. Awerbuch}, title = {{A Tight Lower Bound on the Time of Distributed Maximal Independent Set Algorithms}}, year = 1987, note = {Unpublished manuscript} } @inproceedings{awer-89, author = {B. Awerbuch}, title = {{Distributed Shortest Paths Algorithms}}, booktitle = stoc21, pages = {490--500}, year = 1989 } @article{bal-85, author = {M. L. Balinski}, title = {{Signature Methods for the Assignment Problem}}, journal = or, pages = {527--536}, year = 1985, volume = 33 } @article{bar-82, author = {E. R. Barnes}, title = {An Algorithm for Partitioning the Nodes of a Graph}, journal = siamalgdisc, year = 1982, volume = 3 } @incollection{bar-83, author = {E. R. Barnes}, editor = {L. Lesniak and D. R. Lick and C. E. Wall}, title = {Partitioning the Nodes of a Graph}, booktitle = {Graph Theory with Applications to Algorithms and Computer Science}, year = 1982, publisher = {{John Wiley}} } @unpublished{bat-85, author = {C. A. Bateson}, title = {Performance Comparison of two Algorithms for Weighted Bipartite Matchings}, year = 1985, note = {M.S. thesis, Department of Computer Science, University of Colorado.} } @inproceedings{bea-86, author = {P. Beame}, title = {Limits on the Power of Concurrent-Write Parallel Machines}, booktitle = stoc18, pages = {169--176}, year = 1986, address = {Berkeley, California} } @phdthesis{bea-86-2, author = {P. Beame}, title = {Lower Bounds in Parallel Machine Computation}, year = 1986, school = {University of Toronto, Toronto, Canada} } @book{ber-73, author = {C. Berge}, title = {{Graphs and Hypergraphs}}, year = 1973, publisher = {North Holland}, pages = {85--86} } @unpublished{ber-79, author = {D. P. Bertsekas}, title = {{A Distributed Algorithm for the Assignment Problem}}, year = 1979, note = {Unpublished Manuscript, Lab. for Decision Systems, M.I.T.} } @inproceedings{ber-85, author = {D. P. Bertsekas}, title = {{A Distributed Asynchronous Relaxation Algorithm for the Assignment Problem}}, booktitle = {Proc. 24th IEEE Conference on Decision and Control, Ft.\ Lauderdale, FL}, year = 1985 } @inproceedings{ber-86, author = {D. P. Bertsekas}, title = {Distributed Asynchronous Relaxation Methods for Linear Network Flow Problems}, booktitle = {Proc. 25th IEEE Conference on Decision and Control, Athens, Greece}, year = 1986 } @techreport{ber-86-0, author = {D. P. Bertsekas}, title = {{Distributed Asynchronous Relaxation Methods for Linear Network Flow Problems}}, institution = {Lab. for Decision Systems, M.I.T.}, year = 1986, month = {September}, number = {LIDS-P-1986}, note = {(Revised November, 1986)} } @techreport{ber-86-2, author = {D. P. Bertsekas}, title = {Distributed Asynchronous Relaxation Methods for Linear Network Flow Problems}, institution = {Lab. for Decision Systems, M.I.T.}, year = 1986, month = {September}, number = {LIDS-P-1986} } @techreport{ber-86-3, author = {D. P. Bertsekas}, title = {{Distributed Asynchronous Relaxation Methods for Linear Network Flow Problems}}, institution = {Lab. for Decision Systems, M.I.T.}, year = 1986, number = {LIDS-P-1986} } @book{big-74, author = {N.~L.~Biggs}, title = {Algebraic Graph Theory}, year = 1974, publisher = {Cambridge University Press} } @techreport{blel-86, author = {G. Blelloch}, title = {{Parallel Prefix vs. Concurrent Memory Access}}, institution = {Thinking Machines, Inc.}, year = 1986 } @inproceedings{bop-87, author = {R.~B.~Boppana}, title = {{Eigenvalues and graph bisection: an average case analysis}}, booktitle = focs28, year = 1987 } @article{bre-74, author = {R. P. Brent}, title = {{The Parallel Evaluation of General Arithmetic Expressions}}, journal = JACM, pages = {201--206}, year = 1974, volume = 21 } @inproceedings{cai-86, author = {J.-Y. Cai}, title = {With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy}, booktitle = stoc18, pages = {21--29}, year = 1986 } @article{cher-77, author = {B. V. Cherkassky}, title = {{Algorithm of Construction of Maximal Flow in Networks with Complexity of ${O(V^2 \sqrt E )}$ Operations}}, journal = {Mathematical Methods of Solution of Economical Problems}, pages = {112--125}, year = 1977, volume = 7, note = {(In Russian)} } @incollection{cher-79, author = {B. V. Cherkassky}, editor = {A. V. Karzanov}, title = {{A Fast Algorithm for Computing Maximum Flow in a Network}}, booktitle = {Collected Papers, Issue 3: Combinatorial Methods for Flow Problems}, pages = {90--96}, year = 1979, publisher = {The Institute for Systems Studies, Moscow}, note = {(In Russian)} } @article{chv-73, author = {V.~Chvatal}, title = {Edmonds polytopes and a hierarchy of combinatorial problems}, journal = discmath, pages = {305--337}, year = 1973, volume = 4 } @inproceedings{cole-86, author = {R. Cole}, title = {Parallel Merge Sort}, booktitle = focs27, pages = {511--516}, year = 1986 } @article{cun-76, author = {W. H. Cunningham}, title = {{A Network Simplex Method}}, journal = {Math. Programming}, pages = {105--116}, year = 1976, volume = 11 } @book{dan-62, author = {G. B. Dantzig}, title = {{Linear Programming and Extensions}}, year = 1962, publisher = {Princeton Univ.\ Press, Princeton, NJ} } @article{dia-69, author = {R. B. Dial}, title = {{Algorithm 360: Shortest path forest with topological ordering}}, journal = {Comm. ACM}, pages = {632--633}, year = 1969, volume = 12 } @article{din-70, author = {E. A. Dinic}, title = {{Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation}}, journal = {Soviet Math. Dokl.}, pages = {1277--1280}, year = 1970, volume = 11 } @incollection{duf-56, author = {R. J. Duffin}, editor = {H. W. Kuhn and A. W. Tucker}, title = {{Infinite Programs}}, booktitle = {Linear inequalities and Related Systems}, pages = {157--170}, year = 1956, publisher = {{Princeton University Press, Princeton, NJ}} } @article{edm-65a, author = {J. Edmonds}, title = {{Paths, trees, and flowers}}, journal = {Canadian Journal of Mathematics}, pages = {449--467}, year = 1965, volume = 17 } @article{edm-65b, author = {J. Edmonds}, title = {{Maximum matching and a polyhedron with 0,1-vertices}}, journal = {Journal of Research of the National Bureau of Standards B}, pages = {125--130}, year = 1965, volume = 69 } @book{even-79, author = {S. Even}, title = {Graph Algorithms}, year = 1979, publisher = {Computer Science Press, Potomac, MD} } @article{fan-93, author = {M. Fan}, title = {A Quadratically Convergent Local Algorithm on Minimizing the Largest Eigenvalue of a Symmetric Matrix}, journal = laa, pages = {207--230}, year = 1993, volume = {{188,189}} } @book{fel-66, author = {William Feller}, title = {{An Introduction to Probability Theory and its Applications}}, year = 1966, publisher = {John Wiley \& Sons}, address = {New York}, volume = {{II}} } @book{fel-68, author = {William Feller}, title = {{An Introduction to Probability Theory and its Applications, Second Edition}}, year = 1968, publisher = {John Wiley \& Sons}, address = {New York}, volume = {{I}} } @article{fle-85, author = {R.~Fletcher}, title = {Semi-Definite Matrix Constraints in Optimization}, journal = siamcon, pages = {493-513}, year = 1985, volume = 23 } @book{fle-87, author = {R.~Fletcher}, title = {Practical Methods of Optimization}, year = 1987, publisher = {John Wiley} } @article{fly-72, author = {M. J. Flynn}, title = {Some Computer Organizations and Their Effectiveness}, journal = {IEEE Trans. Computers}, pages = {948-960}, year = 1972, volume = {9} } @article{fre-87, author = {G. Frederickson}, title = {{Fast Algorithms for Shortest Paths in Planar Graphs, with Applications}}, journal = SJC, pages = {1004-1022}, year = 1987, volume = 16 } @techreport{fre-88, author = {R. M. Freund}, title = {{Polynomial-Time Algorithms for Linear Programming Based only on Primal Scaling and Projective Gradients of a Potential Function}}, institution = {Operations Research Center, M.I.T.}, year = 1988, number = {OR-182-88} } @techreport{fre-94, author = {R. M. Freund}, title = {{Complexity of an Algorithm for Finding an Approximate Solution of a Semi-Definite Program with no Regularity Assumption}}, institution = {Operations Research Center, M.I.T.}, year = 1994, number = {OR-302-94} } @techreport{fuj-85, author = {S. Fujishige}, title = {{An ${O}(m^3 \log n)$ Capacity-Rounding Algorithm for the Minimum-Cost Circulation Problem: a Dual Framework of the {Tardos} Algorithm}}, institution = {University of Tsukuba, Japan}, year = 1985, number = 253 } @article{fuj-86, author = {S. Fujishige}, title = {{A Capacity-rounding Algorithm for the Minimum-Cost Circulation Problem: a Dual Framework of the {Tardos} Algorithm}}, journal = {Math. Prog.}, pages = {298--308}, year = 1986, volume = 35 } @article{ful-61, author = {D. R. Fulkerson}, title = {{An Out-of-Kilter Method for Minimal Cost Flow Problems}}, journal = {SIAM J. Appl. Math}, pages = {18--27}, year = 1961, volume = 9 } @article{gab-76, author = {H. N. Gabow}, title = {{Using Euler Partitions to Edge-Color Bipartite Multi-graphs}}, journal = {Int. J. Comput. Inform. Sci.}, pages = {345--355}, year = 1976, volume = {5} } @inproceedings{gab-83, author = {H. N. Gabow}, title = {{Scaling Algorithms for Network Problems}}, booktitle = focs24, pages = {248--258}, year = 1983 } @article{gab-85, author = {H. N. Gabow}, title = {{Scaling Algorithms for Network Problems}}, journal = {J. of Comp. and Sys. Sci.}, pages = {148--168}, year = 1985, volume = 31 } @inproceedings{gab-85-2, author = {H. N. Gabow}, title = {A Scaling Algorithm for Weighted Matching on General Graphs}, booktitle = focs26, pages = {90--100}, year = 1985 } @article{gal-80, author = {Z. Galil}, title = {{An ${O(V^{5/3} E^{2/3})}$ Algorithm for the Maximal Flow Problem}}, journal = {Acta Informatica}, pages = {221--242}, year = 1980, volume = 14 } @book{gas-58, author = {S. I. Gass}, title = {Linear Programming: Methods and Applications}, year = 1958, publisher = {McGraw-Hill} } @techreport{gol-85, author = {A. V. Goldberg}, title = {{A New Max-Flow Algorithm}}, institution = {Laboratory for Computer Science, M.I.T.}, year = 1985, number = {MIT/LCS/TM-291} } @phdthesis{gol-87, author = {A. V. Goldberg}, title = {Efficient Graph Algorithms for Sequential and Parallel Computers}, year = 1987, month = Jan, school = {M.I.T.}, note = {(Also available as Technical Report TR-374, Lab. for Computer Science, M.I.T., 1987)} } @techreport{gol-90, author = {A. V. Goldberg}, title = {{Processor-Efficient Implementation of a Maximum Flow Algorithm}}, institution = {Department of Computer Science, Stanford University}, year = 1990, number = {STAN-CS-90-1301} } @techreport{gol-91-1, author = {A. V. Goldberg}, title = {{Combinatorial Optimization. Lecture Notes for CS363/OR349. Winter 1991}}, institution = {Department of Computer Science, Stanford University}, year = 1991, number = {STAN-CS-91-1358} } @article{gol-91-2, author = {A. V. Goldberg}, title = {{Processor-Efficient Implementation of a Maximum Flow Algorithm}}, journal = ipl, pages = {179--185}, year = 1991 } @incollection{gom-63, author = {R.~Gomory}, editor = {R.~Graves andP.~Wolfe}, title = {An algorithm for integer solutions to linear programs}, booktitle = {Recent Advances in mathematical programming}, year = 1963, publisher = {McGraw-Hill} } @inproceedings{gon-89, author = {C. C. Gonzaga}, editor = {N. Megiddo}, title = {{An Algorithm for Solving Linear Programming in {$O(n^3L)$} Operations}}, booktitle = {Progress in Mathematical Programming}, pages = {1--28}, year = 1989, publisher = {Springer Verlag, Berlin} } @book{gra-81, author = {A.~Graham}, title = {{Kronecker Products and Matrix Calculus: with Applications}}, year = 1981, publisher = {Ellis Horwood}, address = {London} } @article{gri-86, author = {M. D. Grigoriadis}, title = {{An Efficient Implementation of the Network Simplex Method}}, journal = {Math.\ Prog.\ Study}, pages = {83--111}, year = 1986, volume = 26 } @unpublished{gul-97, author = {O. G{\"{u}}ler}, year = {1997}, note = {Personal communication} } @unpublished{gul-94, author = {O. G{\"{u}}ler}, title = {{Barrier Functions in Interior Point Methods}}, year = {1994}, note = {Manuscript}, school = {University of Maryland Balitomre County} } @techreport{gus-86, author = {D. Gusfield}, title = {On Scheduling Transmissions in a Network}, institution = {Department of Computer Science, Yale University}, year = 1986, number = {YALEU DCS TR 481} } @article{hal-35, author = {P. Hall}, title = {{On Representatives in Subsets}}, journal = {J. Lond. Math. Soc.}, pages = {26--30}, year = 1935, volume = 10 } @book{har-72, author = {F. Harary}, title = {Graph Theory}, year = 1972, publisher = {Addison-Wesley} } @article{has-81, author = {R. Hassin}, title = {{Maximum Flows in $(s,t)$ Planar Networks}}, journal = IPL, pages = {107--108}, year = 1981, volume = 13 } @article{has-83, author = {R. Hassin}, title = {{The Minimum-Cost Flow Problem: A Unifying Approach to Dual Algorithms and a New Tree-Search Algorithm}}, journal = mathprog, pages = {228--239}, year = 1983, volume = 25 } @inproceedings{has-86, author = {J. Hastad}, title = {Almost Optimal Lower Bounds for Small Depth Circuits}, booktitle = stoc18, pages = {6--20}, year = 1986, month = may } @unpublished{has-90, author = {R. Hasin}, title = {{Algorithms for the Minimum Cost Circulation Problem on Maximizing the Mean Improvement}}, year = 1990, note = {Unpublished manuscript, School of Mathematical Sciences, Department of Statistics, Tel Aviv University} } @book{hil-85, author = {W. D. Hillis}, title = {The Connection Machine}, year = 1985, publisher = {MIT Press} } @incollection{hof-75, author = {A.~J.~Hoffman}, editor = {R.~Fulkerson}, title = {Eigenvalues of graphs}, booktitle = {Studies in Graph Theory}, year = 1975, publisher = {Mathematical Association of America}, volume = 1 } @article{hu-63, author = {T. C. Hu}, title = {{Multi-Commodity Network Flows}}, journal = {J. ORSA}, pages = {344--360}, year = 1963, volume = 11 } @book{hu-69, author = {T. C. Hu}, title = {{Integer Programming and Network Flows}}, year = 1969, publisher = {Addison-Wesley, Reading, MA} } @article{iri-60, author = {M. Iri}, title = {{A New Method of Solving Transportation-Network Problems}}, journal = {J. Op. Res. Soc. Japan}, pages = {27--87}, year = 1960, volume = 3 } @article{itai-78, author = {A. Itai}, title = {Two-commodity flow}, journal = jacm, pages = {596--611}, year = 1978, volume = 25 } @techreport{jar-89, author = {F.~Jarre}, title = {The method of analytic centers for smooth convex programs}, institution = {{Mathematische Institute der Julius-Maximilians-universit\"at W\"urzburg}}, year = 1989, month = Feb, number = 169 } @article{jar-91a, author = {F.~Jarre}, title = {On the convergence of the method of analytic centers when applied to convex quadratic programs}, journal = mathprog, year = 1991, volume = 49 } @article{jar-93, author = {F.~Jarre}, title = {An interior-point method for minimizing the maximum eigenvalue of a linear combination of matrices}, journal = siamcon, pages = {1360--1377}, year = 1993, volume = 31, number = 5 } @book{jar-94, author = {Florian Jarre}, title = {Interior-Point Methods via Self-Concordance or Relative Lipschitz Condition}, year = 1994, publisher = {{Habilitationsschrift, University of W\"urzburg}}, address = {{Institut f\"ur Angewandte Mathematik, Am Hubland, 97074 W\"urzburg, Germany}}, note = { } } @techreport{jew-58, author = {W. S. Jewell}, title = {{Optimal Flow through Networks}}, institution = {M.I.T.}, year = 1958, number = {8} } @article{jew-62, author = {W. S. Jewell}, title = {{Optimal Flow through Networks with Gains}}, journal = or, pages = {476--499}, year = 1962, volume = 10 } @article{kar-74, author = {A. V. Karzanov}, title = {{Determining the Maximal Flow in a Network by the Method of Preflows}}, journal = {Soviet Math. Dok.}, pages = {434--437}, year = 1974, volume = 15 } @article{kar-84, author = {N. Karmarkar}, title = {A New Polynomial-Time Algorithm for Linear Programming}, journal = {Combinatorica}, pages = {373--395}, year = 1984, volume = 4 } @phdthesis{kar-85, author = {H. J. Karloff}, title = {{Fast Parallel Algorithms for Graph-Theoretic Problems: Matching, Coloring, Partitioning}}, year = 1985, school = {University of California, Berkeley} } @article{karl-86, author = {H.~Karloff}, title = {A Las Vegas RNC Algorithm for Maximum Matching}, journal = {Combinatorica}, year = 1986, volume = 6, number = 4 } @inproceedings{karl-96, author = {H.~Karloff}, title = {How Good is the Goemans-Williamson MAX CUT Algorithm?}, booktitle = stoc28, year = 1996 } @article{karp-78, author = {R. M. Karp}, title = {{A Characterization of the Minimum Cycle Mean in a Digraph}}, journal = discmath, pages = {309--311}, year = 1978, volume = 23 } @inproceedings{karp-91, author = {R. M. Karp}, title = {{Probabilistic Recurrence Relations}}, booktitle = stoc23, pages = {190--197}, year = 1991 } @article{ken-91, author = {R. Kennedy}, title = {{Parallel Cardinality Stacks and an Application}}, journal = ipl, year = {to appear} } @article{kha-80, author = {L. G. Khachian}, title = {{Polynomial Algorithms in Linear Programming}}, journal = {Zhurnal Vychislitelnoi Matematiki i Matematicheskoi Fiziki}, pages = {53--72}, year = 1980, volume = 20, note = {{English translation in {\em USSR computational mathematics and mathematical physics} 20(1980) pp.53--72}} } @techreport{KP-97, author = {L.~G.~Khachyan and L.~Porkolab}, title = {{Computing Integral Points in Convex Semi-Algebraic Sets}}, institution = {{RUTCOR, Rutgers University}}, month = {April}, year = 1997, number = {rrr 11-97}, address = {{640 Bartholomew Road, Piscataway, NJ 08854-8803}}, note = {{Available at URL: {\tt http://rutcor.rutgers.edu/pub/rrr/reports97/11.ps.gz}}} } @article{kle-67, author = {M. Klein}, title = {{A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems}}, journal = {Management Science}, pages = {205--220}, year = 1967, volume = 14 } @book{kon-50, author = {D. K{\"o}nig}, title = {{Theorie der Endlichen und Unendlichen Graphen}}, year = {1950}, publisher = {Chelsea Publishing Co., New York} } @article{kuh-55, author = {H. W. Kuhn}, title = {{The Hungarian Method for the Assignment Problem}}, journal = {Naval Res. Logist. Quart.}, pages = {83--97}, year = 1955, volume = 2 } @article{kuh-56, author = {H. W. Kuhn}, title = {{Variants of the {H}ungarian Method for Assignment Problem}}, journal = {Naval Res. Logist. Quart.}, pages = {253--258}, year = 1956, volume = 3 } @book{law-76, author = {E. L. Lawler}, title = {Combinatorial Optimization: Networks and Matroids}, year = 1976, publisher = {Holt, Reinhart, and Winston, New York, NY.} } @inproceedings{lin-87, author = {N. Linial}, title = {{Distributive Algorithms---Global Solutions from Local Data}}, booktitle = focs28, pages = {331--335}, year = 1987 } @article{lov-72, author = {L.~Lov\'{a}sz}, title = {Normal Hypergraphs and the Weak Perfect Graph Conjecture}, journal = discmath, pages = {253--267}, year = 1972, volume = 2 } @article{lov-79, author = {L.~Lov\'{a}sz}, title = {On the Shannon Capacity of a Graph}, journal = ieeeit, pages = {1--7}, year = 1979, month = Jan, volume = 25, number = 1 } @incollection{lov-83, author = {L.~Lov\'{a}sz}, editor = {L.~Beineke and R.~Wilson}, title = {Perfect Graphs}, booktitle = {Selected Topics in Graph Theory}, year = 1983, publisher = {Academic Press}, volume = 2 } @book{lov-86, author = {L.~Lov\'{a}sz}, title = {{An Algorithmic Theory of Numbers, Graphs and Convexity}}, year = 1986, publisher = {SIAM}, series = {CBMS-NSF50} } @techreport{lov-92, author = {L.~Lov\'{a}sz}, title = {{Combinatorial Optimization: Some Problems and Trends}}, institution = {DIMACS}, year = 1992, month = {November}, number = {{92--53}} } @inproceedings{lub-85, author = {M. Luby}, title = {A Simple Parallel Algorithm for the Maximal Independent Set Problem}, booktitle = stoc17, pages = {1--10}, year = 1985 } @inproceedings{luby-85, author = {M. Luby}, title = {{A Simple Parallel Algorithm for the Maximal Independent Set Problem}}, booktitle = stoc17, pages = {1--10}, year = 1985 } @article{luby-86, author = {M. Luby}, title = {{A Simple Parallel Algorithm for the Maximal Independent Set Problem}}, journal = SJC, pages = {1036--1052}, year = 1986, volume = 15 } @inproceedings{luby-88, author = {M. Luby}, title = {{Removing Randomness in Parallel Computation without a Processor Penalty}}, booktitle = focs29, pages = {162--173}, year = 1988 } @techreport{luby-88-1, author = {M. Luby}, title = {{Removing Randomness in Parallel Computation without a Processor Penalty}}, institution = {International Computer Science Institute, Berkeley}, year = 1989, number = {TR-89-044} } @book{lue-84, author = {{D. G. Luenberger}}, title = {{Linear and nonlinear Programming, second edition}}, year = 1984, publisher = {Addison-Wesley} } @techreport{LSZ-96, author = {Z.~-Q.~Luo and J.~F.~Sturm and S.~Zhang}, title = {{Superlinear convergence of a symmetric primal-dual path-following algorithm for semidefinite programming}}, institution = {{Econometric Institute, Erasmus University}}, year = 1996, address = {{Notterdam, The Netherlands}}, number = {9607} } @techreport{mar-87, author = {C. Martel}, title = {A Comparison of Phase and Non-phase Network Almv  gorithms}, institution = {Department of Electrical and Computer Engineering, University of California, Davis}, year = 1987, number = {CSE-87-7} } @unpublished{mcc-90, author = {S. T. McCormick}, title = {{A Strongly Polynomial Minimum Mean Cut Algorithm for Submodular Flow}}, year = 1990, note = {UBC Faculty of Commerce Working Paper 90-MSC-017} } @article{meg-83, author = {N. Megiddo}, title = {{Towards a Genuinely Polynomial Algorithm for Linear Programming}}, journal = sjc, pages = {347--353}, year = 1983, volume = 12 } @book{meg-89a, editor = {N. Megiddo}, title = {Progress in Mathematical Programming}, year = 1989, publisher = {Springer Verlag, Berlin}, address = {New York} } @inproceedings{meg-89b, author = {N. Megiddo}, editor = {N. Megiddo}, title = {Pathways to the Optimal Set in Linear Programming}, booktitle = {Progress in Mathematical Programming}, year = 1989, publisher = {Springer Verlag, Berlin}, address = {New York} } @book{meh-84, author = {K. Mehlhorn}, title = {Data Structures and Algorithms 1: Sorting and Searching}, year = 1984, publisher = {Springer-Verlag, Berlin} } @techreport{mgol-86, author = {M. Goldberg}, title = {{Parallel Algorithms for Three Graph Problems}}, institution = {RPI}, year = 1986, number = {86--4} } @article{min-60, author = {G. J. Minty}, title = {{Monotone Networks}}, journal = {Proc. Roy. Soc. London}, pages = {194--212}, year = 1960, volume = {A}, number = 257 } @article{min-73, author = {E. Minieka}, title = {{Maximal, Dynamic and Lexicographic Flows}}, journal = or, year = 1973, volume = 21 } @article{mye-83, author = {E. W. Myers}, title = {{An Applicative Random-Access Stack}}, journal = IPL, pages = {241--248}, year = 1983, volume = 17 } @unpublished{nem-93, author = {A. Nemirovskii}, title = {On Polynomiality of the Method of Analytic Centers for Fractional Problems}, year = 1993, note = {Unpublished Manuscript} } @article{ogi-86, author = {A. T. Ogielski}, title = {Integer Optimization and Zero-Temperature Fixed Point in {I}sing Random-Field Systems}, journal = {Physical Review Lett.}, pages = {1251--1254}, year = 1986, volume = 57 } @article{ona-66, author = {K. Onaga}, title = {{Dynamic Programming of Optimum Flows in Lossy Communication Nets}}, journal = {IEEE Trans. Circuit Theory}, pages = {308--327}, year = 1966, volume = 13 } @article{ona-67, author = {K. Onaga}, title = {{Optimal Flows in General Communication Networks}}, journal = {J. Franklin Inst.}, pages = {308--327}, year = 1967, volume = 283 } @techreport{orl-84, author = {J. B. Orlin}, title = {{Genuinely Polynomial Simplex and Non-Simplex Algorithms for the Minimum Cost Flow Problem}}, institution = {Sloan School of Management, MIT}, year = 1984, number = {No. 1615-84} } @article{orl-85, author = {J. B. Orlin}, title = {{On the Simplex Algorithm for Networks and Generalized Networks}}, journal = {Math. Prog. Studies}, pages = {166--178}, year = 1985, volume = 24 } @unpublished{orl-86, author = {J. B. Orlin}, title = {Unpublished manuscript}, year = 1986, note = { } } @inproceedings{orl-88, author = {J. B. Orlin}, title = {{A Faster Strongly Polynomial Minimum Cost Flow Algorithm}}, booktitle = stoc20, pages = {377--387}, year = 1988 } @article{ove-88, author = {M.~L. Overton}, title = {On minimizing the Maximum Eigenvalue of a Symmetric Matrix}, journal = siamx, pages = {256--268}, year = 1988, volume = 9, number = 2 } @article{ove-92, author = {M.~L. Overton}, title = {Large-Scale Optimization of Eigenvalues}, journal = siamopt, pages = {88--120}, year = 1992, volume = 2, number = 1 } @unpublished{pat-93, author = {G. Pataki}, title = {Algorithms for Linear Programs over Cones and Semi-Definite Programming}, year = 1993, note = {Manuscript, Graduate School of Industrial Administration, Carnegie-Mellon University}, address = {Pittsburgh} } @techreport{pat-94, author = {G. Pataki}, title = {On the Multiplicity of optimal eigenvalues}, institution = {{Graduate School of Industrial Administration, Carnegie-Mellon University}}, year = 1994, number = {{MSRR-604}} } @phdthesis{pat-96, author = {G.~Pataki}, title = {{Cone Programming and Nonsmooth Optimization: Geometry and Algorithms}}, school = {{Graduate School of Industrial Adminstration, Carnegie-Mellon University}}, year = 1996 } @inproceedings{pat-96b, author = {G.~Pataki}, title = {{Cone LP's and Semidefinite Programs: Geometry and a Simplex-type Method}}, booktitle = {proceedings of the fifth Integer Programming and Combinatorial Optimization (IPCO) conference}, year = 1996 } @techreport{PT-97, author = {G.~Pataki and L.~Tun\c{c}el}, title = {{On e Generic Properties of Convex Optimization Problems in Conic Form}}, number = {{CORR~97-16}}, year = 1997, institution = {{Department of Combnatorics and Optimization, University of Waterloo}}, address = {{Waterloo, Ontario N2L~3G1}} } @techreport{PS-95, author = {F.~A.~Potra and R.~Sheng}, title = {A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming}, number = 78, series = {Reports on Computational Mathematics}, institution = {{Department of Mathematics, The university of Iowa}}, address = {{Iowa City, IA}}, year = 1995 } @phdthesis{ram-93, author = {Motakuri Venkata Ramana}, title = {An Algorithmic Analysis of Multiquadratic and Semidefinite Programming Problems}, year = 1993, school = {Johns Hopkins University} } @article{raz-86, author = {A. A. Razborov}, title = {Lower Bounds for the Size of Circuits of Bounded Depth with Basis AND, XOR}, journal = {Matem. Zametki}, year = 1986, volume = {(To appear)}, note = {(In Russian)} } @article{rei-83, author = {J. H. Reif}, title = {{Minimum {\it s-t} Cut of a Planar Undirected Network in $O(n\log^2n)$ Time}}, journal = SJC, pages = {71--81}, year = 1983, volume = 12 } @article{ren-88, author = {J. Renegar}, title = {{A Polynomial Time Algorithm, Based on Newton's Method, for Linear Programming}}, journal = mathprog, pages = {59--94}, year = 1988, volume = 40 } @unpublished{rin-91, author = {{Ringertz, U. T.}}, title = {{Optimal Design of nonlinear Shell Structures}}, year = {1991}, note = {{Techniacal Report}}, institution = {{The Aeronautical Research Institute of Sweden}} } @book{roc-70, author = {R. T.~Rockafellar}, title = {Convex Analysis}, year = 1970, publisher = {Princeton University Press}, address = {{Princeton, NJ}} } @incollection{roc-80, author = {H. R{\"{o}}ck}, editor = {U. Pape}, title = {{Scaling Techniques for Minimal Cost Network Flows}}, booktitle = {Discrete Structures and Algorithms}, pages = {181--191}, year = 1980, publisher = {Carl Hansen, M{\"{u}}nich} } @article{ros-65, author = {J. B. Rosen}, title = {{Pattern Separation by Convex Programming}}, journal = {{Mathematical Analysis and Applications}}, pages = {123--134}, year = {1965}, volume = 10 } @article{ruh-88, author = {G. Ruhe}, title = {{Parametric Maximal Flows in Generalized Networks---Complexity and Algorithms}}, journal = {Optimization}, pages = {235--251}, year = 1988, volume = 19 } @article{rus-81, author = {W. L. Ruzzo}, title = {On Uniform Circuit Complexity}, journal = {Journal of Computer and System Sciences}, pages = {365--383}, year = 1981, volume = 22 } @article{sak-73, author = {M. Sakarovitch}, title = {Two-Commodity Network Flow and Linear Programming}, journal = mathprog, pages = {1--20}, year = 1973, volume = 5 } @article{sch-80, author = {J. T. Schwartz}, title = {{Ultracomputers}}, journal = acmtopls, pages = {484--521}, year = 1980, volume = 2 } @book{sch-66, author = {R.~D.~Schafer}, title = {{An Introuduction to Nonassociative Algebras}}, year = 1966, publisher = {Academic Press}, address = {New York} } @book{sch-86, author = {A. Schrijver}, title = {{Theory of Linear and Integer Programming}}, year = 1986, publisher = {J. Wiley \& Sons}, address = {New York} } @article{sha-85, author = {A.~Shapiro}, title = {Extremal problems on the set of nonnegative definite matrices}, journal = laa, pages = {7--18}, year = 1985, volume = 67 } @article{sha-97, author = {A.~Shapiro}, title = {First and second order analysis of nonlinear semidefinite programs}, journal = mathprog, pages = {301--320}, year = 1997, volume = 77 } @unpublished{sha-86, author = {G. Shannon}, title = {Reduction Techniques for Designing Linear-Processor Parallel Algorithms on Sparse Graphs}, year = 1986, note = {Unpublished manuscript} } @article{sha-95, author = {A.~Shapiro}, title = {First and Second Order Analysis of Nonlinear Semidefinite Programs}, journal = mathprog, year = 1995, note = {To appear} } @techreport{shil-78, author = {Y. Shiloach}, title = {{An ${O(n I \log^2 I)}$ Maximum-Flow Algorithm}}, institution = {Computer Science Department, Stanford University, Stanford, CA}, year = 1978, number = {STAN-CS-78-802} } @article{sho-77, author = {N.~Shor}, title = {Cut-off methods with space extension in convex programming problems}, journal = {Cybernatics}, pages = {94--95}, year = 1977, volume = 13, note = {Translated from Russian} } @book{sin-93, author = {Alistair Sinclair}, title = {{Algorithms for Random Generation \& Counting}}, year = 1993, publisher = {{Birkh\"aser}}, address = {Boston}, optcallno = {{QA274.7S56}} } @techreport{sle-80, author = {D. D. Sleator}, title = {{An ${O}(n m \log n)$ Algorithm for Maximum Network Flow}}, institution = {Computer Science Department, Stanford University, Stanford, CA}, year = 1980, number = {STAN-CS-80-831} } @article{smith-86, author = {J. Smith}, title = {{Parallel Algorithms for Depth-First Searches I. Planar Graphs}}, journal = sicomp, pages = {814--830}, year = {1986}, volume = {15} } @inproceedings{smol-86, author = {R. Smolensky}, title = {Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity}, booktitle = stoc19, year = 1987 } @article{son-86, author = {G.~Sonnevend}, title = {{An ``analytic centre''for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming}}, journal = {Lecture Notes in Control and Information Science}, pages = {886--878}, year = 1986, volume = 84 } @mastersthesis{sub-93, author = {S. Subramani}, title = {{Sums of Singular Values}}, year = 1993, school = {{School of Mathematics, University of New South Wales, Kensington, Australia}} } @article{tar-72, author = {R. E. Tarjan}, title = {{Depth-First Search and Linear Graph Algorithms}}, journal = SJC, pages = {146--160}, year = 1972, volume = 1 } @book{tar-83, author = {R. E. Tarjan}, title = {Data Structures and Network Algorithms}, year = 1983, publisher = {Society for Industrial and Applied Mathematics, Philadelphia, PA} } @article{tar-84, author = {R. E. Tarjan}, title = {{A Simple Version of {K}arzanov's Blocking Flow Algorithm}}, journal = {Operations Research Letters}, pages = {265--268}, year = 1984, volume = 2 } @article{tar-85, author = {R. E. Tarjan}, title = {{Amortized Computational Complexity}}, journal = {SIAM J. Alg. Disc. Math.}, pages = {306--318}, year = 1985, volume = 6 } @techreport{tar-88, author = {R. E. Tarjan}, title = {{Efficiency of the Primal Network Simplex Algorihm for the Minimum-Cost Circulation Problem}}, institution = {Department of Computer Science, Princeton University}, year = 1988, number = {CS-TR-187-88} } @article{tard-85, author = {\'E. Tardos}, title = {{A Strongly Polynomial Minimum Cost Circulation Algorithm}}, journal = {Combinatorica}, pages = {247--255}, year = 1985, volume = 5, number = 3 } @article{tard-86, author = {\'E. Tardos}, title = {A strongly polynomial algorithm for solving combinatorial linear programs}, journal = or, pages = {250--256}, year = 1986 } @techreport{todd-88, author = {M. J. Todd}, title = {{Recent Developments and New Directions in Linear Programming}}, institution = {School of Operations Research and Industrial Engineering, Cornell University}, year = 1988, number = {829} } @techreport{TTT-96, author = {M.~J.~Todd and K.~C.~Toh and R.~H.~T{\"ut\"unc\"u}}, title = {{On the Nesterov-Todd direction in semidefinite programming}}, institution = {School of Operations Research and Industrial Engineering, Cornell University}, year = 1996, number = {829} } @article{tom-72, author = {N. Tomizawa}, title = {{On Some Techniques Useful for Solution of Transportation Networks Problems}}, journal = {Networks}, pages = {173--194}, year = 1972, volume = 1 } @phdthesis{tru-73, author = {K. Truemper}, title = {{Optimal Flows in Networks with Positive Gains}}, year = 1986, school = {University of Toronto, Toronto, Canada} } @article{tru-77, author = {K. Truemper}, title = {{On Max Flows with Gains and Pure Min-Cost Flows}}, journal = {SIAM J. Appl. Math.}, pages = {450--456}, year = 1977, volume = 32 } @techreport{tse-96, author = {P.~Tseng}, title = {{Search directions and convergence analysis of some infeasible path-fllowing methods for the monotone semi-definite LCP}}, institution = {{Department of Mathemaics, University of Washington}}, address = {{Seatle, WA 98195}}, number = {{}}, year = 1996 } @techreport{tsu-97, author = {Takashi Tsuchiya}, title = {{A Polynomial Primal-Dual Path-Following Algorithm for Second-Order Cone Programming}}, institution = {{The Institute of Statistical Mathematics}}, address = {{Tokyo, Japan}}, number = {{Research Memorandum No. 649}}, year = 1997 } @techreport{tsu-98, author = {Takashi Tsuchiya}, title = {{A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming}}, institution = {{The Institute of Statistical Mathematics}}, address = {{Tokyo, Japan}}, number = {{Research Memorandum No. 664}}, year = 1998 } @inproceedings{vai-87, author = {P. M. Vaidya}, title = {An Algorithm for Linear Programming that Requires {$O(((m+n)n^2 + (m+n)^{1.5}n)L)$} Arithmetic Operations}, booktitle = stoc19, pages = {29--38}, year = 1987 } @inproceedings{vai-89, author = {P. M. Vaidya}, title = {{Speeding up Linear Programming Using Fast Matrix Multiplication}}, booktitle = focs30, year = 1989 } @inproceedings{val-82, author = {L. G. Valiant}, title = {Parallel Computation}, booktitle = {Proc. 7th IBM Symp. on Mathemetical Foundations of Computer Science}, year = 1982 } @techreport{vish-90, author = {U. Vishkin}, title = {{A Parallel Blocking Flow Algorithm}}, institution = {University of Maryland Inst. for Advanced Comp. Studies}, year = 1990, number = {UMIACS-TR-90-11} } @article{wag-76, author = {R. A. Wagner}, title = {A Shortest Path Algorithm for Edge-Sparse Graphs}, journal = jacm, pages = {50--57}, year = 1976, volume = 23 } @article{wei-74, author = {A. Weintraub}, title = {{A Primal Algorithm to Solve Network Flow Problems with Convex Costs}}, journal = {Management Science}, pages = {87--97}, year = 1974, volume = 21 } @article{wol-81, author = {H.~Wolkowicz}, title = {Some applications of optimization in matrix theory}, journal = laa, pages = {101--118}, year = 1981, volume = 40 } @incollection{yak-59, author = {M. A. Yakovleva}, editor = {V. S. Nemchinov}, title = {{A Problem on Minimum Transportation Cost}}, booktitle = {Applications of Mathematics in Economic Research}, pages = {390--399}, year = 1959, publisher = {Izdat. Social'no-{E}kon. Lit., Moscow} } @article{yan-91, author = {M. Yannakakis}, title = {Expressing Combinatorial Optimization Problems by Linear Programs}, journal = jcss, pages = {441--466}, year = 1991, volume = 43, number = 3 } @inproceedings{yao-85, author = {A. Yao}, title = {Separating the Polynomial-Time Hierarchy by Oracles}, booktitle = focs26, pages = {1--10}, year = 1985 } @techreport{ye-88a, author = {Y.~Ye}, title = {A Class of Potential Reduction Functions For Linear Programming}, institution = {{Department of Management Sciences, The University of Iowa}}, year = 1988, number = {88--13}, type = {Working Paper} } @techreport{ye-88b, author = {Y.~Ye}, title = {The potential algorithm for convex linear complementarity problem}, institution = {{Department of Management Sciences, The University of Iowa}}, year = 1988, type = {Working Paper} } @article{ye-90, author = {Y. Ye}, title = {A Class of Projective Transformations for Linear Programming}, journal = siamcomp, pages = {457--466}, year = 1990, volume = 19, number = 3 } @article{ye-91, author = {Y. Ye}, title = {{An {$O(n^3L)$} Potential Reduction Algorithm for Linear Programming}}, journal = mathprog, pages = {239--258}, year = 1991, volume = 50, number = 2 } @techreport{ye-92a, author = {Y. Ye}, title = {{On the von Neumann economic growth problem}}, institution = {{Department of Management Sciences, The University of Iowa, Iowa City, IA 52242}}, year = 1992, month = {March}, number = {{92--9}}, type = {Working Paper} } @unpublished{you-87, author = {N. Young}, title = {Finding a Minimum Mean Cycle: an ${O(nm\log (n))}$ Time Primal-Dual Algorithm}, year = 1987, note = {(Unpublished manuscript, Department of Computer Science, Princeton University)} } @article{zad-73, author = {N. Zadeh}, title = {{A Bad Network Problem for the Simplex Method and Other Minimum Cost Flow Algorithms}}, journal = mathprog, pages = {255--266}, year = 1973, volume = 5 } @article{zad-73-2, author = {N. Zadeh}, title = {{More Pathological Examples for Network Flow Problems}}, journal = mathprog, pages = {217--224}, year = 1973, volume = 5 } @unpublished{zim-89, author = {U. Zimmermann}, title = {{Negative Circuits for Flows and Submodular Flows}}, year = 1989, note = {Preprints in Optimization Series, Institute F{\"{u}}r Angewandte Mathematik, Techniche Universit{\"{a}}t Caroto-Wilhemina zu Brauschweig, Brauschweig, West Germany} } @techreport{zha-95, author = {Y.~Zhang}, title = {On extending primal-dual interior-point algorithms from linear programming to semidefinite programming}, institution = {{Dept. of Math/Stat, University of Maryland}}, address = {Baltimore County, MD 21228, USA}, year = 1995, number = {{TR 95-20}} }