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
相关论文
共 50 条
  • [1] BIN-PACKING PROBLEMS FOR A RENEWAL PROCESS
    STADJE, W
    ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 1990, 26 (01): : 207 - 217
  • [2] Notes on inverse bin-packing problems
    Chung, Yerim
    Park, Myoung-Ju
    INFORMATION PROCESSING LETTERS, 2015, 115 (01) : 60 - 68
  • [3] Cardinality constrained bin-packing problems
    Kellerer, H
    Pferschy, U
    ANNALS OF OPERATIONS RESEARCH, 1999, 92 (0) : 335 - 348
  • [4] BIN-PACKING
    WAGON, S
    MATHEMATICAL INTELLIGENCER, 1985, 7 (04): : 65 - 68
  • [5] The Price of Clustering in Bin-Packing with Applications to Bin-Packing with Delays
    Azar, Yossi
    Emek, Yuval
    van Stee, Rob
    Vainstein, Danny
    SPAA'19: PROCEEDINGS OF THE 31ST ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURESS, 2019, 2019, : 1 - 10
  • [6] Two heuristics for one of Bin-Packing problems
    Egor, Barashov
    Egor, Grishin
    Daria, Lemtuzhnikova
    IFAC PAPERSONLINE, 2022, 55 (10): : 2575 - 2580
  • [7] Hybrid genetic algorithms for bin-packing and related problems
    Reeves, C
    ANNALS OF OPERATIONS RESEARCH, 1996, 63 : 371 - 396
  • [8] Hybrid genetic algorithms for bin-packing and related problems
    Reeves, C.
    Annals of Operations Research, (63):
  • [9] Algorithms for on-line bin-packing problems with cardinality constraints
    Babel, L
    Chen, B
    Kellerer, H
    Kotov, V
    DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) : 238 - 251
  • [10] A typical problem of bin-packing
    Figueroa Mata, Geovanni
    Carrera Retana, Ernesto
    TECNOLOGIA EN MARCHA, 2011, 24 (02): : 34 - 43
12345