| Popis: |
We obtain approximation ratio 4 + 2 l ≈ 4 + 4 lg k lg n − lg k for the (undirected) k -Connected Subgraph problem, where l = ⌊ lg n − lg k + 1 2 lg k + 1 ⌋ is the largest integer such that 2 l − 1 k 2 l + 1 ≤ n . For large values of n this improves the ratio 6 of Cheriyan and Vegh [4] when n ≥ k 3 (the case l = 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. |
Full Text from ScienceDirect