Improved parallel approximation of a class of integer programming problems

Noga Alon, Aravind Srinivasan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 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 iVP-hard integer programming problems in NC, to within factors better than the current-best NC algorithms (of Berger &c 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. 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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings
EditorsFriedhelm Meyer auf der Heide, Burkhard Monien
PublisherSpringer Verlag
Pages562-573
Number of pages12
ISBN (Print)3540614400, 9783540614401
DOIs
StatePublished - 1996
Externally publishedYes
Event23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996 - Paderborn, Germany
Duration: Jul 8 1996Jul 12 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1099
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other23rd International Colloquium on Automata, Languages, and Programming, ICALP 1996
CountryGermany
CityPaderborn
Period7/8/967/12/96

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

    Alon, N., & Srinivasan, A. (1996). Improved parallel approximation of a class of integer programming problems. In F. Meyer auf der Heide, & B. Monien (Eds.), Automata, Languages and Programming - 23rd International Colloquium, ICALP 1996, Proceedings (pp. 562-573). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1099). Springer Verlag. https://doi.org/10.1007/3-540-61440-0_159