A successive approximation algorithm for the multiple knapsack problem

DOI10.1007/s10878-007-9116-yzbMath1180.90279OpenAlexW2122137596MaRDI QIDQ1029265

Zhen-bo Wang, Wen-Xun Xing

Publication date: 10 July 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9116-y

zbMATH Keywords

approximation algorithmworst-case analysismultiple knapsack problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Knapsack with variable weights satisfying linear constraints ⋮ Two-group knapsack game

Uses Software

• Knapsack
• MULKNAP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact algorithm for large multiple knapsack problems
• A bound and bound algorithm for the zero-one multiple knapsack problem
• An upper bound for the zero-one knapsack problem and a branch and bound algorithm
• A new fully polynomial time approximation scheme for the Knapsack problem
• A 3/4-approximation algorithm for multiple subset sum
• Worst-case analysis of the subset sum algorithm for bin packing.
• New trends in exact algorithms for the \(0-1\) knapsack problem
• A PTAS for the multiple subset sum problem with different knapsack capacities
• The Multiple Subset Sum Problem
• Fast Approximation Algorithms for Knapsack Problems
• Computing Partitions with Applications to the Knapsack Problem
• An Efficient Algorithm for the 0-1 Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

This page was built for publication: A successive approximation algorithm for the multiple knapsack problem