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 algorithmknapsack problemrecurrence relationsjob schedulingsequential selectionaverage-case performancemaximum subset sum problemmultiprogrammed parallel systemson-line approximation algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Complexity and performance of numerical algorithms (65Y20)

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

This page was built for publication: Average-case performance analysis of an approximation algorithm for maximum subset sum using recurrence relations