A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
From MaRDI portal
Publication:5470710
DOI10.1137/S0097539700382820zbMATH Open1095.68035DBLPjournals/siamcomp/ChekuriK05WikidataQ62002052 ScholiaQ62002052MaRDI QIDQ5470710FDOQ5470710
Authors: Chandra Chekuri, Sanjeev Khanna 
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
approximation algorithmgeneralized assignment problempolynomial time approximation schememultiple 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 (95)
- 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
- Distributed approximation of \(k\)-service assignment
- Packing groups of items into multiple knapsacks
- Learning-based multi-objective evolutionary algorithm for batching decision problem
- Constrained submodular maximization via a nonsymmetric technique
- Semi-definite relaxation algorithm of multiple knapsack 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
- A polynomial algorithm for the multiple knapsack problem with divisible item sizes
- Title not available (Why is that?)
- Approximation algorithms for scheduling with reservations
- Approximation schemes for knapsack problems with shelf divisions
- Truthful generalized assignments via stable matching
- Title not available (Why is that?)
- Polynomial time approximation schemes for class-constrained packing problems
- 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
- Packing groups of items into multiple knapsacks
- Improved online algorithms for knapsack and GAP in the random order model
- Minimum cost partitions of trees with supply and demand
- A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
- 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 simple PTAS for the dual bin packing problem and advice complexity of its online version
- Parameterized approximation scheme for the multiple knapsack 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
- Optimal interval scheduling with a resource constraint
- Title not available (Why is that?)
- Title not available (Why is that?)
- Two-machine flow shops with an optimal permutation schedule under a storage constraint
- The multiple subset sum problem
- 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
- Approximability of two variants of multiple knapsack problems
- Approximation for knapsack problems with multiple constraints
- A PTAS for the multiple subset sum problem with different knapsack capacities
- 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
- Two-agent advertisement scheduling on physical books to maximize the total profit
- A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- Upper and lower bounding procedures for the multiple knapsack assignment problem
- Online submodular maximization with preemption
- The packing while traveling problem
- Parameterized approximation scheme for the multiple knapsack 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
- Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines
- Improved Online Algorithms for Knapsack and GAP in the Random Order Model
- Ranking with Fairness Constraints
- Approximation algorithms for the MAXSPACE advertisement problem
- A polynomial-time approximation scheme for the MAXSPACE advertisement problem
- Approximation algorithms for capacitated assignment with budget constraints and applications in transportation systems
- A polynomial-time approximation scheme for sequential batch testing of series systems
- Scheduling and packing under uncertainty
- Scheduling multiple two-stage flowshops with a deadline
- Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint
- Technical note -- The multinomial logit model with sequential offerings: algorithmic frameworks for product recommendation displays
- 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
- A polynomial-time approximation scheme for the airplane refueling problem
- Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints
- A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
- Title not available (Why is that?)
- 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)
