Improved parallel approximation of a class of integer programming problems |
| |
Authors: | N Alon A Srinivasan |
| |
Affiliation: | (1) School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, 69978 Tel Aviv, Israel;(2) Department of Information Systems and Computer Science, National University of Singapore, 119260 Singapore, Republic of Singapore |
| |
Abstract: | We present a method to derandomizeRNC algorithms, converting them toNC algorithms. Using it, we show how to approximate a class of NP-hard integer programming problems inNC, to within factors better than the current-bestNC algorithms (of Berger and Rompel and Motwaniet al.); in some cases, the approximation factors are as good as the best-known sequential algorithms, due to Raghavan. This class
includes problems such as global wire-routing in VLSI gate arrays and a generalization of telephone network planning in SONET
rings. Also for a subfamily of the “packing” integer programs, we provide the firstNC approximation algorithms; this includes problems such as maximum matchings in hypergraphs, and generalizations. The key to
the utility of our method is that it involves sums ofsuperpolynomially many terms, which can however be computed inNC; this superpolynomiality is the bottleneck for some earlier approaches, due to Berger and Rompel and Motwaniet al.
A preliminary version of this work appeared inProc. International Colloquim on Automata, Languages and Programming, 1996, pages 562–573.
Work done in parts at DIMACS (supported in part by NSF-STC91-19999 and by support from the N.J. Commission on Science and
Technology), at the Institute for Advanced Study, Princeton (supported in part by Grant 93-6-6 of the Alfred P. Sloan Foundation),
and at the National University of Singapore. |
| |
Keywords: | De-randomization Integer programming Parallel algorithms Approximation algorithms Rounding theorems Randomized rounding Linear programming Linear relaxation Combinatorial optimization |
本文献已被 SpringerLink 等数据库收录! |
|