The Lovasz Local Lemma due to Erdos and Lovasz is a powerful tool in proving the existence of rare events. We present an extension of this lemma, which works well when the event to be shown to exist is a conjunction of individual events, each of which asserts that a random variable does not deviate much from its mean. As applications, we consider two classes of NP-hard integer programs: minimax and covering integer programs. A key technique, randomized rounding of linear relaxations, was developed by Raghavan and Thompson to derive good approximation algorithms for such problems. We use our extension of the Local Lemma to prove that randomized rounding produces, with non-zero probability, much better feasible solutions than known before, if the constraint matrices of these integer programs are column-sparse (e.g., routing using short paths, problems on hypergraphs with small dimension degree). This complements certain well-known results from discrepancy theory. We also generalize the method of pessimistic estimators due to Raghavan, to obtain constructive (algorithmic) versions of our results for covering integer programs.
To see what problems MIPs model, note, from constraints (i) and (iii) of MIPs, that for all @math , any feasible solution will make the set @math have precisely one 1, with all other elements being 0; MIPs thus model many choice'' scenarios. Consider, e.g., global routing in VLSI gate arrays @cite_22 . Given are an undirected graph @math , a function @math , and @math , a set @math of paths in @math , each connecting @math to @math ; we must connect each @math with @math using exactly one path from @math , so that the maximum number of times that any edge in @math is used for, is minimized--an MIP formulation is obvious, with @math being the indicator variable for picking the @math th path in @math . This problem, the vector-selection problem of @cite_22 , and the discrepancy-type problems of , are all modeled by MIPs; many MIP instances, e.g., global routing, are NP-hard.
@cite_22
2022191808
We study undirected networks with edge costs that satisfy the triangle inequality. Let @math denote the number of nodes. We present an @math -approximation algorithm for a generalization of the metric-cost subset @math -node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each @math , there exists a @math -node connected graph whose cost is within a factor of @math of the cost of any simple @math -edge connected graph. Based on our @math -approximation algorithm, we present an @math -approximation algorithm for the metric-cost node-connectivity survivable network design problem, where @math denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of 0 or 1, where Kortsarz, Krauthgamer, and Lee. [SIAM J. Comput., 33 (2004), pp. 704-720] recently proved, assuming NP @math DTIME( @math ), a hardness-of-approximation lower bound of @math for the subset @math -node-connectivity problem, where @math denotes a small positive number.