Computational Optimization in Collaboration with Mexican Researchers

与墨西哥研究人员合作的计算优化

• 批准号: 9613805
• 负责人: Jianer Chen
• 金额: $ 2.14万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-09-01 至 2000-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9613805&HistoricalAwards=false
• 关键词: Computational; Optimization; Collaboration; 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 .

优化问题的有效求解在理论和实践中都具有重要意义。 不幸的是，许多重要的优化问题都是NP难的，这意味着它们没有基于当前计算机技术的有效解决方案。 然而，这并不意味着需要解决这些问题。 研究了求解这些优化问题的近似算法和启发式算法。 计算优化的最新进展极大地促进了对优化问题的可逼近性的理解。 特别是，最近的研究满意度问题（SAT）和最大满意度问题（MAXSAT）在计算优化的最新进展中发挥了重要作用。 受到这一领域令人兴奋的进展的激励，美国德克萨斯农工大学计算机科学系的陈健尔博士和墨西哥国家理工学院墨西哥研究和高级研究中心的Guillermo Morales-Luna博士组成了一个研究小组，执行美国-墨西哥合作研究。 这次合作的主要目标是：在TAMU和CINVESTAV-IPN计算机科学系的理论计算机科学小组之间建立长期合作;加强CINVESTAV-IPN计算机科学研究生课程，并提高TAMU理论计算机科学研究小组的国际能力和成就;开发设计更好的近似算法的新技术，并开发分析现有近似算法的新方法;并开发用于测试和试验近似算法，特别是MAXSAT的近似算法的计算环境，特别注意检查测试算法的效率和近似因子。