论文标题
具有凸成本的最低成本流量的近似参数计算
Approximate Parametric Computation of Minimum-Cost Flows with Convex Costs
论文作者
论文摘要
本文研究了具有凸成本函数的图表中最低成本流问题的变体，其中顶点的需求取决于一维参数$λ$。我们设计了两种算法方法，用于针对此问题的参数解决方案的近似计算。第一种方法通过插值边际成本函数将参数问题的实例转换为具有分段二次成本函数的实例。新实例可以通过我们在先前的工作中开发的算法准确求解。在第二种方法中，我们计算固定数量的非参数解，并插入所得的流量，从而为原始的参数问题提供了近似解决方案。对于这两种方法，我们都在相应的插值中使用的步骤大小制定明确的界限，以保证相对和绝对误差边距。最后，我们在一项实证研究中测试了现实世界中的交通和天然气实例的方法。
This paper studies a variant of the minimum-cost flow problem in a graph with convex cost function where the demands at the vertices are functions depending on a one-dimensional parameter $λ$. We devise two algorithmic approaches for the approximate computation of parametric solutions for this problem. The first approach transforms an instance of the parametric problem into an instance with piecewise quadratic cost functions by interpolating the marginal cost functions. The new instance can be solved exactly with an algorithm we developed in prior work. In the second approach, we compute a fixed number of non-parametric solutions and interpolate the resulting flows yielding an approximate solution for the original, parametric problem. For both methods we formulate explicit bounds on the step sizes used in the respective interpolations that guarantee relative and absolute error margins. Finally, we test our approaches on real-world traffic and gas instances in an empirical study.
