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 1,55 [Robins och Zelikovsky 2005]. Alla dessa algoritmer är helt kombinatoriska. Ett långvarigt öppet problem är om det finns en LP avkoppling av Steiner träd med integrality gap mindre än 2 [Rajagopalan och Vazirani 1999]. I den här artikeln presenterar vi en LP-baserad approximationsalgoritm för Steiner med en förbättrad approximationsfaktor. Vår algoritm bygger på en, till synes ny, iterativ randomiserad avrundningsteknik. Vi anser att en LP-avslappning av problemet, som bygger på begreppet riktade komponenter. Vi provar en komponent med sannolikhet proportionell mot värdet på den tillhörande variabeln i en fraktionerad lösning: den provtagna komponenten kontrakteras och LP uppdateras följaktligen. Vi itererar den här processen tills alla terminaler är anslutna. Vår algoritm levererar en kostnadslösning på max ln(4) + ε < 1,39 gånger kostnaden för ett optimalt Steinerträd. Algoritmen kan avrandomiseras med hjälp av metoden för begränsat oberoende. Som en biprodukt av vår analys visar vi att integrality gapet i vår LP är som högst 1.55, vilket besvarar den nämnda öppna frågan.
Byrka m.fl. REF förbättrade dessa resultat till en ln 4 + ε  på 1,39 approximation algoritm, som bygger på avrundning en starkare LP avkoppling för detta problem.
Steiner Tree Approximation via Iterative Randomized Rounding
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}