A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem

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

Cited In (81)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470710)