A randomized approximation algorithm for metric triangle packing
A randomized approximation algorithm for metric triangle packing
复制标题
度量三角形填充的随机逼近算法
DOI：
10.1007/s10878-020-00660-7
复制
发表时间：
2019-12
影响因子：
1
通讯作者：
Zhang An
中科院分区：
文献类型：
--
作者：
Chen Yong;Chen Zhi-Zhong;Lin Guohui;Wang Lusheng;Zhang An
给定一个在 3n 个顶点上的边加权完整图，最大权重三角形填充问题要求 G 中 n 个顶点不相交的三角形的集合，使得这三个三角形中边的总权重最大化。尽管该问题在文献中得到了广泛的研究，但令人惊讶的是，在这项工作之前，还没有针对其度量情况设计和分析非平凡的近似算法，其中输入图中的边权重满足三角不等式。在本文中，我们针对最大权重度量三角形填充问题设计了第一个非平凡多项式时间逼近算法。我们的算法是随机的，并且对于任何常数都能达到预期的近似比。
Given an edge-weighted complete graphGon 3nvertices, the maximum-weight triangle packing problem asks for a collection ofnvertex-disjoint triangles inGsuch that the total weight of edges in thesentriangles is maximized. Although the problem has been extensively studied in the literature, it is surprising that prior to this work, no nontrivial approximation algorithm had been designed and analyzed for its metric case, where the edge weights in the input graph satisfy the triangle inequality. In this paper, we design the first nontrivial polynomial-time approximation algorithm for the maximum-weight metric triangle packing problem. Our algorithm is randomized and achieves an expected approximation ratio offor any constant.
登录
查看更多内容
影响因子：
2.5
作者：
GABOW, HN
通讯作者：
GABOW, HN
DOI：
10.1109/focs.2013.61
发表时间：
2013-04
期刊：
2013 IEEE 54th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Marek Cygan
通讯作者：
Marek Cygan
DOI：
10.1016/0020-0190(91)90246-e
发表时间：
1991-01
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
V. Kann
通讯作者：
V. Kann
DOI：
10.1016/j.disc.2007.07.100
发表时间：
2008-04
期刊：
Discret. Math.
影响因子：
--
作者：
G. Manic;Yoshiko Wakabayashi
通讯作者：
G. Manic;Yoshiko Wakabayashi
DOI：
10.1016/j.dam.2013.03.001
发表时间：
2013-09
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
A. V. Zuylen
通讯作者：
A. V. Zuylen