Browsing by Author "Noga Alon"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Improved parallel approximation of a class of integer programming problems
    (1995-11-01T00:00:00Z) Noga Alon; Aravind Srinivasan
    We present a method to derandomize RNC algorithms, converting them to NC algorithms. Using it, we show how to approximate a class of NP-hard integer programming problems in NC, to within factors better than the current-best NC algorithms (of Berger & Rompel and Motwani, Naor & Naor); 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 first NC 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 of superpolynomially many terms, which can however be computed in NC; this superpolynomiality is the bottleneck for some earlier approaches, due to Berger & Rompel and Motwani, Naor & Naor. Part of Alon's work was done while visiting the Institute for Advanced Study, School of Mathematics, Princeton, NJ 08540, USA, supported in part by the Sloan Foundation, grant No. 93-6-6 and by the Fund for Basic Research administered by the Israel Academy of Sciences. Srinivasan's work was done in part at the National University of Singapore, at DIMACS (supported in part by NSF-STC91-19999 and by support from the N.J. Commission on Science and Technology), and at the Institute for Advanced Study, Princeton (supported in part by grant 93-6-6 of the Alfred P. Sloan Foundation).