Fast approximate PCPs for multidimensional bin-packing problems

DOI10.1016/J.IC.2004.10.001MaRDI QIDQ1767978zbMATH OpenOpenAlexFDO

Authors Tuğkan Batu, Ronitt Rubinfeld, Patrick White

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)

Recommendations

• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• A dense hierarchy of sublinear time approximation schemes for bin packing
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
• New classes of fast lower bounds for bin packing problems
• An asymptotically exact algorithm for the high-multiplicity bin packing problem
• Approximation schemes for multidimensional packing
• Approximation algorithms for a hierarchically structured bin packing problem
• Approximation and online algorithms for multidimensional bin packing: a survey
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• Approximation schemes for the generalized extensible bin packing problem

Cites work

• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• Distribution-free property testing
• Fast approximate probabilistically checkable proofs
• Monotonicity testing over general poset domains
• Non-deterministic exponential time has two-prover interactive protocols
• Proof verification and the hardness of approximation problems
• Spot-checkers

Cited in

(16)

• Erasure-Resilient Property Testing
• Optimal unateness testers for real-valued functions: adaptivity helps
• Testing Lipschitz functions on hypergrid domains
• Fast approximate probabilistically checkable proofs
• Testing \(k\)-monotonicity
• Tolerant property testing and distance approximation
• Transitive-closure spanners: a survey
• Local property reconstruction and monotonicity
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Approximating the distance to monotonicity of Boolean functions
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• Parameterized property testing of functions
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Distribution-free connectivity testing for sparse graphs
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Testing of matrix-poset properties

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1767978)