Online bin packing with advice of small size

DOI10.1007/S00224-018-9862-5MaRDI QIDQ2322702zbMATH OpenOpenAlexWikidataFDO

Authors Spyros Angelopoulos, Christoph Dürr, Shahin Kamali, Marc P. Renault, Adi Rosén

Publication date 5 September 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-018-9862-5

zbMATH Keywords

competitive analysisadvice complexityonline bin packing

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• Online bin packing with advice of small size
• Online bin packing with advice
• Online bin packing with advice
• Online algorithms with advice for bin packing and scheduling problems
• On the advice complexity of one-dimensional online bin packing

Cites work

• scientific article; zbMATH DE number 3557207 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1870507 (Why is no real title available?)
• scientific article; zbMATH DE number 910900 (Why is no real title available?)
• Advice complexity and barely random algorithms
• Algorithms for the relaxed online bin-packing model
• Analysis and design of algorithms in combinatorial optimization. (School held in Udine in September 1979)
• Beating the harmonic lower bound for online bin packing
• How Much Information about the Future Is Needed?
• Measuring the problem-relevant information in input
• New lower bounds for certain classes of bin packing algorithms
• On Bin Packing with Conflicts
• On online algorithms with advice for the k-server problem
• On the Advice Complexity of Online Problems
• On the advice complexity of the \(k\)-server problem
• On the advice complexity of the \(k\)-server problem under sparse metrics
• Online algorithms with advice for bin packing and scheduling problems
• Online bin packing with advice
• Online bin packing with advice of small size
• Online computation with advice
• Online minimum spanning tree with advice (extended abstract)
• Randomization can be as helpful as a glimpse of the future in online computation
• Reordering buffer management with advice
• Repacking helps in bounded space on-line bin-packing
• The online knapsack problem: advice and randomization
• The string guessing problem as a method to prove lower bounds on the advice complexity
• Weighted Online Problems with Advice
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(14)

• Online bin packing with advice
• Online algorithms with advice for bin packing and scheduling problems
• Online computation with untrusted advice
• Online bin packing with advice of small size
• Parallel solutions for ordinal scheduling with a small number of machines
• A simple PTAS for the dual bin packing problem and advice complexity of its online version
• Online unit profit knapsack with predictions
• Approximation and Online Algorithms
• Online bin covering with advice
• Online bin covering with advice
• On the advice complexity of one-dimensional online bin packing
• Online bin packing with resource augmentation
• Online bin packing with advice
• Online two-dimensional vector packing with advice

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Online bin packing with advice of small size

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