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