Prize-collecting Steiner network problems

Mohammad Taghi 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 paper 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 non-decreasing 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 in [SSW07]. We further generalize our results for element-connectivity and node-connectivity.

שפה מקוריתאנגלית
כותר פרסום המארחInteger Programming and Combinatorial Optimization - 14th International Conference, IPCO 2010, Proceedings
מוציא לאורSpringer Verlag
מספר עמודים14
מסת"ב (מודפס)3642130356, 9783642130359
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2010
אירוע14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010 - Lausanne, סין
משך הזמן: 9 יוני 201011 יוני 2010

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך6080 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס14th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2010

טביעת אצבע

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

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