An FPTAS for the -modular multidimensional knapsack problem

DOI10.1007/978-3-030-77876-7_6zbMATH Open1487.90550OpenAlexW3191592804MaRDI QIDQ2117618FDOQ2117618

Authors: Yanyan Li 

Publication date: 22 March 2022

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

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

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)

Cites Work

• Title not available (Why is that?)
• Introduction to algorithms.
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Title not available (Why is that?)
• Approximation algorithms for knapsack problems with cardinality constraints
• On the complexity of integer programming
• Title not available (Why is that?)
• Linear time algorithms for some separable quadratic programming problems
• A new fully polynomial time approximation scheme for the Knapsack problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Dynamic programming revisited: Improving knapsack algorithms
• There is no EPTAS for two-dimensional knapsack
• Title not available (Why is that?)
• On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
• The computational complexity of three graph problems for instances with bounded minors of constraint matrices
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
• On the minors of an incidence matrix and Smith normal form
• Title not available (Why is that?)
• Improving proximity bounds using sparsity
• An FPTAS for the parametric knapsack problem
• Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
• On largest volume simplices and sub-determinants
• A strongly polynomial algorithm for bimodular integer linear programming
• A faster FPTAS for the unbounded knapsack problem
• FPT-algorithms for some problems related to integer programming
• Solving the stable set problem in terms of the odd cycle packing number
• The stable set problem in graphs with bounded genus and bounded odd cycle packing number
• Title not available (Why is that?)
• An FPTAS for the knapsack problem with parametric weights
• Title not available (Why is that?)

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

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)