I Steiner Network problem, vi ges en graf G med kant-kostnader och anslutningskrav r uv mellan node par u, v. Målet är att hitta en minimikostnad subgraph H av G som innehåller r uv kant-diskoning vägar för alla u, v  på V. I Prize-Collecting Steiner Network problem, behöver vi inte uppfylla alla krav, men ges en strafffunktion för brott mot anslutningskraven, och målet är att hitta en subgraph H som minimerar kostnaden plus straffet. Fallet när r uv  ska {0, 1} är den klassiska Prize-Collecting Steiner Forest problem. I den här artikeln presenterar vi en ny linjär programmering avkoppling för problemet Prize-Collecting Steiner Network, och genom att avrunda den, få den första konstant-faktor approximation algoritm för submodulära och monotona icke minskande strafffunktioner. I synnerhet omfattar vår inställning alla-eller-ingenting strafffunktioner, som tar ut straff även om anslutningskravet är något kränkt; detta löser en öppen fråga som ställs av Nagarajan et al. Detta beslut riktar sig till Republiken Grekland. Vi generaliserar vidare våra resultat för element-konnektivitet och node-konnektivitet.
Priset som samlar Steiner-skogsproblem (PCSF) REF är en version av Steiner-skogsproblemet som gör det möjligt för bortkopplade källdestination par, genom att utdöma en straffavgift för bortkopplade par.
Prize-collecting steiner network problems
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}