Fair integral network flows. (English) Zbl 1540.90235
Summary: A strongly polynomial algorithm is developed for finding an integer-valued feasible \(st\)-flow of a 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.
MSC:
90C27 | Combinatorial optimization |
90C35 | Programming involving graphs or networks |
68R10 | Graph theory (including graph drawing) in computer science |