Two linear approximation algorithms for the subset-sum problem

DOI10.1016/S0377-2217(99)00157-5zbMath0955.90150OpenAlexW1997684383MaRDI QIDQ1969831

Hans Kellerer, Renata Mansini, Maria Grazia Speranza

Publication date: 19 March 2000

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(99)00157-5

zbMATH Keywords

worst-case performanceapproximation algorithmssubset-sum problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations, Randomized strategies for robust combinatorial optimization with approximate separation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems
• A new linear storage, polynomial-time approximation scheme for the subset-sum problem
• Worst-case analysis of greedy algorithms for the subset-sum problem
• A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
• Merging and Sorting Applied to the Zero-One Knapsack Problem
• Computing Partitions with Applications to the Knapsack Problem
• Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning