论文标题
最大化网络平均收敛时间，但要删除边缘
Maximizing Convergence Time in Network Averaging Dynamics Subject to Edge Removal
论文作者
论文摘要
我们考虑了共识拦截问题（CIP），其中的目标是最大化共识的平均动力学的收敛时间，以消除有限数量的网络边缘。我们首先表明CIP可以作为有效的电阻拦截问题（ERIP），在该问题中，目标是删除有限数量的网络边缘，以最大程度地提高源节点和水槽节点之间的有效电阻。我们表明，即使对于具有固定源/水槽边缘的直径三分之三的两分图，ERIP也是强烈的，并且为CIP建立了相同的硬度结果。然后，我们表明，假设指数时间假设，ERIP和CIP不能近似于（几乎）多项式因子。随后，我们为ERIP设计了一个多项式$ MN $ -MN $ - APPRXIMATION算法，该算法仅取决于节点$ n $的数量$ n $和边缘$ m $的数量，但与边缘电阻的大小无关。最后，使用CIP的二次程序公式，我们设计了一种迭代近似算法，以找到CIP的一阶固定解决方案，并通过数值结果评估其良好性能。
We consider the consensus interdiction problem (CIP), in which the goal is to maximize the convergence time of consensus averaging dynamics subject to removing a limited number of network edges. We first show that CIP can be cast as an effective resistance interdiction problem (ERIP), in which the goal is to remove a limited number of network edges to maximize the effective resistance between a source node and a sink node. We show that ERIP is strongly NP-hard, even for bipartite graphs of diameter three with fixed source/sink edges, and establish the same hardness result for the CIP. We then show that both ERIP and CIP cannot be approximated up to a (nearly) polynomial factor assuming exponential time hypothesis. Subsequently, we devise a polynomial-time $mn$-approximation algorithm for the ERIP that only depends on the number of nodes $n$ and the number of edges $m$, but is independent of the size of edge resistances. Finally, using a quadratic program formulation for the CIP, we devise an iterative approximation algorithm to find a first-order stationary solution for the CIP and evaluate its good performance through numerical results.
