Advanced Combinatorial Optimization


  • L. Aslanyan Institute for Informatics and Automation Problems of NAS RA


The research aims at constructing efficient algorithms and approximations for hard, open and novel combinatorial optimization problems with emphasis on the practical applicability of results. Boolean minimization (hard), Isoperimetry and tomography (open), decentralized and stream analysis (novel) algorithms are considered. Combinatorial reduction is another target, being related with two sets of problem instances, together with a structure of reduction. This triplet is studied to recover the tractability and approximation boundaries. The concept of optimality that is not yet clear for complex systems with conflicting goals is addressed in terms of heuristics, stability and equilibria. These issues play a key-role to the emergence of a major research pole in the area of combinatorial optimization, highly responsive to the industry needs and tightly linked to different research are as with design, analysis and management of complex systems. Applied areas addressed include Population Genomics and Wireless Sensor Networks.

Author Biography

L. Aslanyan, Institute for Informatics and Automation Problems of NAS RA

Laboratory of Discrete modelling, analysis and recognition


Garey, M.R. and Johnson, D.S. (1979). Computers and Intractibility: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York.

Crescenzi P., Kann V., Approximation on the web: A compendium of NP optimization problems, Randomization and Approximation Techniques in Computer Science, Lecture Notes in Computer Science, 1997, Volume 1269/1997, 111-118.

Papadimitriou C.H., Steiglitz K., Combinatorial optimisation: algorithms and complexity, Dover Publications Inc., 1998. New York, 498 p.

Korte B., Jens V., Combinatorial optimization: Theory and algorithms (21 Algorithms and Combinatorics), 4th Ed., Springer, 2008, 627 p.

Trevisan L., Sorkin G.B., Sudan M. and Williamson D.P., Gadgets, Approximation, and Linear Programming, SIAM Journal on Computing, Volume 29, Issue 6, 2074-2097 (2000).

Zhuravlev Yu., Elected Research Works, Magister, Moscow, 1998, 420 p.

Greenberg H., Hart W.E., Lancia G., Opportunities for combinatorial optimization in computational biology, INFORMS Journal on Computing 16, 221-231 (2004).

Arakelyan A., Boyajian A., Aslanyan L., Sahakyan H., Ivanova K., Mitov I., Growing support set systems in analysis of high-through put gene expression data, Classification, forecasting, Data Mining conference, Varna, 22-24 June, 2010.




How to Cite

Aslanyan, L. (2021). Advanced Combinatorial Optimization. Mathematical Problems of Computer Science, 38, 38–41. Retrieved from