Steiners trädproblem är ett klassiskt NP-hårdt optimeringsproblem med ett brett utbud av praktiska tillämpningar. I ett fall av detta problem, vi ges en oriktad graf G = (V, E), en uppsättning terminaler R  på V, och icke-negativa kostnader c e för alla kanter e E. Alla träd som innehåller alla terminaler kallas en Steiner träd; målet är att hitta en minimikostnad Steiner träd. Noderna V \R kallas Steiner noder. Den bästa approximationsalgoritmen känd för Steiner trädproblem beror på Robins och Zelikovsky (SIAM J. Discrete Math, 2005); deras giriga algoritm uppnår en prestandagaranti på 1 + ln 3 2  och 1,55. Den mest kända linjära programmering (LP)-baserade algoritmen, å andra sidan, beror på Goemans och Bertsimas (Math. Programmering, 1993) och uppnår en approximationsgrad på 2 − 2/ på R. I detta dokument etablerar vi en länk mellan giriga och LP-baserade metoder genom att visa att Robins och Zelikovskijs algoritm har en naturlig primal-dual tolkning med avseende på en ny partition-baserad linjär programmeringsavkoppling. Vi har också överraskande kopplingar mellan den nya formuleringen och befintliga LP och vi visar att den nya LP är starkare än den bidirected cut-formuleringen. En instans är b-quasi-bipartite om varje ansluten komponent i G\R har som mest b hörn. Vi visar att Robins och Zelikovsky algoritm har ett approximationsförhållande bättre än 1 + ln 3 2 för sådana fall, och vi bevisar att integrality gapet i vår LP är mellan 8 7 och 2b+1 b+1.
Könemann, Pritchard och Tan REF visade att för en annan LP formulering, som är starkare än BCR, är integrality gapet övre gräns
A Partition-Based Relaxation For Steiner Trees
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}