Technical Reports
HPL-2009-374
Click here for full text:
Hardness Results for Homology Localization
Chen, Chao; Freedman, Daniel
HP Laboratories
HPL-2009-374
Keyword(s): algebraic topology, homology, localization
Abstract: We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We focus on the volume measure, that is, the 1-norm of a cycle. Two main results are presented. First, we prove the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). A side effect is the inapproximability of the problem of computing the nonbounding cycle with the smallest volume, and computing cycles representing a homology basis with the minimal total volume. We also discuss other geometric measures (diameter and radius) and show their disadvantages in homology localization. Our work is restricted to homology over the Z2 field.
11 Pages
Additional Publication Information: To be published and presented at ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA 2010.
External Posting Date: December 17, 2009 [Fulltext]. Approved for External Publication
Internal Posting Date: December 17, 2009 [Fulltext]