Fast approximate PCPs for multidimensional bin-packing problems

DOI10.1016/j.ic.2004.10.001zbMath1062.68140OpenAlexW2116455242MaRDI QIDQ1767978

Ronitt Rubinfeld, Patrick White, Tuğkan Batu

Publication date: 8 March 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/ic

zbMATH Keywords

Multidimensional bin-packing problemsProbabilistically checkable proofsProof-assisted property testingSublinear-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (14)

Testing Lipschitz functions on hypergrid domains ⋮ Parameterized property testing of functions ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Unnamed Item ⋮ Erasure-Resilient Property Testing ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Testing of matrix-poset properties ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Transitive-Closure Spanners: A Survey ⋮ Local Property Reconstruction and Monotonicity ⋮ Tolerant property testing and distance approximation ⋮ Unnamed Item ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Spot-checkers
• Fast approximate probabilistically checkable proofs
• Proof verification and the hardness of approximation problems
• Monotonicity testing over general poset domains
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Fast approximate PCPs for multidimensional bin-packing problems