The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem

DOI10.1007/BF02331572MaRDI QIDQ3354469zbMATH OpenOpenAlexFDO

Authors K. H. Borgwardt, B. Tremel

Publication date 1991

Published in ZOR - Methods and Models of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02331572

zbMATH Keywords

knapsack problemssubset sum maximizationgreedy-algorithmsstochastic analysis of heuristic algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09)

Recommendations

• Stochastic analysis of greedy algorithms for the subset sum problem
• Two linear approximation algorithms for the subset-sum problem
• A class of generalized greedy algorithms for the multi-knapsack problem
• Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems
• The bounded subset sum problem is almost everywhere randomly decidable in O(n)

Cites work

• scientific article; zbMATH DE number 3878679 (Why is no real title available?)
• scientific article; zbMATH DE number 3939098 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Approximation algorithms for combinatorial problems
• Approximation schemes for the subset-sum problem: Survey and experimental analysis
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Geometric algorithms and combinatorial optimization
• Largest-first sequential selection with a sum constraint
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• Probabilistic analysis of the subset-sum problem
• Solving low-density subset sum problems
• The bounded subset sum problem is almost everywhere randomly decidable in O(n)
• Worst-case analysis of greedy algorithms for the subset-sum problem

Cited in

(7)

• Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations
• Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems
• Bounds on the Performance of a Greedy Algorithm for Probabilities
• Largest-first sequential selection with a sum constraint
• Stochastic analysis of greedy algorithms for the subset sum problem
• On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem
• Average-case performance of rollout algorithms for knapsack problems

This page was built for publication: The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem

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