摘要：We study two optimization problems on simplicial complexes with homology over â"¤â,,, the minimum bounded chain problem: given a d-dimensional complex ð'¦ embedded in â"^(d+1) and a null-homologous (d-1)-cycle C in ð'¦, find the minimum d-chain with boundary C, and the minimum homologous chain problem: given a (d+1)-manifold â"³ and a d-chain D in â"³, find the minimum d-chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(â^S{log β_d})-approximation algorithm for the minimum bounded chain problem where β_d is the dth Betti number of ð'¦. Finally, we provide an O(â^S{log n_{d+1}})-approximation algorithm for the minimum homologous chain problem where n_{d+1} is the number of (d+1)-simplices in â"³.
