Inapproximability of Combinatorial Problems via Small LPs and SDPs
Wednesday, February 25, 2015 - 11:30am - 12:20pm
We provide a framework for studying the size of linear programming formulations as well as semidefinite programming formulations of combinatorial optimization problems without encoding them first as linear programs or semidefinite programs. This is done via a factorization theorem for the optimization problem itself (and not a specific encoding of such). As a result we can define the first consistent reduction mechanism that degrades approximation factors in a controlled fashion and which, at the same time, is compatible with approximate linear and semidefinite programming formulations. Moreover, our reduction mechanism is a minor restriction of classical reductions establishing inapproximability in the context of PCP theorems. As a consequence we can establish strong linear programming inapproximability for LPs (and SDPs) with a polynomial number of constraints for a host of problems, such as e.g., VertexCover, where we obtain a 3/2-epsilon inapproximability. Moreover, combining our framework with a recent result of Lee, Raghavendra, and Steurer we can also obtain a large array of inapproximability results for SDPs.