An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
type: Item
instance of: scholarly article
title: An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
zbMATH Open document ID: 1487.90550
DOI: 10.1007/978-3-030-77876-7_6
author: Yanyan Li
publication date: 2022-03-22T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7495073
zbMATH Keywords: multidimensional knapsack problem
zbMATH Keywords: \( \varDelta \)-modular integer linear programming
zbMATH Keywords: FPTAS
zbMATH Keywords: \( \varDelta \)-modular matrix
zbMATH Keywords: approximation algorithm
describes a project that uses: Knapsack
MaRDI profile type: Publication
full work available at URL: 978-3-030-77876-7 6
OpenAlex ID: W3191592804
cites work: A strongly polynomial algorithm for bimodular integer linear programming
cites work: Solving the stable set problem in terms of the odd cycle packing number
cites work: Approximation algorithms for knapsack problems with cardinality constraints
cites work: Q5240419
cites work: The stable set problem in graphs with bounded genus and bounded odd cycle packing number
cites work: Q3651735
cites work: On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
cites work: Q4607934
cites work: The computational complexity of three graph problems for instances with bounded minors of constraint matrices
cites work: The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
cites work: FPT-algorithms for some problems related to integer programming
cites work: On the minors of an incidence matrix and Smith normal form
cites work: An FPTAS for the knapsack problem with parametric weights
cites work: An FPTAS for the parametric knapsack problem
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: A faster FPTAS for the unbounded knapsack problem
cites work: Q5091235
cites work: A new fully polynomial time approximation scheme for the Knapsack problem
cites work: Improved dynamic programming in connection with an FPTAS for the knapsack problem
cites work: Q4821303
cites work: Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
cites work: Q3320130
cites work: There is no EPTAS for two-dimensional knapsack
cites work: Fast Approximation Algorithms for Knapsack Problems
cites work: Improving proximity bounds using sparsity
cites work: A fully polynomial approximation algorithm for the 0-1 knapsack problem
cites work: Linear time algorithms for some separable quadratic programming problems
cites work: On the complexity of integer programming
cites work: Dynamic programming revisited: Improving knapsack algorithms
cites work: Q4221106
cites work: Q4263727
cites work: On largest volume simplices and sub-determinants
Recommended article: An FPTAS for the parametric knapsack problem
Recommended article: An FPTAS for the knapsack problem with parametric weights
Recommended article: An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems
Recommended article: A Practical Efficient Fptas for the 0-1 Multi-objective Knapsack Problem
Recommended article: Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
Recommended article: A Note on Approximation Schemes for Multidimensional Knapsack Problems
Recommended article: Q4952619
Recommended article: Some new results on multi-dimension Knapsack problem
Recommended article: The multidimensional 0-1 knapsack problem -- bounds and computational aspects
Recommended article: Improved dynamic programming in connection with an FPTAS for the knapsack problem
description: scientific article; zbMATH DE number 7495073