---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Chao
foaf_name: Chen, Chao
foaf_surname: Chen
foaf_workInfoHomepage: http://www.librecat.org/personId=3E92416E-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Daniel
foaf_name: Freedman, Daniel
foaf_surname: Freedman
bibo_doi: 10.1007/s00454-010-9322-8
bibo_issue: '3'
bibo_volume: 45
dct_date: 2011^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Hardness results for homology localization@
...