Analysis of a first-fit algorithm for the capacitated unit covering problem

DOI10.1080/00207160.2016.1190834MaRDI QIDQ4976332zbMATH OpenOpenAlexFDO

Authors Taha Ghasemi, Mohammadreza Razzazi

Publication date 28 July 2017

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160.2016.1190834

zbMATH Keywords

approximation algorithmbin packingcapacitated unit covering problemcomputational geometry

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On capacitated covering with unit balls
• scientific article; zbMATH DE number 6678949
• Dynamic bin packing with unit fraction items revisited
• The tight asymptotic approximation ratio of first fit for bin packing with cardinality constraints
• Capacitated vertex covering

Cites work

• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering a set of points in multidimensional space
• Dynamic bin packing with unit fraction items revisited
• Fast algorithms for bin packing
• Hitting sets when the VC-dimension is small
• scientific article; zbMATH DE number 563208 (Why is no real title available?)
• On Bin Packing with Conflicts
• On Packing Two-Dimensional Bins
• Online unit clustering: Variations on a theme
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Resource constrained scheduling as generalized bin packing
• Tighter bounds of the First Fit algorithm for the bin-packing problem

This page was built for publication: Analysis of a first-fit algorithm for the capacitated unit covering problem

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