AF:SMALL:RUI:UNDERSTANDING THE GEOMETRY AND DIVERSITY OF SOLUTIONS - ALGORITHMS FOR GENERATING DIVERSE SOLUTIONS IN OPTIMIZATION

Classical optimization asks to select a best solution from a set of available solutions, according to some criteria. This project explores a new kind of optimization, where instead of returning one best solution, the goal is to return a set of many good solutions that are as different from each other as possible. The award will investigate the most important problems in computer science from this new angle.

The PI will lead a team to invent algorithms for these problems that return a maximally diverse (maximally dispersed) set of solutions within the solution space. The returned solutions will not only look different from each other, but each solution will also be good with respect to the original criteria. The ability to quickly generate diverse solutions has multiple potential benefits to society.

First, presenting a user with multiple solutions not only gives more choice, but it may also help discover criteria that the user was unaware of or found hard to formalize.

Second, a user gains the ability to quickly switch from one good solution to another good-but-very-different solution in case of an adversarial attack. Third, by dividing and scheduling tasks between different solutions, energy efficiency can be achieved by balancing loads in the systems deployed using these solutions. For many of the problems stated in the award, algorithms that return one solution are taught

in an undergraduate algorithms course. The diverse solutions variants of these problems are also natural to motivate in the classroom, particularly for geometric problems where one can visually gauge the diversity. The investigator plans to include simple algorithms for the diverse variants, and design coding projects based on them. The investigator is committed to producing the next generation of researchers and will engage undergraduate and graduate students in this project.

This project is aimed towards developing an algorithmic, technique-focused study of the task of generating diverse solutions in optimization. The user specifies the optimization problem P, an approximation factor c specifying the desired quality of the solutions, and an integer s denoting the number of solutions required. The goal of the algorithm is to quickly generate s solutions to P, each of which is c-approximately optimal, and such that this collection of s solutions is as diverse as possible.

Diversity will be measured as either the average distance, or the minimum distance between all pairs of the returned s solutions. The investigator plans a study of three fundamental problems in computer science, for which classical algorithms (those that return one solution) span a wide variety of techniques. The three problems are Task A) Satisfiability of k-CNF formulae (SAT), Task B) Graph Problems such as minimum spanning tree (MST) and traveling salesman problem (TSP), and Task C) Geometric Problems such as triangulations, and independent sets, vertex covers and dominating sets in planar and unit-disk graphs.

The main goals of this research are to develop polynomial time bi-approximation algorithms that explore the quality-diversity tradeoff, and to develop a (partial)

classification of techniques that can be used to generate diverse solutions to different problems. In terms of theoretical advancements, generating diverse solutions requires a better understanding of the geometric landscape of the space of good solutions, in particular understanding quantities like diameter, dispersed sets, expected distances, and other interesting quantities.

The simple case of two most diverse solutions corresponds to the diameter of the space of solutions, that has been studied (albeit only qualitatively) for SAT solutions, triangulations, and the matching polytope. This award extends this qualitative study, making it algorithmic, and extending to

beyond two solutions. The three classes of problems in this award have classical algorithms that span a wide variety of techniques such as randomized local search, dynamic programming, greedy algorithms and linear and semidefinite programming. The study of diverse versions of these problems will enable the new style of optimization to be applied to problems with inherently different structures. For Task A, given the

historical importance of SAT in the field of computer science and the plethora of known reductions from SAT to other problems, any results on computing diverse solutions to SAT have the potential to be applied to many other NP-complete problems. Tasks B and C will help identify similarities and differences in techniques for solving diverse versions of combinatorial problems from those for solving geometric problems.

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.