On Constrained Convexity Tomography and Lagrangean Approximations

Authors

  • L. Aslanyan Institute for Informatics and Automation Problems of NAS RA
  • H. Sahakyan Institute for Informatics and Automation Problems of NAS RA
  • A. Hovsepyan Institute for Informatics and Automation Problems of NAS RA

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

2021-12-10

How to Cite

Aslanyan, L. ., Sahakyan, H. ., & Hovsepyan, A. . (2021). On Constrained Convexity Tomography and Lagrangean Approximations. Mathematical Problems of Computer Science, 30, 111–122. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/423