The notion of recoverable value was advocated in work of Feige, Immorlica, Mirrokni and Nazerzadeh [Approx 2009] as a measure of quality for approximation algorithms. There this concept was applied to facility location problems. In the current work we apply a similar framework to the maximum independent set problem (MIS). We say that an approximation algorithm has recoverable value @math , if for every graph it recovers an independent set of size at least @math , where @math is the degree of vertex @math , and @math ranges over all independent sets in @math . Hence, in a sense, from every vertex @math in the maximum independent set the algorithm recovers a value of at least @math towards the solution. This quality measure is most effective in graphs in which the maximum independent set is composed of low degree vertices. It easily follows from known results that some simple algorithms for MIS ensure @math . We design a new randomized algorithm for MIS that ensures an expected recoverable value of at least @math . In addition, we show that approximating MIS in graphs with a given @math -coloring within a ratio larger than @math is unique games hard. This rules out a natural approach for obtaining @math .
Consider the LP relaxation of this program where each @math . A well known result due to Nemhauser and Trotter @cite_14 asserts that there is an optimal solution for the relaxation such that for every @math . Moreover, such an optimal solution can be found in polynomial time.
@cite_14
2192675411 2024631575 2123068254 1972894929
Maximum a-posteriori (MAP) inference is an important task for many applications. Although the standard formulation gives rise to a hard combinatorial optimization problem, several effective approximations have been proposed and studied in recent years. We focus on linear programming (LP) relaxations, which have achieved state-of-the-art performance in many applications. However, optimization of the resulting program is in general challenging due to non-smoothness and complex non-separable constraints. Therefore, in this work we study the benefits of augmenting the objective function of the relaxation with strong convexity. Specifically, we introduce strong convexity by adding a quadratic term to the LP relaxation objective. We provide theoretical guarantees for the resulting programs, bounding the difference between their optimal value and the original optimum. Further, we propose suitable optimization algorithms and analyze their convergence. We consider the problem of approximating an integer program by first solving its relaxation linear program and "rounding" the resulting solution. For several packing problems, we prove probabilistically that there exists an integer solution close to the optimum of the relaxation solution. We then develop a methodology for converting such a probabilistic existence proof to a deterministic approximation algorithm. The methodology mimics the existence proof in a very strong sense. We present several polynomial-time approximation algorithms for the one-dimensional bin-packing problem. using a subroutine to solve a certain linear programming relaxation of the problem. Our main results are as follows: There is a polynomial-time algorithm A such that A(I) ≤ OPT(I) + O(log2 OPT(I)). There is a polynomial-time algorithm A such that, if m(I) denotes the number of distinct sizes of pieces occurring in instance I, then A(I) ≤ OPT(I) + O(log2 m(I)). There is an approximation scheme which accepts as input an instance I and a positive real number e, and produces as output a packing using as most (1 + e) OPT(I) + O(e-2) bins. Its execution time is O(e-c n log n), where c is a constant. These are the best asymptotic performance bounds that have been achieved to date for polynomial-time bin-packing. Each of our algorithms makes at most O(log n) calls on the LP relaxation subroutine and takes at most O(n log n) time for other operations. The LP relaxation of bin packing was solved efficiently in practice by Gilmore and Gomory. We prove its membership in P, despite the fact that it has an astronomically large number of variables. Lov asz and Schrijver [SIAM J. Optim., 1 (1991), pp. 166--190] devised a lift-and-project method that produces a sequence of convex relaxations for the problem of finding in a graph an independent set (or a clique) of maximum size. Each relaxation in the sequence is tighter than the one before it, while the first relaxation is already at least as strong as the Lov asz theta function [IEEE Trans. Inform. Theory, 25 (1979), pp. 1--7]. We show that on a random graph Gn,1 2, the value of the rth relaxation in the sequence is roughly 0pt 7pt @math , almost surely. It follows that for those relaxations known to be efficiently computable, namely, for r=O(1), the value of the relaxation is comparable to the theta function. Furthermore, a perfectly tight relaxation is almost surely obtained only at the @math relaxation in the sequence.