CRII: AF: On Designing Approximation Algorithms Based on Round-or-Cut Paradigm

Numerous discrete optimization problems arising in practice are intractable; the approximation algorithms framework provides efficient algorithms for these optimization problems with provable guarantees on the quality of solutions. Among many others, the linear programming (LP) technique has played a central role in the area of approximation algorithms. This project seeks to understand the power of this technique, by exploiting a very flexible paradigm in designing LP-based algorithms, called the "round-or-cut" paradigm. The PI aims to use this paradigm to tackle many combinatorial optimizations problems that seem hard to tackle in other ways. Successful completion of the project will not only yield improved approximation algorithms for these problems, but also lead to a better understanding of the power of linear programming technique. As a part of the project, undergraduate and graduate students will be trained and involved in the research activities. The course materials resulting from this research project will be made freely accessible online. Recently, the round-or-cut paradigm has led to many improved approximation algorithms. This paradigm differs from the traditional "relax-and-round" paradigm in that the LP relaxation used to approximate the problem does not need to be efficiently solvable. As a result, the round-or-cut paradigm has the flexibility that the rounding algorithm can adaptively choose the set of linear constraints to require the fractional solution to satisfy. The major goal of this project is to leverage this flexibility to tackle problems that seem hard to tackle using the traditional relax-and-round paradigm, including the capacitated k-median problem, the machine minimization problem on identical machines, and the unsplittable flow problem on paths. The second goal is to understand the gap between the round-or-cut paradigm and the traditional relax-and-round paradigm. So far, the relax-and-round paradigm is far more popular than the round-or-cut paradigm in designing LP-based approximation algorithms. For a few problems only, algorithms require the stronger round-or-cut paradigm. The PI will investigate whether the relax-and-round paradigm is sufficient for these problems.