An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
From MaRDI portal
Publication:2117618
DOI10.1007/978-3-030-77876-7_6zbMath1487.90550OpenAlexW3191592804MaRDI QIDQ2117618
Publication date: 22 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-77876-7_6
approximation algorithmFPTASmultidimensional knapsack problem\( \varDelta \)-modular integer linear programming\( \varDelta \)-modular matrix
Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
Advances on strictly \(\varDelta \)-modular IPs ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear time algorithms for some separable quadratic programming problems
- There is no EPTAS for two-dimensional knapsack
- A fully polynomial approximation algorithm for the 0-1 knapsack problem
- A new fully polynomial time approximation scheme for the Knapsack problem
- Approximation algorithms for knapsack problems with cardinality constraints
- The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
- A faster FPTAS for the unbounded knapsack problem
- FPT-algorithms for some problems related to integer programming
- Improved dynamic programming in connection with an FPTAS for the knapsack problem
- On the minors of an incidence matrix and Smith normal form
- Dynamic programming revisited: Improving knapsack algorithms
- Improving proximity bounds using sparsity
- An FPTAS for the knapsack problem with parametric weights
- The computational complexity of three graph problems for instances with bounded minors of constraint matrices
- An FPTAS for the parametric knapsack problem
- Solving the stable set problem in terms of the odd cycle packing number
- Fast Approximation Algorithms for Knapsack Problems
- On the complexity of integer programming
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- A strongly polynomial algorithm for bimodular integer linear programming
- On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
- Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
- The stable set problem in graphs with bounded genus and bounded odd cycle packing number
- On largest volume simplices and sub-determinants
