Parameterized Approximation Scheme for the Multiple Knapsack Problem
From MaRDI portal
Publication:3586185
DOI10.1137/080731207zbMath1211.68276OpenAlexW2085922444MaRDI QIDQ3586185
Publication date: 6 September 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://macau.uni-kiel.de/servlets/MCRFileNodeServlet/macau_derivate_00002986/tr-0909-bericht.pdf
Linear programming (90C05) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items (17)
A Fast Approximation Scheme for the Multiple Knapsack Problem ⋮ Scheduling multiple two-stage flowshops with a deadline ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Scheduling on multiple two-stage flowshops with a deadline ⋮ A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem ⋮ Stochastic budget optimization in internet advertising ⋮ Approximate composable truthful mechanism design ⋮ Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Minimum cost partitions of trees with supply and demand ⋮ Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ On the approximability of the two-phase knapsack problem ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack
Uses Software
This page was built for publication: Parameterized Approximation Scheme for the Multiple Knapsack Problem
