TR-2019-09

Discrete Decreasing Minimization, Part III: Network 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.


Bibtex entry:

@techreport{egres-19-09,
AUTHOR = {Frank, Andr{\'a}s and Murota, Kazuo},
TITLE = {Discrete Decreasing Minimization, Part III: Network Flows},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-09}
}


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