Approximating k-forest with resource augmentation: A primal-dual approach

作     者：Angel, Eric Nguyen Kim Thang Singh, Shikha 

作者机构：Univ Evry Val Essonne IBISC Evry France Wellesley Coll Wellesley MA 02181 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2019年第788卷

页      面：12-20页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：ANR project OATA [ANR-15-CE40-0015-01] Chateaubriand Fellowship of the Office for Science & Technology of the Embassy of France in the United States National Science Foundation (NSF) [CNS 1408695, CCF 1553385, CCF 1439084, IIS 1247726, CU 1725543, CU 1716252, CU 1617618, CNS-1755615] 

主　　题：Primal-dual algorithms Resource augmentation k-forest problem Approximation algorithms LP duality algorithms Optimization problems Prize-collecting generalized Steiner tree problem 

摘      要：In this paper, we study the k-forest problem in the model of resource augmentation. In the k-forest problem, given an edge-weighted graph G (V, E), a parameter k, and a set of m demand pairs subset of V x V, the objective is to construct a minimum-cost subgraph that connects at least k demands. The problem is hard to approximate-the best-known approximation ratio is O(min{root vertical bar V vertical bar, root K}). Furthermore, k-forest is as hard to approximate as the notoriously-hard densest k-subgraph problem. While the k-forest problem is hard to approximate in the worst-case, we show that with the use of resource augmentation, we can efficiently approximate it up to a constant factor. First, we restate the problem in terms of the number of demands that are not connected. In particular, the objective of the k-forest problem can be viewed as to remove at most m - k demands and find a minimum-cost subgraph that connects the remaining demands. We use this perspective of the problem to explain the performance of our algorithm (in terms of the augmentation) in a more intuitive way. Specifically, we present a polynomial-time algorithm for the k-forest problem that, for every E 0, removes at most m - k demands and has cost no more than O(1/epsilon(2)) times the cost of an optimal algorithm that removes at most (1 - epsilon)(m - k) demands. (C) 2018 Elsevier B.V. All rights reserved.