AF: Small: RUI:Applications and New Techniques for Exact Parameterized Computation

高效算法是计算机科学各个领域的基础。本项目将研究设计难组合问题的有效算法的新技术。将探讨这些难题的理论分析和实际实施之间的相互作用。此外，该项目将推进算法和系统的研究，在少数族裔服务的机构中，弱势学生将在基础前沿研究中获得宝贵的经验。更准确地说，该项目将研究一些经典和重要的NP-hard问题的新方法，设计精确和参数化算法的代数技术，以及精确和参数化算法的并行/分布式实现。第一部分致力于研究新测度对NP-hard问题（如布尔可满足性问题）算法设计的影响。第二部分的重点是扩展代数技术的力量，以解决那些涉及顶点删除的看似困难的问题。最后一部分是设计一种在并行/多核机器上实现结果算法的聪明方法。

Efficient algorithms are fundamental to various areas in computer science. This project will study new techniques for designing efficient algorithms for hard combinatorial problems. The interaction between theoretical analysis and practical implementations of such hard problems will be explored. Furthermore, this project will advance the study of algorithms and systems in a minority-serving institution where under-represented students will gain valuable experience in foundational cutting-edge research. More precisely, this project will investigate novel measures for some classical and important NP-hard problems, algebraic techniques for designing exact and parameterized algorithms, and parallel/distributed implementations of exact and parameterized algorithms. The first part is devoted to studying the effects of new measures on designing algorithms for well-known NP-hard problems such as the Boolean Satisfiability Problem. The second part is focused on expanding the power of algebraic techniques to those seemingly difficult problems involving vertex deletion. The last part is to devise a clever way to implement resulting algorithms on a parallel/multi-core machines.