标题： 最优同调问题的高效算法及其应用 显示英文标题

标题： Efficient algorithms for optimal homology problems and their applications

摘要： 多尺度单纯形平坦范数（MSFN）是一个d-循环的最优同调问题族，其由一个尺度参数{\lambda } >= 0 索引。每个实例（mSFN）优化一个同调d-循环和一个有界(d + 1)-链的总权重，其中其中一个组件被缩放为{\lambda }。我们提出了一种最小费用流公式，在 (d + 1) 维单纯复形嵌入在{R的d加1次方}中且同调为 Z 的情况下，可以在多项式时间内求解给定尺度{\lambda }的 mSFN 实例。此外，我们建立了 mSFN 的弱对偶性和强对偶性，以及互补松弛条件。另外，我们证明了在 Z+ 上的上同调下定向流公式的最优性条件。接下来，我们提出了一种基于多尺度平坦范数的方法，这是几何测度论领域中定义对象之间距离的概念，用于计算一对平面几何网络之间的距离。使用包含输入网络的域的三角剖分，可以通过求解线性规划来计算给定尺度下两个网络之间的平坦范数距离。此外，这种计算会自动识别捕获两个网络不同的二维区域（补丁）。我们通过二维示例展示了平坦范数距离可以比常用的 Hausdorff 距离更准确地捕捉输入的变化。作为一种稳定性概念，我们也推导了简单的一维曲线与其扰动版本之间的平坦范数距离的上界，作为扰动半径的函数，针对一类受限的扰动。我们在美国一个县的实际电力网络集上展示了我们的方法。我们的方法可以扩展到验证为多个基础设施（如交通、通信、供水和燃气网络）创建的合成网络。 显示英文摘要

摘要： The multiscale simplicial flat norm (MSFN) of a d-cycle is a family of optimal homology problems indexed by a scale parameter {\lambda} >= 0. Each instance (mSFN) optimizes the total weight of a homologous d-cycle and a bounded (d + 1)-chain, with one of the components being scaled by {\lambda}.We propose a min-cost flow formulation for solving instances of mSFN at a given scale {\lambda} in polynomial time in the case of (d + 1)-dimensional simplicial complexes embedded in {R^(d + 1)} and homology over Z. Furthermore, we establish the weak and strong dualities for mSFN, as well as the complementary slackness conditions. Additionally, we prove optimality conditions for directed flow formulations with cohomology over Z+. Next, we propose an approach based on the multiscale flat norm, a notion of distance between objects defined in the field of geometric measure theory, to compute the distance between a pair of planar geometric networks. Using a triangulation of the domain containing the input networks, the flat norm distance between two networks at a given scale can be computed by solving a linear program. In addition, this computation automatically identifies the 2D regions (patches) that capture where the two networks are different. We demonstrate through 2D examples that the flat norm distance can capture the variations of inputs more accurately than the commonly used Hausdorff distance. As a notion of stability, we also derive upper bounds on the flat norm distance between a simple 1D curve and its perturbed version as a function of the radius of perturbation for a restricted class of perturbations. We demonstrate our approach on a set of actual power networks from a county in the USA. Our approach can be extended to validate synthetic networks created for multiple infrastructures such as transportation, communication, water, and gas networks.