En girig approximationsalgoritm baserad på spindelnedbrytningar" utvecklades av Klein och Ravi för nodviktade Steinerträd. Den här algoritmen ger ett värsta case approximationsförhållande på 2 ln k, där k är antalet terminaler. Den mest kända nedre gränsen på approximationsförhållandet är ln k, förutsatt att N P6 DTIME n Olog log n, genom en minskning från inställd täckning 9, 4. Vi visar att för det oviktade fallet kan vi få en approximationsfaktor för ln k. F eller det viktade fallet vi utvecklar en ny nedbrytning teorem, och generalisera begreppet spindlar" till gren-spindlar", som används för att utforma en ny algoritm med en värsta fall approximationsfaktor på 1:5 l n k. Denna algoritm, även polynom, är inte särskilt praktiskt på grund av sin höga körtid; eftersom vi behöver upprepade gånger nd många minimal vikt matchningar i varje iteration. Vi kan generalisera metoden för att ge en approximationsfaktor som närmar sig 1:35 lnk. W e också utveckla en enkel girig algoritm som är praktisk och har en värsta fall approximation faktor 1:6103 lnk. De tekniker som utvecklats för den andra algoritmen innebär en metod för att tillnärma node viktade nätverksdesign problem de ned av 0-1 korrekta funktioner. Dessa nya idéer leder också till förbättrade tillnärmningsgarantier för problemet med en miniminodviktad dominerande uppsättning. Den tidigare bästa approximationsgarantin för detta problem var 3 lnn 7. Genom en direkt tillämpning av de metoder som utvecklats i detta dokument kan vi utveckla en algoritm med en approximationsfaktor som närmar sig 1:35 ln n.
Genom att kombinera en viktad uppsättning täcker approximationsalgoritm och en nodeviktad Steiner träd approximationsalgoritm, uppnådde de approximationsförhållandet 3 ln n. I REF förbättrade de ytterligare approximeringsförhållandet till 1:35 ln n, vilket är det mest kända förhållandet.
Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets
{'venue': 'FSTTCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}