Fair Integral Network Flows

• 成果类型: Article
• 署名作者: Frank, Andras; Murota, Kazuo
• 署名单位: Eotvos Lorand University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; Tokyo Metropolitan University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1303
• 发表日期: 2023
• 页码: 1393-1422
• 关键词: minimum; algorithm

摘要

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.