Hardness of approximation for vertex-connectivity network design problems

Guy Kortsarz, Robert Krauthgamer, James R. Lee

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

תקציר

In the survivable network design problem (SNDP), the goal is to find a minimum-cost spanning subgraph satisfying certain connectivity requirements. We study the vertex-connectivity variant of SNDP in which the input specifies, for each pair of vertices, a required number of vertex-disjoint paths connecting them. We give the first strong lower bound on the approximability of SNDP, showing that the problem admits no efficient 2 log1-εn ratio approximation for any fixed ε > 0, unless NP ⊆ DTIME(n polylog(n)). We show hardness of approximation results for some important special cases of SNDP, and we exhibit the first lower bound on the approximability of the related classical NP-hard problem of augmenting the connectivity of a graph using edges from a given set.

שפה מקוריתאנגלית
עמודים (מ-עד)704-720
מספר עמודים17
כתב עתSIAM Journal on Computing
כרך33
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2004
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Hardness of approximation for vertex-connectivity network design problems'. יחד הם יוצרים טביעת אצבע ייחודית.

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