DERANDOMIZED GRAPH PRODUCTS

被引：73
作者：
ALON, N
FEIGE, U
WIGDERSON, A
ZUCKERMAN, D
机构：
[1] AT&T BELL LABS,MURRAY HILL,NJ 07974
[2] HEBREW UNIV JERUSALEM,DEPT COMP SCI,IL-91904 JERUSALEM,ISRAEL
[3] WEIZMANN INST SCI,DEPT APPL MATH & COMP SCI,IL-76100 REHOVOT,ISRAEL
[4] UNIV TEXAS,DEPT COMP SCI,AUSTIN,TX 78712
来源：
COMPUTATIONAL COMPLEXITY | 1995年 / 5卷 / 01期
关键词：
APPROXIMATION; DERANDOMIZATION; RANDOM WALKS;
D O I：
10.1007/BF01277956
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Berman and Schnitger gave a randomized reduction from approximating MAX-SNP problems within constant factors arbitrarily close to 1 to approximating clique within a factor of n(epsilon) (for some epsilon). This reduction was further studied by Blum, who gave it the name randomized graph products. We show that this reduction can be made deterministic (derandomized), using random walks on expander graphs. The main technical contribution of this paper is in proving a lower bound for the probability that all steps of a random walk stay within a specified set of vertices of a graph. (Previous work was mainly concerned with upper bounds for this probability.) This lower bound extends also to the case where different sets of vertices are specified for different time steps of the walk.
引用
收藏
页码：60 / 75
页数：16
相关论文
共 24 条
[1]  
AJTAI M, 1987, 19TH P ACM S THEOR C, P132
[2]   EIGENVALUES AND EXPANDERS [J].
ALON, N .
COMBINATORICA, 1986, 6 (02) :83-96
[3]   EXPLICIT CONSTRUCTION OF LINEAR SIZED TOLERANT NETWORKS [J].
ALON, N ;
CHUNG, FRK .
DISCRETE MATHEMATICS, 1988, 72 (1-3) :15-19
[4]  
AMALDI E, IN PRESS THEORET COM
[5]  
ARORA S, 1993, 34 FOCS, P724
[6]  
ARORA S, 1992, 33RD P IEEE S F COMP, P14
[7]  
BELLARE M, 1990, 31ST P S F COMP SCI, P563
[8]   ON THE COMPLEXITY OF APPROXIMATING THE INDEPENDENT SET PROBLEM [J].
BERMAN, P ;
SCHNITGER, G .
INFORMATION AND COMPUTATION, 1992, 96 (01) :77-94
[9]  
BERMAN P, 1994, 5 ACM SIAM S DISCR A, P365
[10]  
BLUM A, THESIS MIT
123