I den klassiska Steiner träd problem, med tanke på en oriktad, ansluten graf G = (V, E) med icke-negativa kant kostnader och en uppsättning terminalerT  på V, är målet att hitta en minimikostnad träd E. E som spänner terminalerna. Problemet är APX-hård; den mest kända approximationsalgoritmen har ett förhållande på ρ = ln(4) + ε < 1.39. I denna artikel studerar vi en naturlig generalisering, det multi-nivå Steiner träd (MLST) problem: Med tanke på en häckad sekvens av terminalerT · · · · · T 1  på V, beräkna häckade träd E. · · · · E 1  på E som spänner över motsvarande terminal uppsättningar med minsta totala kostnad. MLST-problemet och varianter av detta har studerats under olika namn, inklusive flernivånätverksdesign, tjänstekvalitetsmulticast träd, Grad-of-Service Steiner träd, och Multi-tier träd. Flera approximativa resultat är kända. Vi presenterar först två enkla O ( ) - approximation heuristiker. Baserat på dessa, introducerar vi en rudimentär sammansatt algoritm som generaliserar ovanstående heuristik, och bestämma dess approximation förhållande genom att lösa ett linjärt program. Vi presenterar sedan en metod som garanterar samma approximationsförhållande med hjälp av högst 2 Steiner trädberäkningar. Vi jämför dessa heuristiker experimentellt på olika fall av upp till 500 hörn med hjälp av tre olika nätverksgenerationsmodeller. Vi presenterar också flera heltal linjära programmering formuleringar för MLST problem och jämföra deras körtider på dessa fall. Enligt vår kunskap uppnår den sammansatta algoritmen det bästa approximationsförhållandet för upp till = 100 nivåer, vilket är tillräckligt för de flesta applikationer, såsom nätverksvisualisering eller utformning av infrastruktur på flera nivåer. Låt G = (V, E) vara en oriktad, ansluten graf med positiva kant kostnader c : E → R +, och låt T  på V vara en uppsättning hörn som kallas terminaler. Ett Steiner träd är ett träd i G som spänner över T. Nätverket (graf) Steiner träd problem (ST) är att hitta en minimal kostnad Steiner träd E E, där kostnaden för E är c (E ) = e E c (e). ST är ett av Karps initiala NP-hårda problem [13]; se även en undersökning [22], en online kompendium [12], och en lärobok [19]. På grund av dess praktiska betydelse på många områden finns det en lång historia av exakta och approximativa algoritmer för problemet. Den klassiska 2- approximationsalgoritmen för ST [11] använder den metriska stängningen av G, d.v.s. den kompletta kantviktade grafen G * med vertex-uppsättningen T där kostnaden för uv för varje kant motsvarar längden på en kortaste u-v-bana i G. Ett minsta spännträd på G * motsvarar ett 2-ungefärligt Steiner-träd i G. För närvarande är den sista i en lång lista över förbättringar den LP-baserade approximationsalgoritmen för Byrka et al. [6], som har ett förhållande på ln(4) + ε < 1,39. Deras algoritm använder en ny iterativ randomiserad avrundningsteknik. Observera att ST är APX-hård [4]; mer konkret är det NP-hårdt att approximera problemet inom en faktor på 96/95 [8]. Detta är i motsats till den geometriska varianten av problemet, där terminaler motsvarar punkter i Euclidean eller rektilinear planet. Båda varianterna tillåter polynom-tids approximation system (PTAS) [1, 16], medan detta inte gäller för det allmänna metriska fallet [4]. I denna artikel, vi anser den naturliga generaliseringen av ST där terminalerna visas på "nivåer" (eller "grad av tjänst") och måste anslutas med kanter av lämpliga nivåer. Vi föreslår nya approximationsalgoritmer och jämför dem med befintliga både teoretiskt och experimentellt. Definition 1.1 (Multi-level Steiner Tree (MLST) Problem). Med tanke på en ansluten, oriktad graf G = (V, E) med kantvikter c : E → R + och inbäddade terminaluppsättningar T  på · · · T 1 V, består ett flernivås Steinerträd av inbäddade kantuppsättningar E. · · · · E 1  på ett sådant sätt att E i spänner T i för alla 1 ≤ i ≤. Kostnaden för en MLST definieras av summan av kantvikterna över alla nivåer, i=1 c (E i ) = i=1 e  och E i c (e). MLST-problemet är att hitta en MLST E OPT,  ska · · · · E OPT,1 E med lägsta kostnad. Ovanstående LP har + 1 variabler och 2 −1 + 2 begränsningar. Varje delmängd Q  till {1, 2,.., } med 1  på Q motsvarar en begränsning. Lemma 2.6. Systemet med 2 – 1 ojämlikheter kan uttryckas i matrisform som t · 1 2 – 1 × 1 ≤ M y,
Dessa tillvägagångssätt är (+1 2 )ρ- och ρ- approximationer, respektive REF.
Multi-level Steiner Trees
{'venue': 'JEAL', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}