标题： 有限情形下的变量最小割最大流界及算法 显示英文标题

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

摘要： 网络中从源到目的的最大可实现容量受到最小割最大流界限的限制；这作为反向极限。 在实际中，由于动态网络条件，链路容量经常波动。 在本工作中，我们引入了一个新的分析框架，利用计算几何工具来分析有限情况下具有可变链路容量的异构网络的吞吐量。 在此模型中，我们推导出新的性能界限，并证明增加链路数量可以将吞吐量的波动减少近$90\%$。 我们正式定义了网络稳定性的概念，并表明不稳定的图可能有指数级的不同最小割集，最多达到$O(2^{|E|})$。 为了解决这种复杂性，我们提出了一种算法，其时间复杂度为$O(|E|^2 + |V|)$，并进一步建议使用自适应无速率随机线性网络编码（AR-RLNC）来缓解延迟与吞吐量之间的权衡。 显示英文摘要

摘要： 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).