A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
From MaRDI portal
approximation algorithmgeneralized assignment problemmultiple knapsack problempolynomial time approximation scheme
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)
Recommendations
Cited in
(only showing first 100 items - show all)- A successive approximation algorithm for the multiple knapsack problem
- Market-based pricing in grids: on strategic manipulation and computational cost
- On the multiperiod binary knapsack problem
- Polynomial time approximation schemes for class-constrained packing problems
- A PTAS for the multiple subset sum problem with different knapsack capacities
- Knapsack with variable weights satisfying linear constraints
- Recovery strategies from major supply disruptions in single and multiple sourcing networks
- Distributed approximation of k-service assignment
- The packing while traveling problem
- Lift-and-project methods for set cover and knapsack
- Flexible allocation on related machines with assignment restrictions
- Approximation for multi-knapsack problem
- Minimum cost partitions of trees with supply and demand
- Approximation for knapsack problems with multiple constraints
- Improved online algorithms for knapsack and GAP in the random order model
- An almost optimal approximation algorithm for monotone submodular multiple knapsack
- Target-based computer-assisted orchestration: complexity and approximation algorithms
- Private non-monotone submodular maximization
- Learning-based multi-objective evolutionary algorithm for batching decision problem
- Approximation schemes for multiperiod binary knapsack problems
- Maximum coverage with cluster constraints: an LP-based approximation technique
- A polynomial-time approximation scheme for the MAXSPACE advertisement 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
- Two-machine flow shops with an optimal permutation schedule under a storage constraint
- A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
- On the approximability of the two-phase knapsack problem
- A polynomial-time approximation scheme for the airplane refueling problem
- 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
- Stochastic budget optimization in internet advertising
- A fast asymptotic approximation scheme for bin packing with rejection
- Upper and lower bounding procedures for the multiple knapsack assignment problem
- The generalized assignment problem with minimum quantities
- On Lagrangian relaxation for constrained maximization and reoptimization problems
- A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint
- Approximation algorithms for the generalized incremental knapsack problem
- The multiple subset sum problem
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- A deterministic polynomial-time approximation scheme for counting knapsack solutions
- Approximability of two variants of multiple knapsack problems
- Improved algorithmic results for unsplittable stable allocation problems
- Optimal interval scheduling with a resource constraint
- Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint
- Parameterized approximation scheme for the multiple knapsack problem
- On Lagrangian Relaxation and Subset Selection Problems
- A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
- scientific article; zbMATH DE number 3900493 (Why is no real title available?)
- A Note on Approximation Schemes for Multidimensional Knapsack Problems
- Approximation schemes for single machine scheduling with non-renewable resource constraints
- 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
- A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
- Two heuristic solution concepts for the vehicle selection problem in line haul transports
- scientific article; zbMATH DE number 1182767 (Why is no real title available?)
- A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
- Packing groups of items into multiple knapsacks
- Packing groups of items into multiple knapsacks
- Parameterized approximation scheme for the multiple knapsack problem
- scientific article; zbMATH DE number 6861894 (Why is no real title available?)
- scientific article; zbMATH DE number 1418266 (Why is no real title available?)
- scientific article; zbMATH DE number 1445306 (Why is no real title available?)
- Online submodular maximization with preemption
- Ranking with Fairness Constraints
- Generalized assignment via submodular optimization with reserved capacity
- A polynomial-time approximation scheme for sequential batch testing of series systems
- Technical note -- The multinomial logit model with sequential offerings: algorithmic frameworks for product recommendation displays
- Constrained submodular maximization via a nonsymmetric technique
- Two-agent advertisement scheduling on physical books to maximize the total profit
- A simple PTAS for the dual bin packing problem and advice complexity of its online version
- Truthful generalized assignments via stable matching
- Multiple subset sum with inclusive assignment set restrictions
- A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
- Improved Online Algorithms for Knapsack and GAP in the Random Order Model
- Approximation algorithms for scheduling with reservations
- scientific article; zbMATH DE number 7765369 (Why is no real title available?)
- Wireless IoT sensors data collection reward maximization by leveraging multiple energy- and storage-constrained UAVs
- Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
- Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints
- 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
- A distributed game theoretical approach for credibility-guaranteed multimedia data offloading in MEC
- Approximations for Throughput Maximization
- Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
- Approximation algorithms for the MAXSPACE advertisement problem
- Scheduling and packing under uncertainty
- Approximation algorithm for generalized budgeted assignment problems and applications in transportation systems
- Improved approximation for two-dimensional vector multiple knapsack
- Time-sharing scheduling with tolerance capacities
- Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
- Local-search based heuristics for advertisement scheduling
- An optimal algorithm for online multiple knapsack
- Lower bounds for matroid optimization problems with a linear constraint
- Generalized assignment and knapsack problems in the random-order model
- Approximating the geometric knapsack problem in near-linear time and dynamically
- An EPTAS for cardinality constrained multiple knapsack via iterative randomized rounding
- A fast algorithm for submodular maximization with a matroid constraint
- Improved approximation for two-dimensional vector multiple knapsack
- Approximation algorithms for round-UFP and round-SAP
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)
