Language
We detect your regional language is French. Do you want to change site's language to French? You may choose other languages.International
English
中文
русск
français
español
العربية
User Center
My Training Class
Feedback
Operations Research Letters | Vol.44, Issue.6 | | Pages 766-771
Refuting a conjecture of Goemans on bounded degree spanning trees
In 2006, Goemans presented an approximation algorithm for the minimum bounded degree spanning tree problem that constructs a tree with cost at most the optimal value of an LP relaxation but degree bound violations of up to two units per vertex. He conjectured that violations of at most one per vertex are attainable, providing a second conjecture that would make his approach achieve this guarantee. While the first conjecture was answered positively by Singh and Lau, we refute the second.
Original Text (This is the original text for your reference.)
Refuting a conjecture of Goemans on bounded degree spanning trees
In 2006, Goemans presented an approximation algorithm for the minimum bounded degree spanning tree problem that constructs a tree with cost at most the optimal value of an LP relaxation but degree bound violations of up to two units per vertex. He conjectured that violations of at most one per vertex are attainable, providing a second conjecture that would make his approach achieve this guarantee. While the first conjecture was answered positively by Singh and Lau, we refute the second.
+More
Translate engine
Article's language
Action
Report
Share
Recommended articles
Report
Select your report category*
Reason*
Your level privilege is in sufficient. You can go to the “User Center” to view your level information and perform points tasks to upgrade your level.
New sign-in location：
Last sign-in location：
Last sign-in date：
About to jump to an external site.
Security unknown, whether to continue