Abstract-Vi studerar de prissamlande versionerna av Steinerträdet, resande säljare, och promenader (alias. PATH-TSP) problem (PCST, PCTSP, respektive PCS): ges en graf (V, E) med kostnader på varje kant och en straff (alias. pris) på varje nod, målet är att hitta ett träd (för PCST), cykel (för PCTSP), eller promenad (för PCS) som minimerar summan av kanten kostnader i trädet / cykeln/rulle och påföljderna för noderna inte spänns av det. Utöver att vara ett användbart teoretiskt verktyg för att hjälpa till att lösa andra optimeringsproblem, har PCST tillämpats fruktbart av AT&T för optimering av verkliga telekommunikationsnät. De senaste förbättringarna för de två första problemen, vilket ger en 2-ungefärlig algoritm för varje, dök först upp 1992. (En 2- approximation för PCS dök upp 2003.) Den naturliga linjära programmeringen (LP) avslappning av PCST har en integrerad lucka på 2, vilket har varit ett hinder för ytterligare förbättringar av detta problem. Vi presenterar (2 − ) - approximation algoritmer för alla tre problem, ansluten med en enhetlig teknik för att förbättra prisinsamling algoritmer som gör det möjligt för oss att kringgå integrality gap barriären.
Archer m.fl. REF tillhandahöll en (2 −  på) approximationsalgoritm för PCST-problemet.
Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
{'venue': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}