--- _id: '10909' abstract: - lang: eng text: 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 ℤ2 field. acknowledgement: Partially supported by the Austrian Science Fund under grantFSP-S9103-N04 and P20134-N13. article_processing_charge: No author: - first_name: Chao full_name: Chen, Chao id: 3E92416E-F248-11E8-B48F-1D18A9856A87 last_name: Chen - first_name: Daniel full_name: Freedman, Daniel last_name: Freedman citation: ama: 'Chen C, Freedman D. Hardness results for homology localization. In: Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2010:1594-1604. doi:10.1137/1.9781611973075.129' apa: 'Chen, C., & Freedman, D. (2010). Hardness results for homology localization. In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1594–1604). Austin, TX, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973075.129' chicago: Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, 1594–1604. Society for Industrial and Applied Mathematics, 2010. https://doi.org/10.1137/1.9781611973075.129. ieee: C. Chen and D. Freedman, “Hardness results for homology localization,” in Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, United States, 2010, pp. 1594–1604. ista: 'Chen C, Freedman D. 2010. Hardness results for homology localization. Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1594–1604.' mla: Chen, Chao, and Daniel Freedman. “Hardness Results for Homology Localization.” Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2010, pp. 1594–604, doi:10.1137/1.9781611973075.129. short: C. Chen, D. Freedman, in:, Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2010, pp. 1594–1604. conference: end_date: 2010-01-19 location: Austin, TX, United States name: 'SODA: Symposium on Discrete Algorithms' start_date: 2010-01-17 date_created: 2022-03-21T08:24:07Z date_published: 2010-02-01T00:00:00Z date_updated: 2023-02-23T11:19:46Z day: '01' department: - _id: HeEd doi: 10.1137/1.9781611973075.129 language: - iso: eng month: '02' oa_version: None page: 1594-1604 publication: Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms publication_identifier: eisbn: - '9781611973075' publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' related_material: record: - id: '3267' relation: later_version status: public scopus_import: '1' status: public title: Hardness results for homology localization type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2010' ...