Greedy algorithms for the minimization knapsack problem: average behavior
type: Item
instance of: scholarly article
title: Greedy algorithms for the minimization knapsack problem: average behavior
zbMATH Open document ID: 1192.90166
published in: Journal of Computer and Systems Sciences International
publication date: 2009-10-19T00:00:00Z
review text: The authors study the average behaviour of primal and dual greedy methods for the solution of the following knapsack problem: \[ \min \left\{ \sum^{n}_{j=1} c_{j}y_{j} \mid \sum^{n}_{j=1} a_{j}y_{j} \geq d, y_{j} \in \{0,1\}, j=1,\dots,n\right\}. \tag{P} \] The coefficients \(c_{j}, a_{j}\) are assumed to be independent random variables uniformly distributed over \([0,1]\). If \(\mathcal{A}_{n}\) denotes the primal or dual greedy algorithm for the solution of (P), \(g^{\mathcal{A}_{n}}\) the resulting objective function value, and \(g^{*}\) the optimal value of (P), \(\mathcal{A}_{n}\) is said \textit{to have asymptotical tolerance \(t > 0\)}, if \({\mathbf P}(g^{\mathcal{A}_{n}}-g^{*} \leq t) \rightarrow 1 \text{ for } n \rightarrow \infty\). The main result of this paper is the following: If \(d=\mu n\) with \(\mu < t/3\), then the primal and dual greedy methods for (P) have asymptotical tolerance \(t\).
reviewed by: Reinhardt Euler
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C15
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 5617854
author: G. N. Dyubin
author: A. A. Korbut
describes a project that uses: Stony Brook
describes a project that uses: Knapsack
MaRDI profile type: Publication
full work available at URL: s11488-008-1003-1
OpenAlex ID: W4229769813
DOI: 10.1007/S11488-008-1003-1
Recommended article: The primal and dual greedy algorithms for the knapsack problem: the average behavior
Recommended article: The average behaviour of greedy algorithms for the knapsack problem: general distributions
Recommended article: Q4233334
Recommended article: Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.
Recommended article: Q3682239
Recommended article: Average performance of greedy heuristics for the integer knapsack problem.
Recommended article: On the optimality of the greedy solutions of the general knapsack problems
Recommended article: Worst-case and average-case analysis of an algorithm solving a generalized knapsack problem
Recommended article: Greedy algorithms for a class of knapsack problems with binary weights
Recommended article: Q5753744
description: scientific article; zbMATH DE number 5617854