Polyhedral Frameworks for Approximation Algorithms

Emory University, Atlanta GA

Investigators

Abstract

Linear programming (LP) and polyhedral formulations have earned an unparalleled reputation in the last 60 years as a unifying framework for both practically and theoretically attacking discrete optimization problems, ranging from resource allocation and scheduling to routing and VLSI design. From a theoretical perspective they are the basis of most known approaches to constructing generic approximation algorithms for NP-hard problems. Despite LP's distinguished status, the PI feels that the full impact of polyhedral techniques on computer science has yet to be realized. The PI aims to address this gap by (1) developing frameworks for designing approximation algorithms that better leverage the structure that polyhedral formulations provide, and, as an ambitious long term goal, (2) developing a complexity theory based on polyhedral formulation size. In particular, the PI proposes an iterated packing technique for rounding packing problems that enjoys many of the benefits that the elegant and powerful iterated rounding method offers for covering problems: iterated packing is conceptually simple, and large fractional components facilitate rounding. One may view LP as a bona fide model of computation, with formulation size as a measure of complexity. This perspective has the potential of inducing different types of separations than traditional complexity measures; for example, although matching is a fundamental problem in P, there is no polynomial-sized polyhedral formulation known for it. The PI also seeks to unearth connections between traditional and polyhedral complexity. For any discrete optimization problem, the PI suggests a canonical decision problem and conjectures that the optimization problem is solvable in polynomial time if and only if the associated decision problem is in NC^1. A broader goal of this inherently interdisciplinary research is to forge deeper connections between the operations research and theoretical computer science communities: LP is a foundational component of the former, and the PI seeks to elevate the status of LP beyond that of just a tool in the latter. The PI will attempt to engage collaborators from both communities, and the research conducted will be disseminated in venues visible to both communities.