Computational Optimization in Collaboration with Mexican Researchers

点击翻译按钮获取中文摘要

Efficient solution to optimization problems is of great interest and importance in practice and theory. Unfortunately, many important optimization problems turn out to be NP-hard, which implies that they do not have efficient solutions based on current computer techniques. However, this does not obviate the need for solving these problems. Approximation algorithms and heuristic algorithms for these optimization problems have been studied. Recent progress in computational optimization has greatly advanced the understanding of the approximability of optimization problems. In particular, recent study of the SATISFIABILITY problem (SAT) and the MAXIMUM SATISFIABILITY problem (MAXSAT) has played an important role in recent advances in computational optimization. Motivated by such an exciting progress in the area, Dr. Jianer Chen from the Department of Computer Science at Texas A&M University (TAMU) of the United States of America and Dr. Guillermo Morales-Luna from the Computer Science Section at the Mexican Research and Advanced Studies Center of National Polythecnic Insitute (CINVESTAV_IPN) of Mexico have formed a research team for performing the U.S.-Mexico collaborative research. The primary objectives of this collaboration are: to establish a long term cooperation among the theoretical computer science groups in the computer sciences departments of TAMU and CINVESTAV-IPN; to strengthen the graduate program in Computer Science in CINVESTAV-IPN, and to increase the international competence and accomplishments of the theoretical computer science research group at TAMU; to develop new techniques for designing better approximation algorithms and to develop new methods for analyzing existing approximation algorithms; and to develop a computational environment for testing and experimenting with approximation algorithms, in particular, approximation algorithms for MAXSAT, with special care to examine the efficiency and approximation factors of the tested algorithms .