A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

DOI10.1137/S0097539700382820zbMath1095.68035DBLPjournals/siamcomp/ChekuriK05WikidataQ62002052 ScholiaQ62002052MaRDI QIDQ5470710

Chandra Chekuri, Sanjeev Khanna

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

generalized assignment problemapproximation algorithmpolynomial time approximation schememultiple knapsack problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (64)

A Fast Approximation Scheme for the Multiple Knapsack Problem ⋮ A polynomial-time approximation scheme for the MAXSPACE advertisement problem ⋮ Scheduling multiple two-stage flowshops with a deadline ⋮ 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 ⋮ Scheduling on multiple two-stage flowshops with a deadline ⋮ Optimal interval scheduling with a resource constraint ⋮ A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem ⋮ Stochastic budget optimization in internet advertising ⋮ A Polynomial-Time Approximation Scheme for Sequential Batch Testing of Series Systems ⋮ On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint ⋮ Knapsack with variable weights satisfying linear constraints ⋮ Approximation schemes for single machine scheduling with non-renewable resource constraints ⋮ Minimum cost partitions of trees with supply and demand ⋮ Wireless IoT sensors data collection reward maximization by leveraging multiple energy- and storage-constrained UAVs ⋮ Technical Note—The Multinomial Logit Model with Sequential Offerings: Algorithmic Frameworks for Product Recommendation Displays ⋮ Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints ⋮ Constrained Submodular Maximization via a Nonsymmetric Technique ⋮ Approximation schemes for generalized two-dimensional vector packing with application to data placement ⋮ Coordinated scheduling of production and delivery with production window and delivery capacity constraints ⋮ Approximation algorithms for the generalized incremental knapsack problem ⋮ Two-machine flow shops with an optimal permutation schedule under a storage constraint ⋮ Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines ⋮ Approximation algorithms for capacitated assignment with budget constraints and applications in transportation systems ⋮ Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint ⋮ A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function ⋮ Two heuristic solution concepts for the vehicle selection problem in line haul transports ⋮ Unnamed Item ⋮ Recovery strategies from major supply disruptions in single and multiple sourcing networks ⋮ A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version ⋮ Partitioning a weighted partial order ⋮ Approximation schemes for deal splitting and covering integer programs with multiplicity constraints ⋮ Distributed approximation of \(k\)-service assignment ⋮ Improved Online Algorithms for Knapsack and GAP in the Random Order Model ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ Ranking with Fairness Constraints ⋮ The packing while traveling problem ⋮ A fast asymptotic approximation scheme for bin packing with rejection ⋮ Unnamed Item ⋮ On Lagrangian Relaxation and Subset Selection Problems ⋮ On the approximability of the two-phase knapsack problem ⋮ Improved online algorithms for Knapsack and GAP in the random order model ⋮ Approximation algorithms for scheduling with reservations ⋮ Upper and lower bounding procedures for the multiple knapsack assignment problem ⋮ Lift-and-project methods for set cover and knapsack ⋮ Flexible allocation on related machines with assignment restrictions ⋮ Online Submodular Maximization with Preemption ⋮ Two-Agent Advertisement Scheduling on Physical Books to Maximize the Total Profit ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ A successive approximation algorithm for the multiple knapsack problem ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Target-based computer-assisted orchestration: complexity and approximation algorithms ⋮ A polynomial-time approximation scheme for the airplane refueling problem ⋮ Truthful Generalized Assignments via Stable Matching ⋮ Market-based pricing in grids: on strategic manipulation and computational cost ⋮ Private non-monotone submodular maximization ⋮ Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem ⋮ Packing items into several bins facilitates approximating the separable assignment problem ⋮ Learning-based multi-objective evolutionary algorithm for batching decision problem ⋮ The generalized assignment problem with minimum quantities ⋮ Approximation schemes for multiperiod binary knapsack problems ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique

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