Improved Parallel Approximation of a Class of Integer Programming Problems

N. Alon, A. Srinivasan

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

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 and Rompel and Motwani et 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 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 and Rompel and Motwani et al.

Original languageEnglish (US)
Pages (from-to)449-462
Number of pages14
JournalAlgorithmica (New York)
Volume17
Issue number4
DOIs
StatePublished - Apr 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Approximation algorithms
  • Combinatorial optimization
  • De-randomization
  • Integer programming
  • Linear programming
  • Linear relaxation
  • Parallel algorithms
  • Randomized rounding
  • Rounding theorems

Fingerprint Dive into the research topics of 'Improved Parallel Approximation of a Class of Integer Programming Problems'. Together they form a unique fingerprint.

  • Cite this