On Constrained Convexity Tomography and Lagrangean Approximations
Abstract
In this paper one particular problem of general type of discrete tomography problems is considered and an approximate algorithm for its solution based on Lagrangean relaxation is introduced. A program’s implementation is given as well.
References
R. J. Gardner, P. Gritzmann, D. Prangenberg, On the computational complexity ofreconstructing lattice sets from their X-rays. Technical Report (970-05012), Techn. Univ.Munchen, fak. f. math, 1997.
G. J. Woeginger. The reconstruction of polyominoes from their orthogonal projections.Inform. Process. Lett., 77, pp 225-229, 2001.
E. Barcucci, A. Del Lungo, M. Nivat, and R. Pinzani. Reconstructing convex polyominoesfrom horizontal and vertical projections. Theoret. Comput. Sci., 155,pp. 321-347, 1996.
G. Dahl and T. Flatberg. Lagrangian decomposition for reconstructing hv-convex (0, 1)matrices, Report 303, University of Oslo, pp. 1-13, 2002.
M. Guignard and S. Kim. Lagrangian decomposition: a model yielding stronger lagrangianbounds. Math. Prog., 39, pp215-228, 1987.
А. Саакян, Градиентные алгоритмы синтеза (0,1)-матриц с различнымистроками. ДАН Арм ССР, LXXXIII, 5, стр. 207-209. 1986.
H. J. Ryser. Combinatorial properties of matrices of zeros and ones. Canad. J. Math., 9:pp371-377, 1957.
D. Gale. A theorem on flows in networks. Pacific J. Math., 7, pp 1073-1082, 1957.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
