Knapsack problems: a parameterized point of view
From MaRDI portal
Publication:2419116
DOI10.1016/j.tcs.2018.12.019zbMath1422.68113arXiv1611.07724OpenAlexW2963464899WikidataQ128680437 ScholiaQ128680437MaRDI QIDQ2419116
Frank Gurski, Jochen Rethmann, Carolin Rehs
Publication date: 29 May 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.07724
knapsack problemparameterized complexitykernelizationmultiple knapsack problem\(d\)-dimensional knapsack problem
Related Items
Unnamed Item ⋮ Comparing linear width parameters for directed graphs ⋮ Counting and enumerating independent sets with applications to combinatorial optimization problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- Polynomial kernels for weighted problems
- Fundamentals of parameterized complexity
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Parameterizing by the number of numbers
- There is no EPTAS for two-dimensional knapsack
- Polynomial time approximation schemes and parameterized complexity
- Data reductions and combinatorial bounds for improved approximation algorithms
- An application of simultaneous diophantine approximation in combinatorial optimization
- On fixed-parameter tractability and approximability of NP optimization problems
- Which problems have strongly exponential complexity?
- Change-making problems revisited: a parameterized point of view
- Parametrized complexity theory.
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- Reducing a Target Interval to a Few Exact Queries
- Integer Programming with a Fixed Number of Variables
- Reflections on Multivariate Algorithmics and Problem Parameterization
- On the Solution of Discrete Programming Problems
- 50 Years of Integer Programming 1958-2008
- Kernelization: New Upper and Lower Bound Techniques
- Minkowski's Convex Body Theorem and Integer Programming
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Fixed-Parameter Tractability and Completeness I: Basic Results
