Refuting a conjecture of Goemans on bounded degree spanning trees

Autor:	Martin Nägele, Rico Zenklusen, Stephen R. Chestnut
Rok vydání:	2016
Předmět:	Discrete mathematics Vertex (graph theory) Spanning tree Degree (graph theory) Applied Mathematics Shortest-path tree 0102 computer and information sciences 02 engineering and technology Management Science and Operations Research Minimum spanning tree k-minimum spanning tree 01 natural sciences Industrial and Manufacturing Engineering Combinatorics 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Tree (set theory) Software MathematicsofComputing_DISCRETEMATHEMATICS Minimum degree spanning tree Mathematics
Zdroj:	Operations Research Letters. 44:766-771
ISSN:	0167-6377
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::33ca96d3482e8cb40ec0792b76a063c7 https://doi.org/10.1016/j.orl.2016.09.014 Zobrazit plný text záznamu Full Text from ScienceDirect