LP-relaxations for tree augmentation

Guy Kortsarz, Zeev Nutov

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


In the TREE AUGMENTATION problem the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T∪F is 2-edge-connected. The best approximation ratio known for the problem is 1.5. In the more general WEIGHTED TREE AUGMENTATION problem, F should be of minimum weight. WEIGHTED TREE AUGMENTATION admits several 2-approximation algorithms w.r.t. the standard cut-LP relaxation. Improving this natural ratio is a major open problem, and resolving it may have implications on other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is an old open problem even for TREE AUGMENTATION. In this paper we introduce two different LP-relaxations, and for each of them give a simple combinatorial algorithm that computes a feasible solution for TREE AUGMENTATION of size at most 1.75 times the optimal LP value.

שפה מקוריתאנגלית
עמודים (מ-עד)94-105
מספר עמודים12
כתב עתDiscrete Applied Mathematics
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 20 אפר׳ 2018

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

Publisher Copyright:
© 2018 Elsevier B.V.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'LP-relaxations for tree augmentation'. יחד הם יוצרים טביעת אצבע ייחודית.

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