A PTAS for the multiple subset sum problem with different knapsack capacities

DOI10.1016/S0020-0190(00)00010-7zbMath1014.68225MaRDI QIDQ1607031

Ulrich Pferschy, Alberto Caprara, Hans Kellerer

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

multiple subset sum problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (16)

Multiple subset sum with inclusive assignment set restrictions ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Improved algorithmic results for unsplittable stable allocation problems ⋮ Coupled-Tasks in Presence of Bipartite Compatibilities Graphs ⋮ LP based heuristics for the multiple knapsack problem with assignment restrictions ⋮ Some complexity and approximation results for coupled-tasks scheduling problem according to topology ⋮ Faster algorithms for \(k\)-\textsc{Subset Sum} and variations ⋮ Mathematical models and decomposition methods for the multiple knapsack problem ⋮ A branch-and-bound algorithm for hard multiple knapsack problems ⋮ Approximation algorithms for scheduling with reservations ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ MAKESPAN MINIMIZATION WITH MACHINE AVAILABILITY CONSTRAINTS ⋮ A successive approximation algorithm for the multiple knapsack problem ⋮ Lens Spaces, Isospectral on Forms but not on Functions ⋮ Faster algorithms for \(k\)-subset sum and variations ⋮ The one-dimensional cutting stock problem with usable leftovers -- a survey

Cites Work

• Bin packing can be solved within 1+epsilon in linear time
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Integer Programming with a Fixed Number of Variables
• Unnamed Item

This page was built for publication: A PTAS for the multiple subset sum problem with different knapsack capacities