An FPTAS for the -modular multidimensional knapsack problem

DOI10.1007/978-3-030-77876-7_6MaRDI QIDQ2117618zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 22 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-77876-7_6

zbMATH Keywords

approximation algorithmFPTASmultidimensional knapsack problem\( \varDelta \)-modular integer linear programming\( \varDelta \)-modular matrix

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Integer programming (90C10)

Recommendations

• An FPTAS for the parametric knapsack problem
• An FPTAS for the knapsack problem with parametric weights
• An approximate dynamic programming approach to multidimensional knapsack problems
• A Practical Efficient Fptas for the 0-1 Multi-objective Knapsack Problem
• Implementing an efficient fptas for the 0-1 multi-objective knapsack problem
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• Publication:4952619
• Some new results on multi-dimension Knapsack problem
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Improved dynamic programming in connection with an FPTAS for the knapsack problem

Cites work

• scientific article; zbMATH DE number 3850828 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 1342145 (Why is no real title available?)
• scientific article; zbMATH DE number 6850361 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 7561569 (Why is no real title available?)
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem
• A strongly polynomial algorithm for bimodular integer linear programming
• An FPTAS for the knapsack problem with parametric weights
• An FPTAS for the parametric knapsack problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Dynamic programming revisited: Improving knapsack algorithms
• FPT-algorithms for some problems related to integer programming
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Improving proximity bounds using sparsity
• Introduction to algorithms.
• Linear time algorithms for some separable quadratic programming problems
• On largest volume simplices and sub-determinants
• On the complexity of integer programming
• On the minors of an incidence matrix and Smith normal form
• On the optimality of pseudo-polynomial algorithms for integer programming
• Solving the stable set problem in terms of the odd cycle packing number
• The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
• The computational complexity of three graph problems for instances with bounded minors of constraint matrices
• The stable set problem in graphs with bounded genus and bounded odd cycle packing number
• There is no EPTAS for two-dimensional knapsack
• Tight complexity lower bounds for integer linear programming with few constraints

Cited in

(3)

• Advances on strictly \(\varDelta \)-modular IPs
• Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
• There is no EPTAS for two-dimensional knapsack

Describes a project that uses

Uses Software

• Knapsack

This page was built for publication: An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117618)