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