Hardness results for homology localization

We address the problem of localizing homology classes, namely, findingthe cycle representing a given class with the most concise geometric measure. Westudy 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 isNP-hard to approximate even when the Betti number is O(1). The latter result leadsto the inapproximability of the problem of computing the nonbounding cycle withthe smallest volume and computing cycles representing a homology basis with theminimal total volume.As for the other two measures defined by pairwise geodesic distance, diameterand radius, we show that the localization problem is NP-hard for diameter but ispolynomial for radius.