Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations

DOI10.1016/S0898-1221(98)00162-XzbMath0932.65069MaRDI QIDQ1125006

S. H. Smith

Publication date: 15 March 2000

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

zbMATH Keywords

approximation algorithm; knapsack problem; recurrence relations; job scheduling; sequential selection; average-case performance; maximum subset sum problem; multiprogrammed parallel systems; on-line approximation algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

65K05: Numerical mathematical programming methods

90C27: Combinatorial optimization

65Y20: Complexity and performance of numerical algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Largest-first sequential selection with a sum constraint
• Probabilistic bounds for dual bin-packing
• Bin packing: Maximizing the number of pieces packed
• Heuristic algorithms for the multiple knapsack problem
• Probabilistic analysis of the subset-sum problem
• Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems
• Probabilistic analysis of a heuristic for the dual bin packing problem
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• Solving low-density subset sum problems
• Asymptotic Methods in the Probabilistic Analysis of Sequencing and Packing Heuristics
• Breaking Records and Breaking Boards
• Optimal selection of stochastic intervals under a sum constraint