Knapsack problems: a parameterized point of view
From MaRDI portal
Abstract: The knapsack problem (KP) is a very famous NP-hard problem in combinatorial optimization. Also its generalization to multiple dimensions named d-dimensional knapsack problem (d-KP) and to multiple knapsacks named multiple knapsack problem (MKP) are well known problems. Since KP, d-KP, and MKP are integer-valued problems defined on inputs of various informations, we study the fixed-parameter tractability of these problems. The idea behind fixed-parameter tractability is to split the complexity into two parts - one part that depends purely on the size of the input, and one part that depends on some parameter of the problem that tends to be small in practice. Further we consider the closely related question, whether the sizes and the values can be reduced, such that their bit-length is bounded polynomially or even constantly in a given parameter, i.e. the existence of kernelizations is studied. We discuss the following parameters: the number of items, the threshold value for the profit, the sizes, the profits, the number d of dimensions, and the number m of knapsacks. We also consider the connection of parameterized knapsack problems to linear programming, approximation, and pseudo-polynomial algorithms.
Recommendations
Cites work
- 50 Years of Integer Programming 1958-2008
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- An application of simultaneous diophantine approximation in combinatorial optimization
- Change-making problems revisited: a parameterized point of view
- Data reductions and combinatorial bounds for improved approximation algorithms
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1302173 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- Improved bounds on Bell numbers and on moments of sums of random variables
- Integer Programming with a Fixed Number of Variables
- Kernelization: new upper and lower bound techniques
- Minkowski's Convex Body Theorem and Integer Programming
- On fixed-parameter tractability and approximability of NP optimization problems
- On the efficiency of polynomial time approximation schemes
- On the Solution of Discrete Programming Problems
- Parametrized complexity theory.
- Polynomial time approximation schemes and parameterized complexity
- Reducing a target interval to a few exact queries
- Reflections on multivariate algorithmics and problem parameterization
- There is no EPTAS for two-dimensional knapsack
- Which problems have strongly exponential complexity?
Cited in
(23)- The inverse-parametric knapsack problem
- A polyhedral study of the cardinality constrained knapsack problem
- Solutions of hard knapsack problems using extreme pruning
- Cooperative and axiomatic approaches to the knapsack allocation problem
- An FPTAS for the knapsack problem with parametric weights
- Comparing linear width parameters for directed graphs
- Optimizing some constructions with bars: new geometric knapsack problems
- Reducing a target interval to a few exact queries
- Parameterized approximation scheme for the multiple knapsack problem
- A Knapsack Secretary Problem with Applications
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- Some Complexity Issues In A Class Of Knapsack Problems: What Makes A Knapsack Problem “Hard”?
- Parametric Solution for Linear Bicriteria Knapsack Models
- Computing partitions with applications to capital budgeting problems
- Parameterized approximation scheme for the multiple knapsack problem
- scientific article; zbMATH DE number 7559442 (Why is no real title available?)
- Optimal Packing Problems: From Knapsack Problem to Open Dimension Problem
- Computational Science - ICCS 2004
- A multivariate complexity analysis of the generalized Noah's ark problem
- How can we maximize phylogenetic diversity? Parameterized approaches for networks
- Scheduling kernels via configuration LP
- The parameterized complexity of scheduling with precedence delays: shuffle product and directed bandwidth
- Counting and enumerating independent sets with applications to combinatorial optimization problems
This page was built for publication: Knapsack problems: a parameterized point of view
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419116)
