Variable Min-Cut Max-Flow Bounds and Algorithms in Finite Regime

Gitik, Rivka; Cohen, Alejandro

Permalink

https://hdl.handle.net/2142/130296 Copy

Description

Title

Variable Min-Cut Max-Flow Bounds and Algorithms in Finite Regime

Author(s)

• Gitik, Rivka
• Cohen, Alejandro

Issue Date

2025-09-17

Keyword(s)

• Variable min cut
• Variable max flow
• Variable minimum cut
• Variable maximum flow
• Uncertain min cut
• Uncertain max flow
• Finite regime
• Network coding

Abstract

The maximum achievable capacity from source to destination in a network is limited by the min-cut max-flow bound; this serves as a converse limit. In practice, link capacities often fluctuate due to dynamic network conditions. In this work, we introduce a novel analytical framework that leverages tools from computational geometry to analyze throughput in heterogeneous networks with variable link capacities in a finite regime. Within this model, we derive new performance bounds and demonstrate that increasing the number of links can reduce throughput variability by nearly 90%. We formally define a notion of network stability and show that an unstable graph can have an exponential number of different min-cut sets, up to O(2|E|). To address this complexity, we propose an algorithm that enforces stability with time complexity O(|E|2+|V|), and further suggest mitigating the delay-throughput tradeoff using adaptive rateless random linear network coding (AR-RLNC).

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130296&&

Copyright and License Information

Copyright 2025 is held by Rivka Gitik and Alejandro Cohen.

Owning Collections