Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs

References

• [1] Ahuja RK, Batra JL, Gupta SK (1984) A parametric algorithm for convex cost network flow and related problems. Eur. J. Oper. Res. 16:222–235.Crossref, Google Scholar
• [2] Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Englewood Cliffs, NJ).Google Scholar
• [3] Aissi H, Mahjoub AR, McCormick ST, Queyranne M (2015) Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs. Math. Programming 154(1–2):3–28.Crossref, Google Scholar
• [4] Arezki Y, van Vliet D (1990) A full analytical implementation of the Partan/Frank-Wolfe algorithm for equilibrium assignment. Transportation Sci. 24(1):58–62.Link, Google Scholar
• [5] Bar-Gera H (2002) Origin-based algorithm for the traffic assignment problem. Transportation Sci. 36(4):398–417.Link, Google Scholar
• [6] Beckmann MJ, McGuire CB, Winsten CB (1956) Studies in the Economics of Transportation (Yale University Press, New Haven, CT).Google Scholar
• [7] Best MJ (1996) An algorithm for the solution of the parametric quadratic programming problem. Fischer H, Riedmüller B, Schäffler S, eds. Applied Mathematics and Parallel Computing (Physica-Verlag).Crossref, Google Scholar
• [8] Birkhoff G, Diaz JB (1956) Non-linear network problems. Quart. Appl. Math. 13(4):431–443.Crossref, Google Scholar
• [9] Braess D (1968) Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12(1):258–268.Google Scholar
• [10] Carstensen P (1983) The complexity of some problems in parametric linear and combinatorial programming. PhD thesis, University of Michigan, Ann Arbor.Google Scholar
• [11] Cohen MB, Kyng R, Miller GL, Pachocki JW, Peng R, Rao AB, Xu SC (2014) Solving SDD linear systems in nearly mlog 1/2n time. Shmoys D, ed. Proc. 46th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 343–352.Google Scholar
• [12] Coppersmith D, Winograd S (1987) Matrix multiplication via arithmetic progressions. Aho AV, ed. Proc. 19th Annual ACM Sympos. Theory Comput (Association for Computing Machinery, New York), 1–6.Google Scholar
• [13] Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms, 3rd ed. (MIT Press, Cambridge, MA).Google Scholar
• [14] Correa J, Stier-Moses NE (2010) Wardrop equilibria. Cochran JJ, ed. Wiley Encyclopedia of Operations Research and Management Science (Wiley & Sons, Hoboken, NJ).Google Scholar
• [15] Disser Y, Skutella M (2015) The simplex algorithm is NP-mighty. Indyk P, ed. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms, (Society for Industrial and Applied Mathematics, Philadelphia), 858–872.Google Scholar
• [16] Duffin RJ (1947) Nonlinear networks. IIa. Bull. Amer. Math. Soc. (New Series) 53(10):963–971.Crossref, Google Scholar
• [17] Duffin RJ (1965) Topology of series-parallel networks. J. Math. Anal. Appl. 10(2):303–318.Crossref, Google Scholar
• [18] Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• [19] Gallo G, Grigoriadis MD, Tarjan RE (1989) A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1):30–55.Crossref, Google Scholar
• [20] Gill PE, Golub GH, Murray W, Saunders MA (1974) Methods for modifying matrix factorizations. Math. Comput. 28(126):505–535.Crossref, Google Scholar
• [21] Goldberg PW, Papadimitriou CH, Savani R (2013) The complexity of the homotopy method, equilibrium selection, and Lemke-Howson solutions. ACM Trans. Econom. Comput. 1(2):1–25.Crossref, Google Scholar
• [22] Granot F, McCormick ST, Queyranne M, Tardella F (2012) Structural and algorithmic properties for parametric minimum cuts. Math. Programming 135(1):337–367.Crossref, Google Scholar
• [23] Grone R (1991) On the geometry and Laplacian of a graph. Linear Algebra Appl. 150:167–178.Crossref, Google Scholar
• [24] Gross M, Pfetsch ME, Schewe L, Schmidt M, Skutella M (2018) Algorithmic results for potential-based flows: Easy and hard cases. Networks 73(3):306–324.Crossref, Google Scholar
• [25] Hager WW (1989) Updating the inverse of a matrix. SIAM Rev. 31(2):221–239.Crossref, Google Scholar
• [26] Harks T, Kleinert I, Klimm M, Möhring RH (2015) Computing network tolls with support constraints. Networks 65(3):262–285.Crossref, Google Scholar
• [27] Harville DA (1997) Matrix Algebra from a Statistician’s Perspective (Springer, New York).Crossref, Google Scholar
• [28] Herings PJJ, Peeters R (2010) Homotopy methods to compute equilibria in game theory. Econom. Theory 42(1):119–156.Crossref, Google Scholar
• [29] Herings PJJ, van den Elzen AH (2002) Computation of the Nash equilibrium selected by the tracing procedure in n-person games. Games Econom. Behav. 38(1):89–117.Crossref, Google Scholar
• [30] Karp RM, Orlin JB (1981) Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl. Math. 3(1):37–45.Crossref, Google Scholar
• [31] Katzenelson J (1965) An algorithm for solving nonlinear resistor networks. Bell Systems Tech. J. 44(8):1605–1620.Crossref, Google Scholar
• [32] Kelner JA, Orecchia L, Sidford A, Allen Zhu Z (2013) A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. Boneh D, Roughgarden T, Feigenbaum J, eds. Proc. 45th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 911–920.Google Scholar
• [33] Khachiyan L, Tarasov S, Erlich E (1988) The inscribed ellipsoid method. Soviet Math. Dokl. 37(1):226–230.Google Scholar
• [34] Kirchhoff G (1847) Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Ann. Phys. 148(12):497–508.Crossref, Google Scholar
• [35] Klimm M, Warode P (2019) Computing all Wardrop equilibria parametrized by the flow demand. Chan TM, Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 917–934.Google Scholar
• [36] Klimm M, Pfetsch M, Raber R, Skutella M (2020) On the robustness of potential-based flow networks. Technical report. Technische Universität Darmstadt, Darmstadt, Germany.Google Scholar
• [37] Kojima M, Nishino H, Sekine T (1976) An extension of Lemke’s method to the piece-wise linear complementarity problem. SIAM J. Appl. Math. 31(4):600–613.Crossref, Google Scholar
• [38] Kozlov MK, Tarasov SP, Khachiyan LG (1980) The polynomial solvability of convex quadratic programming. USSR Comput. Math. Math. Phys. 20(5):223–228.Crossref, Google Scholar
• [39] Kyng R, Sachdeva S (2016) Approximate Gaussian elimination for Laplacians—Fast, sparse, and simple. Ostrovsky R, Dinur I, eds. Proc. 57th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Computer Society, Los Alamitos, CA), 573–582.Google Scholar
• [40] LeBlanc LJ, Helgason RV, Boyce DE (1985) Improved efficiency of the Franke-Wolfe algorithm for convex network programs. Transportation Sci. 19(4):445–462.Link, Google Scholar
• [41] Lemke CE, Howson JT Jr (1964) Equilibrium points of bimatrix games. SIAM J. Appl. Math. 12(2):413–423.Crossref, Google Scholar
• [42] Merris R (1994) Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197:143–176.Crossref, Google Scholar
• [43] Minoux M (1984) A polynomial algorithm for minimum quadratic cost flow problems. Eur. J. Oper. Res. 18(3):377–387.Crossref, Google Scholar
• [44] Minoux M (1986) Solving integer minimum cost flows with separable convex cost objective polynomially. Gallo G, Sandi C, eds. Netflow at Pisa (Springer, Berlin), 237–239.Crossref, Google Scholar
• [45] Mohar B, Alavi Y, Chartrand G, Oellermann OR (1991) The Laplacian spectrum of graphs. Alavi Y, Chartrand G, Ollermann O, Schwenk A, eds. Graph Theory, Combinatorics, and Applications (Wiley, New York), 871–898.Google Scholar
• [46] Murty K (1980) Computational complexity of parametric linear programming. Math. Programming 19(1):213–219.Crossref, Google Scholar
• [47] Nesterov YE, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (Society of Industrial and Applied Mathematics, Philadelphia). Google Scholar
• [48] Nikolova E, Kelner J, Brand M, Mitzenmacher M (2006) Stochastic shortest paths via quasi-convex maximization. Azar Y, Erlebach T, eds. Proc. 14th Annual Eur. Sympos. Algorithms (Springer, Berlin), 552–563.Crossref, Google Scholar
• [49] O’Hare SJ, Connors RD, Watling DP (2016) Mechanisms that govern how the Price of Anarchy varies with travel demand. Transportation Res. Part B 84:55–80.Crossref, Google Scholar
• [50] Rockafellar RT (1984) Network Flows and Monotropic Optimization (John Wiley and Sons, Hoboken, NJ).Google Scholar
• [51] Ruszczyński A (2006) Nonlinear Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [52] Sacher RS (1980) A decomposition algorithm for quadratic programming. Math. Programming 18(1):16–30.Crossref, Google Scholar
• [53] Sherman J, Morrison WJ (1950) Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann. Math. Statist. 21(1):124–127.Crossref, Google Scholar
• [54] Spielman DA, Teng S (2004) Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. Láaszló Babai, ed. Proc. 36th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 81–90.Google Scholar
• [55] Spielman DA, Teng SH (2014) Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Anal. Appl. 35(3):835–885.Crossref, Google Scholar
• [56] Végh L (2016) A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. SIAM J. Comput. 45(5):1729–1761.Crossref, Google Scholar
• [57] Wardrop JG (1952) Some theoretical aspects of road traffic research. Proc. Inst. Civil Engrg. 1(3):325–378.Crossref, Google Scholar
• [58] Youn H, Gastner MT, Jeong H (2008) Price of Anarchy in transportation networks: efficiency and optimality control. Phys. Rev. Lett. 101(12):128701-1–128701-4.Crossref, Google Scholar
• [59] Zadeh N (1973) A bad network problem for the simplex method and other minimum cost flow algorithms. Math. Programming 5(1):255–266.Crossref, Google Scholar