  


MinMorse: Approximability & Applications
Abhishek Rathore (abhishekjcrathod.in) Abstract: In this work, we resolve an open problem posed by Joswig et al. [49] by providing an O~(N) time, O(log2(N)) factor approximation algorithm for the minMorse unmatched problem (MMUP) Let M be the no. of critical cells of the optimal discrete Morse function and N be the total no. of cells of a regular cell complex K. The goal of MMUP is to find M for a given K. To begin with, we apply an approx. preserving graph reduction procedure on MMUP to obtain a new problem namely the minpartial order problem (minPOP)(a strict generalization of the minfeedback arc set problem (minFAS)). The reduction involves introduction of rigid edges which are edges that demand strict inclusion in output solution. To solve minPOP, we use the Leighton Rao divide&conquer paradigm that provides solutions to SDPformulated instances of mindirected balanced cut with rigid edges (minDBCRE). Our first algorithm for minDBCRE extends Agarwal et al.’s rounding procedure for digraph formulation of ARValgorithm to handle rigid edges. Our second algorithm to solve minDBCRE SDP, adapts Arora et al.’s primal dual MWUM. In terms of applications, under the mild assumption1 of the size of topological features being significantly smaller compared to the size of the complex, we obtain an (a) O~(N ) algorithm for computing homology groups Hi(K,A) of a simplicial complex K, (where A is an arbitrary abelian group.) (b) an O~(N^2) algorithm for computing persistent homology and (c) an O~(N ) algorithm for computing the optimal discrete MorseWitten function compatible with input scalar function as simple consequences of our approximation algorithm for MMUP thereby giving us the best known complexity bounds for each of these applications under the aforementioned assumption. Such an assumption is realistic in applied settings, and often a characteristic of modern massive datasets. Also, for the scalar field topology application, we discuss why the prescribed conditions for compatibility are natural, rigorous and general. Keywords: Computational Topology, Discrete Morse Theory, Approximation Algorithms, Homology Computation, Persistent Homology, Scalar Field Topology Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 3: Applications  Science and Engineering (Other ) Citation: Download: [PDF] Entry Submitted: 03/10/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  