CAREER: Overcoming limitations to approximating combinatorial optimization problems

University Of Colorado At Boulder, Boulder CO

Investigators

Abstract

This proposal seeks to develop a comprehensive understanding of the limitations of approximation algorithms for combinatorial optimization problems. Combinatorial optimization problems are of great importance to various areas such as operations research, machine learning, VLSI design, computational biology and statistical physics. The task of finding algorithms for combinatorial optimization problems arise in countless applications, from billion-dollar operations to everyday computing tasks. Many optimization problems are NP-hard and thus cannot be solved exactly in polynomial time unless P=NP. However, the majority of such problems are key elements to practical applications where often, if the optimal solution is hard to find, producing an approximate solution suffices. The research proposed will study the limitations of approximation algorithms posed by the Unique Games Conjecture and the limitations posed by the presence of unlikely worst-case instances. The PI aims to design a methodology to partially or fully overcome such limitations by addressing both of those factors. The proposal outlines a challenging plan focusing on research in a broad cross-section of spectral graph theory, convex optimization, multi-commodity flows, and harmonic analysis. The contributions of the work described in this proposal will have great impact on the theory of approximability as well as real world problems for which efficient, exact algorithms will be provided for semi-random instances and will naturally result in collaborations between researchers across many different fields such as mathematics, theory of computer science, industrial engineering, operations research and networking.