Microsoft Word - Aslanyan1.doc


Îǵ»éÝ»ïÇϳÛÇ ¨ ѳßíáÕ³Ï³Ý ï»ËÝÇϳÛÇ Ù³Ã»Ù³ïÇÏ³Ï³Ý Ñ³ñó»ñ 30, 111--122, 2008. 

111 
 

 

ê³Ñٳݳ÷³Ï áõéáõóÇÏáõÃÛ³Ý ïáÙá·ñ³ýdz ¨ 
ɳ·ñ³ÝÅÛ³Ý Ùáï³ñÏáõÙÝ»ñÇ Ù³ëÇÝ 

 
ȨáÝ ²ëɳÝÛ³Ý, гëÙÇÏ ê³Ñ³ÏÛ³Ý,  ²ñïÛáÙ Ðáíë»÷Û³Ý 

 
ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï 

lasl@sci.am hasmik@ipia.sci.am artyom.hovsepyan@gmail.com 
 
 

²Ù÷á÷áõÙ 
 

êáõÛÝ Ñá¹í³ÍáõÙ ¹Çï³ñÏíáõÙ ¿ ¹ÇëÏñ»ï ïáÙá·ñ³ýdzÛÇ ÁݹѳÝáõñ 
¹³ëÇ ÙÇ Ù³ëݳíáñ ËݹÇñ, áñÇ ÉáõÍÙ³Ý Ñ³Ù³ñ ³é³ç³ñÏíáõÙ ¿ 
ȳ·ñ³ÝÅÛ³Ý é»É³ùë³ódzÛÇ íñ³ ÑÇÙÝí³Í ÙÇ Ùáï³íáñ Ù»Ãá¹ 
ѳٳå³ï³ëË³Ý Íñ³·ñ³ÛÇÝ Çñ³Ï³Ý³óٳٵ: 

 
 
 
 

¶ñ³Ï³ÝáõÃÛáõÝ 
 
1. R. J. Gardner, P. Gritzmann, D. Prangenberg, On the computational complexity of 
reconstructing lattice sets from their X-rays. Technical Report (970-05012), Techn. Univ. 
Munchen, fak. f. math, 1997. 
 
2. G. J. Woeginger. The reconstruction of polyominoes from their orthogonal projections. 
Inform. Process. Lett., 77, pp 225-229, 2001. 
 
3. E. Barcucci, A. Del Lungo, M. Nivat, and R. Pinzani. Reconstructing convex polyominoes 
from horizontal and vertical projections. Theoret. Comput. Sci., 155,  
pp.  321-347, 1996. 
 
4. G. Dahl and T. Flatberg. Lagrangian decomposition for reconstructing hv-convex (0, 1) 
matrices, Report 303, University of Oslo, pp. 1-13, 2002. 
 
5. M. Guignard and S. Kim. Lagrangian decomposition: a model yielding stronger lagrangian 
bounds. Math. Prog., 39, pp215-228, 1987. 
 
6. À. À. Ñààêÿí, Ãðàäèåíòíûå àëãîðèòìû ñèíòåçà (0,1)-ìàòðèö ñ ðàçëè÷íûìè 
ñòðîêàìè. ÄÀÍ Àðì ÑÑÐ, LXXXIII, 5, ñòð. 207-209. 1986. 
 
7. H. J. Ryser. Combinatorial properties of matrices of zeros and ones. Canad. J. Math., 9:pp 
371-377, 1957. 
 
8. D. Gale. A theorem on flows in networks. Pacific J. Math., 7, pp 1073-1082, 1957. 
 



112             ê³Ñٳݳ÷³Ï áõéáõóÇÏáõÃÛ³Ý ïáÙá·ñ³ýdz ¨ ɳ·ñ³ÝÅÛ³Ý Ùáï³ñÏáõÙÝ»ñÇ Ù³ëÇÝ 

 
 
 

On Constrained Convexity Tomography and Lagrangean Approximations 
 

L.  Aslanyan, H.  Sahakyan,  A. Hovsepyan 
 

 
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.