咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Integrality gap of the hypergr... 收藏

Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound

Steiner 树的 hypergraphic 松驰的完全差距: 1.55 上面的界限的一个短证明

作     者:Chakrabarty, Deeparnab Koenemann, Jochen Pritchard, David 

作者机构:Ecole Polytech Fed Lausanne CH-1015 Lausanne Switzerland Univ Penn Philadelphia PA 19104 USA Univ Waterloo Waterloo ON N2L 3G1 Canada 

出 版 物:《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期:2010年第38卷第6期

页      面:567-570页

核心收录:

学科分类:1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主  题:Hypergraph Integrality gap Randomized algorithm Steiner tree 

摘      要:Recently, Byrka, Grandoni, RothvoBand Sanita gave a 1.39 approximation for the Steiner tree problem, using a hypergraph-based linear programming relaxation. They also upper-bounded its integrality gap by 1.55. We describe a shorter proof of the same integrality gap bound, by applying some of their techniques to a randomized loss-contracting algorithm. (C) 2010 Elsevier B.V. All rights reserved.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分