[Zurück]

C. Chen, D. Freedman:
"Hardness results for homology localization";
Discrete & Computational Geometry (eingeladen), 45 (2011), 3; S. 425 - 448.

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.