A note on 0.5-bounded greedy algorithms for the 0/1 knapsack problem

DOI10.1016/0020-0190(92)90089-EMaRDI QIDQ1208445zbMATH OpenFDO

Authors Silvano Martello, Paolo Toth

Publication date 16 May 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90089-E

zbMATH Keywords

0/1 knapsack problemapproximation algorithmgreedy algorithmssubset-sum problemworst-case bound

Mathematics Subject Classification ID

Boolean programming (90C09) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem
• A note on the max-min 0-1 knapsack problem
• Publication:3481489
• Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
• Average-case analysis of a greedy algorithm for the 0/1 knapsack problem.
• scientific article; zbMATH DE number 7122316
• Computing and Selecting ε-Efficient Solutions of {0, 1}-Knapsack Problems
• Approximation algorithms on 0--1 linear knapsack problem with a single continuous variable
• Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm
• Lower Bounds on Time-Accuracy Trade-Offs for the 0-1 Knapsack Problem

Cites work

• A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem
• An Algorithm for Large Zero-One Knapsack Problems
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• Worst-case analysis of greedy algorithms for the subset-sum problem

Cited in

(4)

• A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem
• An approximate binary search algorithm for the multiple-choice knapsack problem
• Lower Bounds on Time-Accuracy Trade-Offs for the 0-1 Knapsack Problem
• A Fast Approximation Algorithm For The Subset-Sum Problem

This page was built for publication: A note on 0.5-bounded greedy algorithms for the 0/1 knapsack problem

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