文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Improved low-density subset sum algorithms
侵权投诉

Improved low-density subset sum algorithms

The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on bas

0:9408::: cannot be improved in this way. The following proposition shows that any n-sphere of radius p n with< can cover only an exponentially small fraction of the vertices of the n-cube. Thus, no polynomial collection of such spheres can satisfy our requirements. 1 4

p n with< . We show that this is not possible, and that the asymptotic bound of 1 4

Proposition. Any sphere of radius p n;<, in Rn contains at most (2? )n points of f0; 1gn, for some= ( )> 0. 1 4 1 2

Proof. Suppose that the n-sphere is centered at the point c= (c;:::; cn ). We are interested in the number of points e 2 f0; 1gn for which kc? ek n. Using the upper bound technique of 14], we show that N, the number of points in f0; 1gn inside the sphere, is bounded by

N e 1

n n Y (e?c2 i i=1

+ e? c? 2 ): ( i

1)

(20) 2 P=1 2

If the point e= (e;:::; en) is inside the sphere, then kc? ek= n (ci? ei) i and after expanding the right side, Equation 20 contains a term of the form exp

n,

n? (ci? ei) X

n

!

2

for each such point e, which proves Equation 20 since all terms in the expansion are nonnegative. Since the terms in the product in Equation 20 are independent, we know that the value of N is bounded by

i=1

1;

e n max c2R n

Y

n

i=1

e?c2+ e? c? i

(

i

1)2

e n(2e?= )n: 1 4 ( 1) 1 4

(It is easy to show that the maximum value of f (z)= e?z2+ e? z? 2 is 2e?= .) Thus,

N en 2n e?= n= 2n en ( 1 4) 1 4

(

?1=4)?1=4)

= (2? ( ))n; for ( )= 2(1? e 1 4

For all<, ( )> 0, which proves the proposition. As n ! 1, any n-sphere with radius p n,<, will contain at most (2? ( ))n points in f0; 1gn . Thus, any polynomial-sized collection of spheres cannot contain all the points in f0; 1gn . Thus we cannot hope to asymptotically improve the 0:9408:::

上一页第5页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email