Steiner träd problemet är ett av de mest grundläggande NP-hårda problem: med tanke på en viktad oriktad graf och en delmängd av terminal noder, hitta en minimal kostnad träd spänner terminalerna. I en sekvens av papper förbättrades approximationsförhållandet för detta problem från 2 till den nuvarande bästa 1.55 [Robins,. Alla dessa algoritmer är helt kombinatoriska. Ett långvarigt öppet problem är om det finns en LP-avräkning för Steiner träd med integrality gap mindre än 2 [Vazirani,. I detta dokument förbättrar vi approximationsfaktorn för Steinerträdet och utvecklar en LP-baserad approximationsalgoritm. Vår algoritm bygger på en, till synes ny, iterativ randomiserad avrundningsteknik. Vi anser att en riktad komponent skära av avkoppling för k-begränsade Steiner träd problem. Vi provar en av dessa komponenter med sannolikhet proportionell mot värdet av den tillhörande variabeln i den optimala fraktionerade lösningen och kontrakterar den. Vi itererar denna process för ett lämpligt antal gånger och slutligen mata ut de provtagna komponenterna tillsammans med en minimal kostnad terminal spänner träd i den återstående grafen. Vår algoritm levererar en kostnadslösning på max ln(4) gånger kostnaden för ett optimalt k-begränsat Steinerträd. Detta innebär direkt en ln(4) + ε < 1,39 approximation för Steiner träd. Som en biprodukt av vår analys visar vi att integrality gapet i vår LP är som högst 1.55, vilket svarar på * Extended abstract.
Den bästa approximationsalgoritmen för allmänna metriska instanser beror på Byrka et al. REF och beräknar en lösning som kostar högst ln(4) +  på < 1,39 gånger så mycket som en LP-avslappning.
An improved LP-based approximation for steiner tree
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}