I den här artikeln studerar vi den prissamlande versionen av problemet med det generaliserade Steinerträdet. Såvitt vi vet finns det ingen generell kombinatorisk teknik i approximationsalgoritmer som utvecklats för att studera de prissamlande versionerna av olika problem. Dessa problem studeras från fall till fall av Bienstock et al. [5] Genom att tillämpa en LP-avrundningsteknik som inte är en kombinatorisk metod. Det viktigaste bidraget i detta dokument är att införa en allmän kombinatorisk strategi för att lösa dessa problem genom ett nytt primal-dual schema (utan behov av att lösa en LP). Vi kopplar ihop det ursprungliga schemat med Farkas lemma för att få en kombinatoriell 3-approximeringsalgoritm för problemet med PrizeCollecting Generalized Steiner Tree. Vårt arbete inspirerar också en kombinatorisk algoritm [19] för att lösa ett specialfall av Kellys problem [22] av priskanter. Vi anser också att problemet med k-skog, en generalisering av k-MST och k-Steiner träd, och vi visar att trots dessa problem för vilka det finns konstant faktor approximation algoritmer, är k-skog problemet mycket svårare att approximera. Särskilt för att uppnå en approximationsfaktor som är bättre än O(n 1/6−ε ) för kskog krävs betydligt nya idéer, bland annat en förbättring av approximationsfaktorn O(n 1/3−ε ) för det ökända tätaste k-subgrafproblemet. Vi noterar att k-skog och prissamlande version av Generalized Steiner Tree är nära relaterade till varandra, eftersom den senare är Lagrangian avkoppling av den förra.
Dessutom är approximabiliteten av dessa två versioner av tät-k-subgraf polynomiskt relaterade REF.
The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
{'venue': "SODA '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}