A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
From MaRDI portal
Publication:5470710
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)
Recommendations
Cited in
(only showing first 100 items - show all)- scientific article; zbMATH DE number 7525506 (Why is no real title available?)
- 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
- A fast algorithm for submodular maximization with a matroid constraint
- The generalized assignment problem with minimum quantities
- scientific article; zbMATH DE number 7765369 (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
- Coordinated scheduling of production and delivery with production window and delivery capacity constraints
- On the approximability of the two-phase knapsack problem
- 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
- Distributed approximation of k-service assignment
- Approximation algorithms for round-UFP and round-SAP
- Semi-definite relaxation algorithm of multiple knapsack problem
- Learning-based multi-objective evolutionary algorithm for batching decision problem
- Packing groups of items into multiple knapsacks
- Constrained submodular maximization via a nonsymmetric technique
- A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint
- A fast asymptotic approximation scheme for bin packing with rejection
- Approximation schemes for generalized two-dimensional vector packing with application to data placement
- A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
- Maximum coverage with cluster constraints: an LP-based approximation technique
- Multiple subset sum with inclusive assignment set restrictions
- Ranking with Fairness Constraints
- A polynomial algorithm for the multiple knapsack problem with divisible item sizes
- Approximation algorithms for the MAXSPACE advertisement problem
- Approximation schemes for knapsack problems with shelf divisions
- scientific article; zbMATH DE number 1445306 (Why is no real title available?)
- A polynomial-time approximation scheme for the MAXSPACE advertisement problem
- Approximation algorithms for scheduling with reservations
- Truthful generalized assignments via stable matching
- Polynomial time approximation schemes for class-constrained packing problems
- scientific article; zbMATH DE number 1182767 (Why is no real title available?)
- 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
- Approximate envy-freeness in indivisible resource allocation with budget constraints
- 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
- Improved online algorithms for knapsack and GAP in the random order model
- Packing groups of items into multiple knapsacks
- Minimum cost partitions of trees with supply and demand
- Scheduling multiple two-stage flowshops with a deadline
- Scheduling and packing under uncertainty
- A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem
- Stochastic budget optimization in internet advertising
- Greedy algorithms for stochastic monotone k-submodular maximization under full-bandit feedback
- Packing items into several bins facilitates approximating the separable assignment problem
- On Lagrangian Relaxation and Subset Selection Problems
- Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint
- Note on polynomial-time approximation schemes for integrated network design and scheduling problems
- Fair division of chores with budget constraints
- Technical note -- The multinomial logit model with sequential offerings: algorithmic frameworks for product recommendation displays
- A simple PTAS for the dual bin packing problem and advice complexity of its online version
- A successive approximation algorithm for the multiple knapsack problem
- Parameterized approximation scheme for the multiple knapsack problem
- Improved algorithmic results for unsplittable stable allocation problems
- Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
- An optimal algorithm for online multiple knapsack
- On Lagrangian relaxation for constrained maximization and reoptimization problems
- Optimal interval scheduling with a resource constraint
- scientific article; zbMATH DE number 3900493 (Why is no real title available?)
- 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
- Two-machine flow shops with an optimal permutation schedule under a storage constraint
- The multiple subset sum problem
- scientific article; zbMATH DE number 1418266 (Why is no real title available?)
- Lift-and-project methods for set cover and knapsack
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- Improved approximation for two-dimensional vector multiple knapsack
- A deterministic polynomial-time approximation scheme for counting knapsack solutions
- Flexible allocation on related machines with assignment restrictions
- Lower bounds for matroid optimization problems with a linear constraint
- Knapsack with variable weights satisfying linear constraints
- scientific article; zbMATH DE number 6861894 (Why is no real title available?)
- Generalized assignment and knapsack problems in the random-order model
- Market-based pricing in grids: on strategic manipulation and computational cost
- A distributed game theoretical approach for credibility-guaranteed multimedia data offloading in MEC
- Approximations for Throughput Maximization
- Approximation schemes for multiperiod binary knapsack problems
- Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
- Approximability of two variants of multiple knapsack problems
- Approximation for knapsack problems with multiple constraints
- A polynomial-time approximation scheme for the airplane refueling problem
- On the multiperiod binary knapsack problem
- A PTAS for the multiple subset sum problem with different knapsack capacities
- Approximating the geometric knapsack problem in near-linear time and dynamically
- Time-sharing scheduling with tolerance capacities
- Local-search based heuristics for advertisement scheduling
- A fast algorithm for maximizing a non-monotone DR-submodular integer lattice function
- Approximation algorithms for the generalized incremental knapsack problem
- Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
- An almost optimal approximation algorithm for monotone submodular multiple knapsack
- Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints
- Target-based computer-assisted orchestration: complexity and approximation algorithms
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)
