Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing
复制标题
DOI：
10.48550/arxiv.2305.02987
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Elfarouk Harb;Kent Quanrud;C. Chekuri
中科院分区：
文献类型：
--
作者：
Elfarouk Harb;Kent Quanrud;C. Chekuri
Boob等人[1]描述了一种迭代剥离算法，称为Greedy++，用于解决Denmark子图问题（DSG），并证明它收敛于最优解。Chekuri，Quanrud和托雷斯[2]将该算法扩展到一般的超模密度问题（其中DSG是一个特例），并证明了所得到的算法Super-Greedy++（因此也是Greedy++）收敛。在本文中，我们重新审视了收敛性证明，并提供了一个不同的视角。这是通过一个连接到Fujishige的二次规划找到一个字典序最佳基地（contra）polymatroid [3]，和噪声版本的弗兰克-沃尔夫方法从凸优化[4，5]。这给了我们一个更简单的收敛性证明，也显示了一个更强的性质，即Super-Greedy++收敛到最优稠密分解向量，回答了Harb等人提出的问题。本文的第二个贡献是通过Frank-Wolfe算法来理解Thorup关于理想树包装和贪婪树包装[7，8]的工作，该算法用于在图形拟阵中找到字典序最优基础。这产生了一个更简单和透明的证明。这两个结果看似不同，但通过Fujishige的结果和凸优化是统一的。
Boob et al. [1] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Quanrud, and Torres [2] extended the algorithm to general supermodular density problems (of which DSG is a special case) and proved that the resulting algorithm Super-Greedy++ (and hence also Greedy++) converges. In this paper, we revisit the convergence proof and provide a different perspective. This is done via a connection to Fujishige's quadratic program for finding a lexicographically optimal base in a (contra)polymatroid [3], and a noisy version of the Frank-Wolfe method from convex optimisation [4,5]. This gives us a simpler convergence proof, and also shows a stronger property that Super-Greedy++ converges to the optimal dense decomposition vector, answering a question raised in Harb et al. [6]. A second contribution of the paper is to understand Thorup's work on ideal tree packing and greedy tree packing [7,8] via the Frank-Wolfe algorithm applied to find a lexicographically optimum base in the graphic matroid. This yields a simpler and transparent proof. The two results appear disparate but are unified via Fujishige's result and convex optimisation.