Hardness results for homology localization

Chen C, Freedman D. 2011. Hardness results for homology localization. Discrete & Computational Geometry. 45(3), 425–448.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English

Scopus indexed
Author
Chen, ChaoISTA; Freedman, Daniel
Department
Abstract
We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius. For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that 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). The latter result leads to 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. As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius. Our work is restricted to homology over the ℤ2 field.
Publishing Year
Date Published
2011-01-14
Journal Title
Discrete & Computational Geometry
Publisher
Springer
Volume
45
Issue
3
Page
425 - 448
IST-REx-ID

Cite this

Chen C, Freedman D. Hardness results for homology localization. Discrete & Computational Geometry. 2011;45(3):425-448. doi:10.1007/s00454-010-9322-8
Chen, C., & Freedman, D. (2011). Hardness results for homology localization. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-010-9322-8
Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” Discrete & Computational Geometry. Springer, 2011. https://doi.org/10.1007/s00454-010-9322-8.
C. Chen and D. Freedman, “Hardness results for homology localization,” Discrete & Computational Geometry, vol. 45, no. 3. Springer, pp. 425–448, 2011.
Chen C, Freedman D. 2011. Hardness results for homology localization. Discrete & Computational Geometry. 45(3), 425–448.
Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” Discrete & Computational Geometry, vol. 45, no. 3, Springer, 2011, pp. 425–48, doi:10.1007/s00454-010-9322-8.
Material in ISTA:
Earlier Version

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar