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.

Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.