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
مستوى الصوت9
رقم الإصدار1
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - ديسمبر 2012

بصمة

أدرس بدقة موضوعات البحث “Prize-collecting steiner network problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا