Optimization Online


Min-Morse: Approximability & Applications

Abhishek Rathore (abhishek***at***jcrathod.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 min-Morse 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 min-partial order problem (min-POP)(a strict generalization of the min-feedback arc set problem (min-FAS)). The reduction involves introduction of rigid edges which are edges that demand strict inclusion in output solution. To solve min-POP, we use the Leighton- Rao divide-&-conquer paradigm that provides solutions to SDP-formulated instances of min-directed balanced cut with rigid edges (min-DBCRE). Our first algorithm for min-DBCRE extends Agarwal et al.ís rounding procedure for digraph formulation of ARV-algorithm to handle rigid edges. Our second algorithm to solve min-DBCRE 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 Morse-Witten 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 (Semi-definite Programming )

Category 3: Applications -- Science and Engineering (Other )


Download: [PDF]

Entry Submitted: 03/10/2015
Entry Accepted: 03/20/2015
Entry Last Modified: 04/19/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society