Vi tar itu med problemet med att lokalisera homologiklasser, nämligen att hitta cykeln som representerar en viss klass med det mest koncisa geometriska måttet. Vi fokuserar på volymmåttet, det vill säga 1-normen för en cykel. Två huvudsakliga resultat presenteras. För det första, vi bevisar att problemet är NP-hård att approximera inom någon konstant faktor. För det andra visar vi att för homologi av dimension två eller högre, problemet är NP-hård att approximera även när Batti talet är O(1). En bieffekt är omätbarheten av problemet med att beräkna den icke-gränsande cykeln med den minsta volymen, och datorcykler som representerar en homologi bas med den minsta totala volymen. Vi diskuterar också andra geometriska mått (diameter och radie) och visar deras nackdelar i homologi lokalisering. Vårt arbete är begränsat till homologi över Z2-fältet.
Chen och Freedman REF visade att lokaliseringsproblem är NP-hård till ungefärlig med fast förhållande över godtycklig dimension.
Hardness results for homology localization
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}