I problemet Directed Steiner Tree (DST) får vi en n-vertex riktad kantvägd graf, en rot r, och en samling av k terminal noder. Vårt mål är att hitta en minimal kostnad subgraph som innehåller en riktad väg från r till varje terminal. Vi presenterar en O (log 2 k/ log log k ) - approximation algoritm för DST som körs i kvasi-polynom-tid, dvs., i tid n poly log(k ). Genom att anta Projection Game Conjecture och NP 0 <ε <1 ZPTIME(2 n ε ), och justera parametrarna i hårdhetsresultatet av Halperin och Krauthgamer [STOC'03], visar vi den matchande nedre gränsen av  och (log 2 k/ log log k ) för klassen av kvasi- polynom- tid algoritmer, vilket innebär att vår approximation förhållande är asymptotiskt den bästa möjliga. Detta är den första förbättringen av DST problemet sedan den klassiska kvasi-polynom-tid O (log 3 k ) approximation algoritm av Charikar et al. [SODA'98 & J. Algorithms'99]. (I tidningen påstås felaktigt en O (log 2 k ) approximation på grund av ett misstag i tidigare arbete.) Vår strategi bygger på två huvudingredienser. För det första, vi härleder en approximation bevara minskning till gruppen Steiner Tree på träd med beroende Constraint (GSTTD) problem. Jämfört med den klassiska gruppen Steiner Tree on Trees problem, i GSTTD får vi dessutom en del beroende begränsningar bland noderna i utgångsträdet som måste vara nöjda. Den GSTTD instansen har kvasi-polynom storlek och logaritmisk höjd. Vi noterar däremot att Zelikovskijs heigh-reduction theorem [Algorithmica'97] som användes i allt tidigare arbete på DST uppnår en minskning till ett träd instans av den relaterade gruppen Steiner Tree (GST) problem av liknande höjd, men förlorar en logaritmisk faktor i approximation förhållandet. Vår andra ingrediens är en LP-avrundning algoritm för att ungefär lösa GSTTD instanser, som är inspirerad av det ramverk som utvecklats av [Rothvoß, Preprint'11; Friggstad et al., IPCO'14]. Vi anser att en Sherali-Adams lyft av en ordentlig LP-avslappning av GSTTD. Vår avrundningsalgoritm fortskrider nivå för nivå från roten till bladen, avrundning och konditionering varje gång på en korrekt delmängd av behörighet att göra digital
Nyligen visade REF att denna minskning kan förfinas för att bevisa att approximationen är 2 k/ log log k.
O(log2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm
{'venue': 'STOC 2019', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}