The matching augmentation problem: a 7/4-approximation algorithm

• 成果类型: Article
• 署名作者: Cheriyan, J.; Dippel, J.; Grandoni, F.; Khan, A.; Narayan, V. V.
• 署名单位: University of Waterloo; Universita della Svizzera Italiana; Indian Institute of Science (IISC) - Bangalore; McGill University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01394-z
• 发表日期: 2020
• 页码: 315-354
• 关键词: Approximation; subgraph

摘要

We present a 7/4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any givenMAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a 7/4 approximation algorithm for awell-structuredMAPinstance. The algorithm starts with amin-cost 2-edge cover and then applies ear-augmentation steps. We analyze the cost of the ear-augmentations using an approach similar to the one proposed by Vempala and Vetta for the (unweighted) min-size 2-ECSS problem (in: Jansen and Khuller (eds.) ApproximationAlgorithms forCombinatorialOptimization, Third InternationalWorkshop, APPROX2000, Proceedings, LNCS1913, pp.262-273, Springer, Berlin, 2000).