Abstract: Optimization of discrete mathematical programs is a computationally difficult problem. We would like to find approximation algorithms for many NP-Hard problems that are naturally described in terms of optimizing nonlinear functions. One approach to solving these problems is to construct a solvable linear approximation and a mechanism for converting a linear solution into a discrete one. If the error produced in relaxing the problem and in converting the relaxed solution back into an integer one can be bounded then an approximation algorithm can be constructed. This talk will present two techniques based on linear program relaxations and rounding to produce approximation algorithms for certain combinatorial optimization problems.

PIPAGE rounding (Ageev and Sviridenko, 2000) is a general method of constructing constant-factor approximation algorithms for some discrete optimization problems with assignment-type constraints over bipartite graphs. The key components of this method are producing a linear relaxation of the optimization problem and performing a simple deterministic rounding procedure on this relaxation. This method was first used to design approximations algorithms with better performance guarantees for well-known problems related to maximum coverage and maximum cut.

The second technique (Fleishcer, Goemans, Mirrokni, and Sviridenko, 2006) is used to construct approximation algorithms for a broad class of assignment problems, given that an approximation algorithm exists for the simplified one bin/location versions of the problems. A separable assignment problem (SAP) is defined by a set of bins and a set of items to pack in each bin; a value, f_ij, for assigning item j to bin i; and a separate packing constraint for each bin - i.e. for bin i, a family L_i of subsets of items that fit in bin i. The goal is to pack items into bins to maximize the aggregate value. This describes a very broad class of problems, since the constraints on the valid bin packings can potentially be exponentially large. Problems that belong to this class include maximum general assignment (GAP), knapsack, AdWord assignment (AAP), and distributed caching (DCP). Given a β-approximation algorithm for finding the highest value packing of a single bin for a SAP problem, this technique can be used to construct a polynomial-time LP-rounding based ((1 - 1/e)β)-approximation algorithm for the general multi-bin problem.