The tight asymptotic approximation ratio of First Fit for bin packing with cardinality constraints
作者:
Highlights:
• A complete analysis of First Fit for bin packing with cardinality constraints.
• Novel weights functions that provide a tight analysis.
• The problem was open since the 1970's.
• Surprising results compared to standard bin packing.
• A moderate number of cases for the different constraints.
摘要
•A complete analysis of First Fit for bin packing with cardinality constraints.•Novel weights functions that provide a tight analysis.•The problem was open since the 1970's.•Surprising results compared to standard bin packing.•A moderate number of cases for the different constraints.
论文关键词:Bin packing,First fit,Asymptotic approximation ratio
论文评审过程:Received 24 May 2015, Revised 13 August 2016, Accepted 26 March 2018, Available online 13 April 2018, Version of Record 31 May 2018.
论文官网地址:https://doi.org/10.1016/j.jcss.2018.03.004