# Algorithms and Complexity for the Almost Equal Maximum Flow Problem

Preprint · Rebekka Haese, Till Heller, Sven O. Krumke

- Archive id: arxiv:2104.05288
- Published: 2021-04-12
- Venue: Operations Research Proceedings 2019. Springer, Cham, 2020. 323-329
- arXiv: https://arxiv.org/abs/2104.05288
- Source URL: https://arxiv.org/abs/2104.05288
- PDF: https://arxiv.org/pdf/2104.05288
- Provenance: arxiv

## Abstract

In the Equal Maximum Flow Problem (EMFP), we aim for a maximum flow where we require the same flow value on all edges in some given subsets of the edge set. In this paper, we study the closely related Almost Equal Maximum Flow Problems (AEMFP) where the flow values on edges of one homologous edge set differ at most by the valuation of a so called deviation function~$Δ$. We prove that the integer almost equal maximum flow problem (integer AEMFP) is in general $\\mathcal{NP}$-complete, and show that even the problem of finding a fractional maximum flow in the case of convex deviation functions is also $\\mathcal{NP}$-complete. This is in contrast to the EMFP, which is polynomial time solvable in the fractional case. We provide inapproximability results for the integral AEMFP. For the integer AEMFP we state a polynomial algorithm for the constant deviation and concave case for a fixed number of homologous sets.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.