Riktade Steiner-problem är grundläggande problem i kombinationsoptimering och teoretisk datavetenskap. Ett viktigt problem i denna genre är k-kanten ansluten riktade Steiner träd (k-DST) problem. I detta problem, vi ges en riktad graf G på n hörn med kant-kostnader, en rot vertex r, en uppsättning av h terminaler T och ett heltal k. Målet är att hitta en min-kostnad subgraph H  på G som ansluter r till varje terminal T av k kant-di joint r, t-sökvägar. Detta problem inkluderar som specialfall den välkända riktade Steiner träd (DST) problem (fallet k = 1) och gruppen Steiner träd (GST) problem. Trots att de har studerats och nämnts många gånger i litteraturen, t.ex. av Feldman et al. [SODA'09, JCSS'12], av Cheriyan et al. [SODA'12, TALG'14] och av Laekhanukit [SODA'14] fanns det ingen känd icke-trivial approximationsalgoritm för k-DST för k ≥ 2 även i specialfallet att en ingångsgraf är riktad acykliskt och har ett konstant antal lager. Om en inmatningsgraf inte är acyklisk, är komplexitetsstatusen för k-DST inte ens känd för ett mycket strikt specialfall som k = 2 och  på T = 2. I detta dokument gör vi framsteg mot att utveckla en icke-trivial approximationsalgoritm för k-DST. Vi presenterar en O(D · k D‐1 · log n) - approximationsalgoritm för k-DST på riktade acykliska grafer (DAG) med D-lager, som kan utökas till ett specialfall av k-DST på "allmänna grafer" när en instans har en D-shallow optimal lösning, d.v.s., det finns k edge-dis joint r, t-patter, var och en av längder på de flesta D, för varje terminal t  på T. För fallet k = 1 (DST), vår algoritm ger en approximationsgrad av O(D log h), vilket innebär en O(log 3 h) - approximationsalgoritm för DST som körs i kvasi-polynom-tid (på grund av höjden-reduction av Zelikovsky [Algorithmica'97]). Vår algoritm är baserad på en LP-formulering som gör att vi kan bädda in en lösning till en träd-instance av GST, som inte bevarar anslutning. Vi visar dock att man slumpmässigt kan extrahera en lösning av k-DST från träd-intansen av GST. Vår algoritm är nästan tight när k, D är konstanter eftersom fallet att k = 1 och D = 3 är NP-hård att approximera till inom en faktor av O(log h), och vår algoritm arkiverar samma approximation förhållande för detta specialfall. Vi noterar också att k 1/4---hårdhet instans av k-DST är en DAG med 6 lager, och vår algoritm ger O(k 5 log n)-tillnärmning för detta specialfall. Följaktligen, som vår algoritm fungerar för allmänna grafer, får vi en O(D ·k D−1 · log n)-tillnärmning algoritm för en D-smallow instans av k kant-anslutna riktade Steiner subgraph problem, där vi vill ansluta varje par av terminaler genom k kant-sprickvägar.
I ett senare arbete presenterade Laekhanukit REF en LP-baserad O(k D−1 D log n)-tillnärmningsalgoritm för D-shallow fall av k-DST och k-DSS kör i tid n O(D).
Approximating Directed Steiner Problems via Tree Embedding
{'venue': 'ICALP 2016', 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Computer Science', 'Mathematics']}