Approximating binary images from discrete X-rays

作     者：Gritzmann, P De Vries, S Wiegelmann, M 

作者机构：Tech Univ Munich Zentrum Math D-80290 Munich Germany 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：2000年第11卷第2期

页      面：522-546页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：discrete tomography set packing set covering set partitioning greedy algorithm matching approximation algorithm worst-case performance polynomial time 

摘      要：We study the problem of approximating binary images that are accessible only through few evaluations of their discrete X-ray transform, i.e., through their projections counted with multiplicity along some lines. This inverse discrete problem belongs to a class of generalized set partitioning problems and allows natural packing and covering relaxations. For these ( NP-hard) optimization problems we present various approximation algorithms and provide estimates for their worst-case performance. Further, we report on computational results for various variants of these algorithms. In particular, the corresponding integer programs are solved with only small absolute error for instances up to 250, 000 binary variables.