An Accelerated Newton–Dinkelbach Method and Its Application to Two Variables per Inequality Systems

References

• [1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms and Applications (Prentice Hall, Hoboken, NJ).Google Scholar
• [2] Aspvall B, Shiloach Y (1980) A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. SIAM J. Comput. 9(4):827–845.Crossref, Google Scholar
• [3] Cohen E, Megiddo N (1994) Improved algorithms for linear inequalities with two variables per inequality. SIAM J. Comput. 23(6):1313–1347.Crossref, Google Scholar
• [4] Dadush D, Végh LA, Zambelli G (2018) Geometric rescaling algorithms for submodular function minimization. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 832–848.Google Scholar
• [5] Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Math. 1:269–271.Crossref, Google Scholar
• [6] Dinkelbach W (1967) On nonlinear fractional programming. Management Sci. 13(7):492–498.Link, Google Scholar
• [7] Edelsbrunner H, Rote G, Welzl E (1989) Testing the necklace condition for shortest tours and optimal factors in the plane. Theoret. Comput. Sci. 66(2):157–180.Crossref, Google Scholar
• [8] Feinberg EA, Huang J (2014) The value iteration algorithm is not strongly polynomial for discounted dynamic programming. Oper. Res. Lett. 42(2):130–131.Crossref, Google Scholar
• [9] Fredman ML, Tarjan RE (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3):596–615.Crossref, Google Scholar
• [10] Goemans MX, Gupta S, Jaillet P (2017) Discrete Newton’s algorithm for parametric submodular function minimization. Proc. 19th Internat. Conf. Integer Programming Combinatorial Optim. (Springer, New York), 212–227.Google Scholar
• [11] Goldberg AV, Tarjan RE (1989) Finding minimum-cost circulations by canceling negative cycles. J. ACM 36(4):873–886.Crossref, Google Scholar
• [12] Hansen TD, Kaplan H, Zwick U (2014) Dantzig’s pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM–SIAM, New York–Philadelphia), 847–860.Google Scholar
• [13] Hochbaum DS, Naor J (1994) Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. 23(6):1179–1192.Crossref, Google Scholar
• [14] Hochbaum DS, Megiddo N, Naor J, Tamir A (1993) Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Programming 62:69–83.Crossref, Google Scholar
• [15] Iwata S (2008) Submodular function minimization. Math. Programming 112(1):45–64.Crossref, Google Scholar
• [16] Iwata S, Orlin JB (2009) A simple combinatorial algorithm for submodular function minimization. Proc. Twentieth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, New York), 1230–1237.Google Scholar
• [17] Jiang H (2021) Minimizing convex functions with integral minimizers. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 976–985.Google Scholar
• [18] Karczmarz A (2022) Improved strongly polynomial algorithms for deterministic MDPs, 2VPI feasibility, and discounted all-pairs shortest paths. Proc. 2022 ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 154–172.Google Scholar
• [19] Lee YT, Sidford A, Wong SC (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. 2015 IEEE 56th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Berkeley, CA), 1049–1065.Google Scholar
• [20] Littman ML, Dean TL, Kaelbling LP (1995) On the complexity of solving Markov decision problems. Proc. 11th Annual Conf. Uncertainty Artificial Intelligence (UAI) (Morgan Kaufmann, Burlington, MA), 394–402.Google Scholar
• [21] Madani O (2002) On policy iteration as a Newton’s method and polynomial policy iteration algorithms. Proc. 18th National Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 273–278.Google Scholar
• [22] Megiddo N (1979) Combinatorial optimization with rational objective functions. Math. Oper. Res. 4(4):414–424.Link, Google Scholar
• [23] Megiddo N (1983) Towards a genuinely polynomial algorithm for linear programming. SIAM J. Comput. 12(2):347–353.Crossref, Google Scholar
• [24] Nagano K (2007) A strongly polynomial algorithm for line search in submodular polyhedra. Discrete Optim. 4(3–4):349–359.Crossref, Google Scholar
• [25] Olver N, Végh LA (2020) A simpler and faster strongly polynomial algorithm for generalized flow maximization. J. ACM 67(2):10.1–10.26.Crossref, Google Scholar
• [26] Post I, Ye Y (2015) The simplex method is strongly polynomial for deterministic Markov decision processes. Math. Oper. Res. 40(4):859–868.Link, Google Scholar
• [27] Radzik T (1992) Newton’s method for fractional combinatorial optimization. Proc. 33rd Annual Sympos. Foundations Comput. Sci., 659–669.Google Scholar
• [28] Radzik T (1998) Fractional combinatorial optimization. Du DZ, Pardalos PM, eds. Handbook of Combinatorial Optimization, vol. 1 (Springer, New York), 429–478.Crossref, Google Scholar
• [29] Radzik T, Goldberg AV (1994) Tight bounds on the number of minimum-mean cycle cancellations and related results. Algorithmica 11(3):226–242.Crossref, Google Scholar
• [30] Shostak RE (1981) Deciding linear inequalities by computing loop residues. J. ACM 28(4):769–779.Crossref, Google Scholar
• [31] Smale S (1998) Mathematical problems for the next century. Math. Intelligencer 20:7–15.Crossref, Google Scholar
• [32] Tardos É (1985) A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3):247–256.Crossref, Google Scholar
• [33] Topkis DM (1978) Minimizing a submodular function on a lattice. Oper. Res. 26(2):305–321.Link, Google Scholar
• [34] Végh LA (2017) A strongly polynomial algorithm for generalized flow maximization. Math. Oper. Res. 42(1):179–211.Link, Google Scholar
• [35] Wang Q, Yang X, Zhang J (2006) A class of inverse dominant problems under weighted ℓ∞ norm and an improved complexity bound for Radzik’s algorithm. J. Global Optim. 34(4):551–567.Crossref, Google Scholar