Fair Integral Network Flows

References

• [1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows—Theory, Algorithms and Applications (Prentice-Hall, Englewood Cliffs, NJ).Google Scholar
• [2] Borradaile G, Iglesias J, Migler T, Ochoa A, Wilfong G, Zhang L (2017) Egalitarian graph orientations. J. Graph Algorithms Appl. 21(4):687–708.Crossref, Google Scholar
• [3] Dinits EA (1970) Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doklady 11:1277–1280.Google Scholar
• [4] Edmonds J, Giles R (1977) A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1:185–204.Crossref, Google Scholar
• [5] Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2):248–264.Crossref, Google Scholar
• [6] Ford LR Jr, Fulkerson DR (1962) Flows in Networks (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [7] Frank A (1979) Kernel systems of directed graphs. Acta Scientiarum Mathematicarum 41:63–76.Google Scholar
• [8] Frank A (2011) Connections in Combinatorial Optimization (Oxford University Press, Oxford, UK).Google Scholar
• [9] Frank A, Murota K (2018) Discrete decreasing minimization, Part II: Views from discrete convex analysis. Preprint, submitted August 25, https://arxiv.org/abs/1808.08477.Google Scholar
• [10] Frank A, Murota K (2021) Decreasing minimization on M-convex sets: Background and structures. Math. Programming ePub ahead of print, October 27, https://doi.org/10.1007/s10107-021-01722-2.Google Scholar
• [11] Frank A, Murota K (2021) Decreasing minimization on M-convex sets: Algorithms and applications. Math. Programming ePub ahead of print, October 15, https://doi.org/10.1007/s10107-021-01711-5.Google Scholar
• [12] Frank A, Murota K (2022) Fair integral submodular flows. Discrete Appl. Math. 320:416–434.Google Scholar
• [13] Fujishige S (1980) Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5(2):186–196.Link, Google Scholar
• [14] Fujishige S (2005) Submodular Functions and Optimization, 2nd ed., Annals of Discrete Mathematics, vol. 58 (Elsevier, Amsterdam).Google Scholar
• [15] Georgiadis L, Georgatsos P, Floros K, Sartzetakis S (2002) Lexicographically optimal balanced networks. IEEE/ACM Trans. Networking 10(6):818–829.Crossref, Google Scholar
• [16] Goemans MX, Gupta S, Jaillet P (2017) Discrete Newton’s algorithm for parametric submodular function minimization. Eisenbrand F, Koenemann J, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 10328, 212–227.Crossref, Google Scholar
• [17] Goldberg AV, Tarjan RE (1988) A new approach to the maximum-flow problem. J. ACM 35(4):921–940.Crossref, Google Scholar
• [18] Harvey NJA, Ladner RE, Lovász L, Tamir T (2006) Semi-matchings for bipartite graphs and load balancing. J. Algorithms 59(1):53–78.Crossref, Google Scholar
• [19] Hochbaum DS, Shanthikumar JG (1990) Convex separable optimization is not much harder than linear optimization. J. ACM 37(4):843–862.Crossref, Google Scholar
• [20] Hoffman AJ (1960) Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. Bellman R, Hall M Jr., eds. Combin. Anal. Proc. Sympos. Appl. Math., vol. 10 (American Mathematical Society, Providence, RI), 113–127.Google Scholar
• [21] Ibaraki T, Katoh N (1988) Resource Allocation Problems: Algorithmic Approaches (MIT Press, Cambridge, MA).Google Scholar
• [22] Kaibel V, Onn S, Sarrabezolles P (2015) The unimodular intersection problem. Oper. Res. Lett. 43(6):592–594.Crossref, Google Scholar
• [23] Katoh N, Shioura A, Ibaraki T (2013) Resource allocation problems. Pardalos PM, Du D-Z, Graham RL, eds. Handbook of Combinatorial Optimization, vol. 5, 2nd ed. (Springer, Berlin), 2897–2988.Crossref, Google Scholar
• [24] Megiddo N (1974) Optimal flows in networks with multiple sources and sinks. Math. Programming 7:97–107.Crossref, Google Scholar
• [25] Megiddo N (1977) A good algorithm for lexicographically optimal flows in multi-terminal networks. Bull. Amer. Math. Soc. 83(3):407–409.Crossref, Google Scholar
• [26] Moulin H (2003) Fair Division and Collective Welfare (MIT Press, Cambridge, MA).Crossref, Google Scholar
• [27] Murota K (2003) Discrete Convex Analysis (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [28] Nace D, Orlin JB (2007) Lexicographically minimum and maximum load linear programming problems. Oper. Res. 55(1):182–187.Link, Google Scholar
• [29] Plaut B, Roughgarden T (2020) Almost envy-freeness with general valuations. SIAM J. Discrete Math. 34(2):1039–1068.Crossref, Google Scholar
• [30] Radzik T (2013) Fractional combinatorial optimization. Pardalos PM, Du DZ, Graham RL, eds. Handbook of Combinatorial Optimization, 2nd ed. (Springer Science+Business Media, New York), 1311–1355.Crossref, Google Scholar
• [31] Schrijver A (2003) Combinatorial Optimization—Polyhedra and Efficiency (Springer, Heidelberg).Google Scholar
• [32] Tardos É (1985) A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3):247–255.Crossref, Google Scholar
• [33] Végh LA (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