Prize-collecting steiner network problems

Mohammadtaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, Zeev Nutov

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


In the Steiner Network problem, we are given a graph G with edge-costs and connectivity requirements ruv between node pairs u, v. The goal is to find a minimum-cost subgraph H of G that contains ruv edge-disjoint paths for all u, v ∈ V. In Prize-Collecting Steiner Network problems, we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when ruv ∈ {0, 1} is the classic Prize-Collecting Steiner Forest problem. In this article, we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone nondecreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed by Nagarajan et al. [2008]. We further generalize our results for element-connectivity and node-connectivity.

שפה מקוריתאנגלית
מספר המאמר2
כתב עתACM Transactions on Algorithms
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - דצמ׳ 2012

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Prize-collecting steiner network problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי