Bin packing under linear constraints

DOI10.1007/s10878-017-0140-2zbMath1383.90035OpenAlexW2618972974MaRDI QIDQ1679514

Kameng Nip, Zhen-bo Wang

Publication date: 9 November 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0140-2

zbMATH Keywords

linear programmingapproximation algorithmbin packingworst-case ratio

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints ⋮ Some graph optimization problems with weights satisfying linear constraints ⋮ Related machine scheduling with machine speeds satisfying linear constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling under linear constraints
• Tight absolute bound for first fit decreasing bin-packing: \(\operatorname{FFD}(L)\leq 11/9 \operatorname{OPT}(L)+6/9\)
• A new polynomial-time algorithm for linear programming
• Bin packing with controllable item sizes
• Bin packing can be solved within 1+epsilon in linear time
• Variable Sized Bin Packing
• Optimal Bin Packing with Items of Random Sizes
• Optimal Bin Packing with Items of Random Sizes II
• Polynomial algorithms in linear programming
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Bin packing under linear constraints