Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems

Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
复制标题

锦标赛介数问题及相关排名问题的近似方案

DOI：
--
复制
发表时间：
2009
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
通讯作者：
W. Schudy
W. Schudy
中科院分区：
--
文献类型：
--
作者：
Marek Karpinski;W. Schudy

文献摘要

被引文献

相似文献

我们通过设计一个多项式时间近似方案（PTAS）确定了竞赛图中最小介数问题的近似性状况。之前并不知道有常数因子近似算法。我们还引入了一类更广义的所谓脆弱排序问题，并为它们构建了多项式时间近似方案。这些结果依赖于一种处理脆弱排序约束的新技术，并且可能具有独立的研究价值。
We settle the approximability status of the Minimum Betweenness problem in tournaments by designing a polynomial time approximation scheme (PTAS). No constant factor approximation was previously known. We also introduce a more general class of so-called fragile ranking problems and construct PTASs for them. The results depend on a new technique of dealing with fragile ranking constraints and could be of independent interest.