On the Tree Augmentation Problem
| Autor: | Zeev Nutov |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
000 Computer science knowledge general works General Computer Science Applied Mathematics Computer Science Applications Combinatorics Set (abstract data type) Tree (descriptive set theory) Computer Science - Data Structures and Algorithms Computer Science Theory of computation Data Structures and Algorithms (cs.DS) Enhanced Data Rates for GSM Evolution Mathematics Integer (computer science) |
| Zdroj: | Algorithmica. 83:553-575 |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/s00453-020-00765-9 |
| Popis: | In the Tree Augmentation problem we are given a tree T=(V,F) and a set E of edges with positive integer costs {c_e:e in E}. The goal is to augment T by a minimum cost edge set J subseteq E such that T cup 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+epsilon approximate solution in time n^{{(M/epsilon^2)}^{O(1)}}. Using a simpler LP, we achieve ratio 12/7+epsilon in time ^{O(M/epsilon^2)}. This also gives ratio better than 2 for logarithmic costs, and not only for constant costs. In addition, we will show that (for arbitrary costs) the problem admits ratio 3/2 for trees of diameter |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink