Sammanfattning I den klassiska (min-kostnad) Steiner träd problem, får vi en kant-viktad oriktad graf och en uppsättning av terminala noder. Målet är att beräkna ett minkostnadsträd S som spänner över alla terminaler. I den här artikeln tar vi hänsyn till min-power-versionen av problemet (även känt som min-power-versionen). Symmetrisk multicast), som är bättre lämpad för trådlösa applikationer. Här är målet att minimera den totala strömförbrukningen av noder, där kraften i en nod v är den maximala kostnaden för någon kant av S incident till v. Intuitivt, noder är antenner (en del av vilka är terminaler som vi behöver ansluta) och kant kostnader definiera kraften att ansluta sina slutpunkter via dubbelriktade länkar (så att stödja protokoll med ack meddelanden). Observera att vi inte kräver att kantkostnader återspeglar Euclidean avstånd mellan noder: på detta sätt kan vi modellera hinder, begränsad sändningskraft, icke-omniriktade antenner etc. Annorlunda från sin min-cost motsvarighet, min-power Steiner träd är NP-hård även i spanning träd fall (alias. symmetrisk konnektivitet), dvs. När alla noder är terminaler. Eftersom kraften i ett träd ligger inom en och två gånger dess kostnad, beräkna en ρst ≤ ln(4) + ε [Byrka et al.'10] ungefärlig minkostnad Steiner träd ger en 2ρst < 2,78 approximation för problemet. För min-power spanning träd samma metod ger en 2 approximation, som förbättrades till 5/3 + ε med en icke-trivial strategi i [Althaus et al.'06]. I detta papper presenterar vi en förbättrad approximation algoritm för min-power Steiner träd. Vårt resultat är baserat på två huvudingredienser. Vi presenterar den första nedbrytningsteorem för min-power Steiner träd, i anda av analoga strukturella resultat för min-kostnad Steiner träd och min-power spanning träd. Baserat på detta teorem definierar vi en riktig LP-avslappning, som vi utnyttjar inom den iterativa randomiserade avrundningsramen i [Byrka et al.'10]. En noggrann analys av minskningen av kraften i noderna vid varje iteration ger en 3 ln 4 − 9 4 + ε < 1,91 approximationsfaktor. Samma tillvägagångssätt ger en förbättrad 1,5 + ε approximation för min-power spanning träd också. Detta motsvarar approximationsfaktorn i [Nutov och Yaroshevitch'09] för specialfallet av min-power spanning träd med kantvikter i {0, 1}.
Den algoritm som presenteras i REF är för beräkning av ett minkostnadsträd S, som spänner över alla terminaler.
On Min-Power Steiner Tree
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}