Approximation algorithms for Max Morse Matching

详细信息    查看全文

• 作者：Abhishek Rathod ; ^{abhishek@jcrathod.in} ; Talha Bin Masood ^{tbmasood@csa.iisc.ernet.in} ; Vijay Natarajan ^{vijayn@csa.iisc.ernet.in}
• 关键词：Discrete Morse theory ; Computational topology ; Approximation algorithms ; Homology computation
• 刊名：Computational Geometry
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：61
• 期：Complete
• 页码：1-23
• 全文大小：1723 K
• 卷排序：61

文摘

In this paper, we prove that the Max Morse Matching Problem is approximable, thus resolving an open problem posed by Joswig and Pfetsch [1]. For D  -dimensional simplicial complexes, we obtain a (D+1)(D2+D+1)-factor approximation ratio using a simple edge reorientation algorithm that removes cycles. For D≥5D≥5, we describe a 2D-factor approximation algorithm for simplicial manifolds by processing the simplices in increasing order of dimension. This algorithm leads to 12-factor approximation for 3-manifolds and 49-factor approximation for 4-manifolds. This algorithm may also be applied to non-manifolds resulting in a 1(D+1)-factor approximation ratio. One application of these algorithms is towards efficient homology computation of simplicial complexes. Experiments using a prototype implementation on several datasets indicate that the algorithm computes near optimal results.