Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
We consider the problem of approximating an integer program by first solving its relaxation linear program and then "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 algorithm mimics the existence proof in a very strong sense. © 1988.
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
R.B. Morris, Y. Tsuji, et al.
International Journal for Numerical Methods in Engineering
Leo Liberti, James Ostrowski
Journal of Global Optimization
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997