Abstract: A special quality of discrete tomography problem solutions that requires the ray difference is considered. Two classes of reconstruction tasks of (0,1)-matrices with different rows are studied: matrices with prescribed column and row sums and matrices with prescribed column sums only. Both cases are known as algorithmically open problems. We reformulate them as integer programming problems. Depending on parameters obtained, the Lagrangean relaxation model and then variable splitting technique, or a greedy heuristics approaches are applied for getting approximate solutions. In later case an optimization version is considered, where the objective is to maximize the number of pair-wise different row rays, which in case of existence of a matrix, is equivalent to the requirement of row differences.

Keywords: discrete tomography, (0,1)-matrices, integer programming

ACM Classification Keywords: F.2.2 Nonnumerical Algorithms and Problems: Computations on discrete structures

Link:

LINEAR PROGRAM FORM FOR RAY DIFFERENT DISCRETE TOMOGRAPHY

Hasmik Sahakyan, Levon Aslanyan

http://www.foibg.com/ijitk/ijitk-vol04/ijitk04-1-p04.pdf