On the Tree Augmentation Problem

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


In the Tree Augmentation problem we are given a tree T= (V, F) and a set E⊆ V× V of edges with positive integer costs { ce: e∈ E}. The goal is to augment T by a minimum cost edge set J⊆ E such that T∪ J is 2-edge-connected. We obtain the following results.Recently, Adjiashvili [SODA 17] introduced a novel LP for the problem and used it to break the 2-approximation barrier for instances when the maximum cost M of an edge in E is bounded by a constant; his algorithm computes a 1.96418 + ϵ approximate solution in time n(M/ϵ2)O(1). Using a simpler LP, we achieve ratio 127+ϵ in time 2O(M/ϵ2)poly(n). This gives ratio better than 2 for logarithmic costs, and not only for constant costs.One of the oldest open questions for the problem is whether for unit costs (when M= 1) the standard LP-relaxation, so called Cut-LP, has integrality gap less than 2. We resolve this open question by proving that for unit costs the integrality gap of the Cut-LP is at most 28 / 15 = 2 - 2 / 15. In addition, we will prove that another natural LP-relaxation, that is much simpler than the ones in previous work, has integrality gap at most 7/4.

שפה מקוריתאנגלית
עמודים (מ-עד)553-575
מספר עמודים23
כתב עתAlgorithmica
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - פבר׳ 2021

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

Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On the Tree Augmentation Problem'. יחד הם יוצרים טביעת אצבע ייחודית.

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