Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/99307
Title: Improved Parallel Approximation of a Class of Integer Programming Problems
Authors: Alon, N.
Srinivasan, A. 
Keywords: Approximation algorithms
Combinatorial optimization
De-randomization
Integer programming
Linear programming
Linear relaxation
Parallel algorithms
Randomized rounding
Rounding theorems
Issue Date: Apr-1997
Source: Alon, N.,Srinivasan, A. (1997-04). Improved Parallel Approximation of a Class of Integer Programming Problems. Algorithmica (New York) 17 (4) : 449-462. ScholarBank@NUS Repository.
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.
Source Title: Algorithmica (New York)
URI: http://scholarbank.nus.edu.sg/handle/10635/99307
ISSN: 01784617
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

34
checked on Feb 23, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.