Computational Optimization in Collaboration with Mexican Researchers

优化问题的有效求解在实践和理论上都具有重要的意义。不幸的是，许多重要的优化问题被证明是NP-Hard的，这意味着它们没有基于现有计算机技术的有效解。然而，这并不排除解决这些问题的必要性。研究了这些优化问题的近似算法和启发式算法。计算最优化的最新进展极大地提高了对最优化问题可逼近性的理解。特别是，最近对可满足性问题(SAT)和最大可满足性问题(MAXSAT)的研究在计算优化的最新进展中发挥了重要作用。在这一令人振奋的进展的推动下，美国德克萨斯农工大学计算机科学系的陈建儿博士和墨西哥国家理工学院墨西哥研究和高级研究中心(CINVESTAVIPN)计算机科学部的吉列尔莫·莫拉莱斯-露娜博士组成了一个研究小组进行美墨合作研究。这一合作的主要目标是：在TAMU和CINVESTAV-IPN的计算机科学系的理论计算机科学小组之间建立长期的合作；加强CINVESTAV-IPN的计算机科学研究生课程，并提高TAMU理论计算机科学研究小组的国际能力和成就；开发设计更好的近似算法的新技术，并开发分析现有近似算法的新方法；开发用于测试和试验近似算法的计算环境，特别是MAXSAT的近似算法，特别注意检查被测试算法的效率和近似因子。

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 .