Bin-packing and matchings in threshold graphs
type: Item
instance of: scholarly article
title: Bin-packing and matchings in threshold graphs
zbMATH Open document ID: 0838.05083
DOI: 10.1016/0166-218X(94)00156-8
published in: Discrete Applied Mathematics
publication date: 1996-05-30T00:00:00Z
review text: For \(z\in (0, 1]^n\), let \(L_n(z)\) be the number of bins in an optimal solution to the bin-packing problem \(z\). Using some version of the first fit decreasing heuristic FFD, the author obtains the following explicit formulae: \[ \begin{aligned} \text{Exp}(L_{2m}(Z)) & = m+ (2m- 1) (\begin{smallmatrix} 2(m- 2)\\ m- 1\end{smallmatrix}) 2^{- 2m+ 1},\\ \text{Exp} (L_{2m+ 1}(Z)) & = m-\textstyle{{1\over 2}}+ (2m+ 1)(\begin{smallmatrix} 2m\\ m\end{smallmatrix}) 2^{- 2m- 1}.\end{aligned} \] They imply \[ \text{Exp}(L_n(Z))\to \lfloor\textstyle{{n\over 2}}\rfloor+ \sqrt{\overline 2\pi^{- 1}} \overline n, \] where \(\to\) means stochastic convergence.
reviewed by: Toru Ishihara
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 806418
zbMATH Keywords: matching
zbMATH Keywords: threshold graphs
zbMATH Keywords: number of bins
zbMATH Keywords: bin-packing problem
zbMATH Keywords: FFD
zbMATH Keywords: stochastic convergence
author: Gottfried Tinhofer
MaRDI profile type: Publication
cites work: Q4002885
cites work: Q3328583
cites work: Q3911421
Recommended article: Ond-threshold graphs andd-dimensional bin packing
Recommended article: Packing $k$-Matchings and $k$-Critical Graphs
Recommended article: THE GRAPH-BIN PACKING PROBLEM
Recommended article: On packing bipartite graphs
Recommended article: Total matchings and total coverings of threshold graphs
Recommended article: Threshold arrangements and the knapsack problem
Recommended article: On the bipartite graph packing problem
Recommended article: Extremal threshold graphs for matchings and independent sets
Recommended article: Q3390778
Recommended article: An exact threshold theorem for random graphs and the node-packing problem
description: scientific article; zbMATH DE number 806418