A Fast Approximation Scheme for the Multiple Knapsack Problem

DOI10.1007/978-3-642-27660-6_26zbMath1302.90183OpenAlexW2167596143MaRDI QIDQ2891378

Klaus Jansen

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://macau.uni-kiel.de/receive/macau_mods_00001844

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (10)

Scheduling multiple two-stage flowshops with a deadline ⋮ Scheduling on multiple two-stage flowshops with a deadline ⋮ A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint ⋮ Knapsack problems: a parameterized point of view ⋮ Wireless IoT sensors data collection reward maximization by leveraging multiple energy- and storage-constrained UAVs ⋮ Unnamed Item ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ Bounding the Running Time of Algorithms for Scheduling and Packing Problems ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Approximation schemes for multiperiod binary knapsack problems

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem
• The Multiple Subset Sum Problem
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Parameterized Approximation Scheme for the Multiple Knapsack Problem
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: A Fast Approximation Scheme for the Multiple Knapsack Problem