Abstrakt. Moss och Rabani [13] studie begränsade nodviktade Steiner trädproblem med två oberoende viktvärden förknippade med varje nod, nämligen kostnad och pris (eller straff). De ger en O(log n)-tillnärmning algoritm för den prissamlande nodviktade Steiner träd problem (PCST)-där målet är att minimera kostnaden för ett träd plus straffet för hörn som inte täcks av trädet. De använder algoritmen för PCST för att få en bicriteria (2, O(log n))- tillnärmning algoritm för den budgeterade nodviktade Steiner träd problem där målet är att maximera priset på ett träd med en given budget för sin kostnad. Deras lösning kan kosta upp till två gånger budgeten, men samlar in en faktor 1 log n ) av det optimala priset. Vi förbättrar dessa resultat från minst två aspekter. Vårt första huvudresultat är en primal-dual O(log h)-tillnärmning algoritm för ett mer allmänt problem, prissamlande nodviktade Steiner Forest (PCRS), där vi har h krav var och en begär anslutning av ett par hörn. Vår algoritm kan ses som en girig algoritm som minskar antalet krav genom att välja en struktur med minsta kostnads-till-minskning förhållande. Denna naturliga argumentation (används också av Klein och Ravi [11] och Guha et al. [9] ) leder till en mycket enklare algoritm än Moss och Rabani [13] för PCST. Vårt andra huvudsakliga bidrag är det budgeterade nodviktade Steiner-trädproblemet, som också är en förbättring för Moss och Rabani [13] och Guha et al. [9].................................................................. I det orotade fallet, vi förbättra på en O(log 2 n)-tillnärmning av [9], och presentera en O(log n)-tillnärmning algoritm utan budgetöverträdelse. För rotat fall, där en specificerad vertex måste visas i lösningen träd, vi förbättra bicriteria resultat [13] till en bicriteria approximation förhållande (1 +, O(log n) / 2 ) för alla positiva (eventuellt substant). Det vill säga, för varje tillåten budgetöverträdelse 1 +, Vi presenterar en algoritm som uppnår en kompromiss i garantin för pris. Vi visar faktiskt att detta är nästan tight för den naturliga linjär-programmering avkoppling som används av oss såväl som i [13].
Bateni, Hajiaghayi och Liaghat REF föreslog en O(log  på V)-tillnärmningsalgoritm för det prissamlande Steiner skogsproblemet och tillämpade den på det budgeterade Steiner träd problemet.
Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}