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

DOI10.1016/0020-0190(92)90089-EzbMATH Open0793.90040MaRDI QIDQ1208445FDOQ1208445

Authors: Silvano Martello, Paolo Toth 

Publication date: 16 May 1993

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

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

zbMATH Keywords

approximation algorithmgreedy algorithmsworst-case boundsubset-sum problem0/1 knapsack problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• An Algorithm for Large Zero-One Knapsack Problems
• Worst-case analysis of greedy algorithms for the subset-sum problem
• A simple 0.5-bounded greedy algorithm for the 0/1 knapsack problem

Cited In (4)

• 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
• A simple 0.5-bounded greedy algorithm for the 0/1 knapsack 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)