ONR-YIP: Applications of Algebraic Techniques in Algorithm Design
Abstract
BackgroundClassical algorithms for fundamental problems in the field of computing mostly employ "combinatorial" techniques. These can be considered as techniques tailored to the particular combinatorics of the problem at hand. Perhaps, the most famous examples are Ford-Fulkersons algorithm for the maximum fol w problem and the Chrisfides approximation algorithm for the traveling salesman problem (TSP). In the last decade algebraic techniques from several fields of mathematics revolutionized the field. Researchers managed to break long-standing barriers in the fields of approximation algorithms and fast graph algorithms. This includes new approximation algorithms for Traveling salesman problems, and unique games problems and faster algorithms for solving systems of linear equationsinvolving Laplacian matrices and faster maximum fol w algorithms.Proposed ResearchOur plan is to apply these algebraic techniques at other frontiers of the field of computing including counting problems, analysis of Markov chains, and resource allocation problems. Our starting point is the algebraic machinery that we developed for studying traveling salesman problems. Recently, we have managed to extend and exploit this machinery to design Markov chain Monte Carlo algorithms, and to design approximation algorithms for several market design problems. Our plan is to use our machinery to truly understand the computational complexity of the following problems:Counting Perfect MatchingsCounting the number of perfect matchings in a given graph G is one of the fundamental problems in the field of computing. For a bipartite graph G, the best efficient randomized algorithm gives a 1 + E approximation but the best deterministic algorithm only gives a 2n approximation. It is a widely open problem to get 1 + E approximation with deterministic algorithms. For general (nonbipartite) graphs, the situation is worse; we are not aware of even a Cn approximation algorithm.Mixed DiscreminantComputing the mixed discreminant of a set of PSD matrices is a linear algebraic generalization of counting perfect matchings in bipartite graphs. This problem is closely related to several fundamental problems in machine learning and theory of determinantal point processes as well as recent developments on TSP and the Kadison-Singer problem. To this date, we are not aware any approximation algorithm for this problem.Nash Welfare Maximization ProblemsNash welfare maximization objective is proved to be one of the ideal objective functions in resource allocationproblems. This is because it satisfies almost "envy-freeness" property. However, this objective seems very hard to optimize algorithmically. Recently, using our algebraic machinery we managed to get a hand on this objective. We plan to build on our insights and approach a number of market design and resource allocation problems that are based on this objective function.Naval RelevanceIn the last decade algebraic techniques are proved to be applicable to a variety of optimization problems. We expect that the machinery that comes out of thisproposal would widen this area. The resource allocation problems that we study here could be of particular interests to Naval use-cases. In particular, choosing the optimal location of supply bases for submarines and aircraft carriers is an optimization problem with an inherent fairness objective. The machinery that we are planning to develop for NashWelfare objective can be of particular interests for these tasks.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 05, 2017
- Source ID
- N000141712429
Entities
People
- Shayan Oveis Gharan
Organizations
- Office of Naval Research
- United States Navy
- University of Washington