Partial multicuts in trees

Asaf Levin, Danny Segev

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


Let T = (V, E) be an undirected tree, in which each edge is associated with a non-negative cost, and let { s1, t1 }, ..., { sk, tk } be a collection of k distinct pairs of vertices. Given a requirement parameter t ≤ k, the partial multicut on a tree problem asks to find a minimum cost set of edges whose removal from T disconnects at least t out of these k pairs. This problem generalizes the well-known multicut on a tree problem, in which we are required to disconnect all given pairs. The main contribution of this paper is an (frac(8, 3) + ε{lunate})-approximation algorithm for partial multicut on a tree, whose run time is strongly polynomial for any fixed ε{lunate} > 0. This result is achieved by introducing problem-specific insight to the general framework of using the Lagrangian relaxation technique in approximation algorithms. Our algorithm utilizes a heuristic for the closely related prize-collecting variant, in which we are not required to disconnect all pairs, but rather incur penalties for failing to do so. We provide a Lagrangian multiplier preserving algorithm for the latter problem, with an approximation factor of 2. Finally, we present a new 2-approximation algorithm for multicut on a tree, based on LP-rounding.

שפה מקוריתאנגלית אמריקאית
עמודים (מ-עד)384-395
מספר עמודים12
כתב עתTheoretical Computer Science
מספר גיליון1-3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 15 דצמ׳ 2006
פורסם באופן חיצוניכן

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700???


להלן מוצגים תחומי המחקר של הפרסום 'Partial multicuts in trees'. יחד הם יוצרים טביעת אצבע מחקרית ייחודית.

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