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
- 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?)
- 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
- 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 Solution of Discrete Programming Problems
- On the efficiency of polynomial time approximation schemes
- 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
(22)- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 7559442 (Why is no real title available?)
- Optimizing some constructions with bars: new geometric knapsack problems
- The inverse-parametric knapsack problem
- A polyhedral study of the cardinality constrained knapsack problem
- Scheduling kernels via configuration LP
- Counting and enumerating independent sets with applications to combinatorial optimization problems
- Optimal Packing Problems: From Knapsack Problem to Open Dimension Problem
- Solutions of hard knapsack problems using extreme pruning
- Computational Science - ICCS 2004
- Comparing linear width parameters for directed graphs
- Computing partitions with applications to capital budgeting problems
- Parameterized approximation scheme for the multiple knapsack problem
- A multivariate complexity analysis of the generalized Noah's ark problem
- Parametric Solution for Linear Bicriteria Knapsack Models
- How can we maximize phylogenetic diversity? Parameterized approaches for networks
- An FPTAS for the knapsack problem with parametric weights
- A Knapsack Secretary Problem with Applications
- Reducing a target interval to a few exact queries
- Parameterized approximation scheme for the multiple knapsack problem
- Cooperative and axiomatic approaches to the knapsack allocation problem
- Some Complexity Issues In A Class Of Knapsack Problems: What Makes A Knapsack Problem “Hard”?
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)
