CAREER: Analytic and Algebraic Methods in Approximating Constraint Satisfaction Problems and Their Applications

About This Grant

Many problems in industries such as manufacturing, scheduling, and chip design require solving discrete optimization problems over a finite but large set of feasible solutions. This field of optimization relies on mathematical disciplines such as graph theory, algebra, and topology to design efficient algorithms. However, for many of these optimization problems, finding optimal (best) solutions is widely believed to be computationally infeasible. Approximation algorithms offer a practical approach by providing solutions that are guaranteed to be close to the optimum, measured by a predefined approximation ratio between the cost of the generated solution and the cost of the optimal solution. This project addresses key challenges in designing such algorithms, focusing on a fundamental type of problems in computer science called constraint satisfaction problems. As a part of the education plan, this project emphasizes educational outreach by fostering enthusiasm for mathematics among high school and undergraduate students, highlighting its connection to cutting-edge research and real-world applications. Additionally, by connecting research to education, the project prepares undergraduate and graduate students for careers in computational fields. The proposed research includes three main components: (1) developing a mathematical framework to characterize the approximation thresholds of satisfiable finite-domain Constraint Satisfaction Problems (CSPs), building on the foundational dichotomy theorem for CSPs; (2) advancing the understanding of Ordering Constraint Satisfaction Problems, a variant of CSPs, by leveraging their structural properties to design efficient approximation algorithms; and (3) applying the developed mathematical tools to address important problems in additive combinatorics and complexity theory. These efforts aim to enrich the theoretical understanding of optimization and computation by building on deep mathematical principles and exploring their connections to algorithm design. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.