A 4 + ϵ approximation for k-connected subgraphs

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


We obtain approximation ratio [Formula presented] for the (undirected) k-CONNECTED SUBGRAPH problem, where [Formula presented] is the largest integer such that 2ℓ−1k2ℓ+1≤n. For large values of n this improves the ratio 6 of Cheriyan and Végh [4] when n≥k3 (the case ℓ=1). Our result implies an fpt-approximation ratio 4+ϵ that matches (up to the “+ϵ” term) the best known ratio 4 for k=6,7 for both the general and the easier augmentation versions of the problem. Similar results are shown for the problem of covering an arbitrary symmetric crossing supermodular biset function.

שפה מקוריתאנגלית
עמודים (מ-עד)64-75
מספר עמודים12
כתב עתJournal of Computer and System Sciences
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - פבר׳ 2022

הערה ביבליוגרפית

Publisher Copyright:
© 2021 Elsevier Inc.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A 4 + ϵ approximation for k-connected subgraphs'. יחד הם יוצרים טביעת אצבע ייחודית.

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