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

DOI10.1007/BF02331572zbMath0729.90063OpenAlexW2032162132MaRDI QIDQ3354469

B. Tremel, Karl Heinz Borgwardt

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) Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (2)

Largest-first sequential selection with a sum constraint ⋮ Average-case performance of rollout algorithms for knapsack problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Largest-first sequential selection with a sum constraint
• Approximation schemes for the subset-sum problem: Survey and experimental analysis
• The bounded subset sum problem is almost everywhere randomly decidable in O(n)
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• Probabilistic analysis of the subset-sum problem
• Geometric algorithms and combinatorial optimization
• Approximation algorithms for combinatorial problems
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• Worst-case analysis of greedy algorithms for the subset-sum problem
• Solving low-density subset sum problems
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

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