Advanced Combinatorial Optimization
Abstract
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.
References
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.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
