Fair Integral Network Flows

DOI10.1287/MOOR.2022.1303MaRDI QIDQ6121632zbMATH OpenFDO

Authors András Frank, Kazuo Murota

Publication date 27 February 2024

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.02673

zbMATH Keywords

lexicographic minimizationnetwork flowpolynomial algorithm

Mathematics Subject Classification ID

Graph theory (05Cxx) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Abstract: A strongly polynomial algorithm is developed for finding an integer-valued feasible $st$-flow of given flow-amount which is decreasingly minimal on a specified subset $F$ of edges in the sense that the largest flow-value on $F$ is as small as possible, within this, the second largest flow-value on $F$ is as small as possible, within this, the third largest flow-value on $F$ is as small as possible, and so on. A characterization of the set of these $st$-flows gives rise to an algorithm to compute a cheapest $F$-decreasingly minimal integer-valued feasible $st$-flow of given flow-amount. Decreasing minimality is a possible formal way to capture the intuitive notion of fairness.

Recommendations

• Fair integral submodular flows
• Fairness in routing and load balancing
• Upward max-min fairness
• Fast, Fair, and Efficient Flows in Networks
• scientific article; zbMATH DE number 4079141

Cited in

(3)

• Two proofs of a structural theorem of decreasing minimization on integrally convex sets
• Local density and its distributed approximation
• From theory to practice: engineering approximation algorithms for dynamic orientation

This page was built for publication: Fair Integral Network Flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6121632)