TR-2020-16

Fair Integral Flows

András Frank, Kazuo Murota



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.


Bibtex entry:

@techreport{egres-20-16,
AUTHOR = {Frank, Andr{\'a}s and Murota, Kazuo},
TITLE = {Fair Integral Flows},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2020},
NUMBER = {TR-2020-16}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!