Fast approximate PCPs for multidimensional bin-packing problems

被引：26

作者：

Batu, T ^{[1
]}

Rubinfeld, R

White, P

机构：

[1] Simon Fraser Univ, Sch Comp Sci, Burnaby, BC V5A 1S6, Canada

[2] MIT, CSAIL, Cambridge, MA 02139 USA

[3] Cornell Univ, Comp Sci Dept, Ithaca, NY 14853 USA

来源：

INFORMATION AND COMPUTATION | 2005年 / 196卷 / 01期

基金：

美国国家科学基金会;

关键词：

proof-assisted property testing; probabilistically checkable proofs; multidimensional bin-packing problems; sublinear-time algorithms;

D O I：

10.1016/j.ic.2004.10.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider approximate PCPs for multidimensional bin-packing problems. In particular, we show how a verifier can be quickly convinced that a set of multidimensional blocks can be packed into a small number of bins. The running time of the verifier is bounded by O(log(d) n) where n is the number of blocks and d is the dimension. (C) 2004 Elsevier Inc. All rights reserved.

引用

页码：42 / 56

页数：15

共 9 条

[1] Proof verification and the hardness of approximation problems [J].

Arora, S ;

Lund, C ;

Motwani, R ;

Sudan, M ;

Szegedy, M .

JOURNAL OF THE ACM, 1998, 45 (03) :501-555

[2]

Babai L., 1991, Computational Complexity, V1, P3, DOI 10.1007/BF01200056

[3]

Babai Laszlo, 1991, P 23 ANN ACM S THEOR, P21, DOI [10.1145/103418.103428, DOI 10.1145/103418.103428]

[4]

DODIS Y, 1999, LNCS, V1671, P96

[5] Fast approximate probabilistically checkable proofs [J].

Ergün, F ;

Kumar, R ;

Rubinfeld, R .

INFORMATION AND COMPUTATION, 2004, 189 (02) :135-159

[6] Spot-checkers [J].

Ergün, F ;

Kannan, S ;

Kumar, SR ;

Rubinfeld, R ;

Viswanathan, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2000, 60 (03) :717-751

[7]

Fischer E., 2002, P 34 ANN ACM S THEOR, P474

[8] Testing monotonicity [J].

Goldreich, O ;

Goldwasser, S ;

Lehman, E ;

Ron, D .

39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :426-435

[9]

HALEVY S, 2003, LNCS, V1671, P302

← 1 →