Gruppen Steiner träd problem är en generalisering av Steiner träd problem där vi ges flera undergrupper (grupper) av hörn i en viktad graf, och målet är att hitta en minsta vikt ansluten subgraph som innehåller minst en vertex från varje grupp. Problemet introducerades av Reich och Widmayer och lindar applikationer i VLSI design. Gruppen Steiner träd problem generaliserar uppsättningen täcker problemet, och är därför minst lika svårt. Vi ger en randomiserad O(log3 n log k) - approximation algoritm för gruppen Steiner träd problem på en n-node graf, där k är antalet grupper. Den bästa tidigare prestandagaranti var (1 +?)a (Bateman, Helvig, Robins och Zelikovsky). Med tanke på att gruppen Steiner problem modellerar också nätverksdesign problem med plats-teoretiska begränsningar studeras av Marathe, Bavi och Sundaram, våra resultat förbättrar också deras bicriteria approximation resultat. På samma sätt förbättrar vi tidigare resultat av Slavik på en turné version, kallas ärende schemaläggning problem. Vi använder resultatet av Bartal på probabilistisk approximation av finita metriska utrymmen enligt trädmått problem till en i ett träd metrisk. För att hitta en lösning på ett träd använder vi en generalisering av randomiserad avrundning. Vår approximation garanterar förbättring av O(log' nlog k) när det gäller grafer som utesluter små minderåriga genom att använda ett bättre alternativ till Bartal resultat på probabilistiska approximationer av mätvärden inducerade av sådana grafer (Konjevod, Ravi och Salman) -denna förbättring gäller för gruppen Steiner problem på plana grafer samt på en uppsättning punkter i 2D-Euclidean fallet. -1 Inledning.
För GST finns en polynom-tid algoritm av Garg et al. REF som uppnår en approximationsfaktor för O (log 2 k log n), där k är antalet grupper.
A polylogarithmic approximation algorithm for the group Steiner tree problem
{'venue': "SODA '98", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}