New polynomial bounds for matroidal knapsacks

DOI10.1016/0377-2217(95)00248-0MaRDI QIDQ1278377zbMATH OpenOpenAlexFDO

Authors Lígia Amado, Paulo Barcia

Publication date 22 February 1999

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(95)00248-0

zbMATH Keywords

matroidal knapsackrelaxationmatroids

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• Matroidal relaxations for 0-1 knapsack problems
• The matroidal knapsack: A class of (often) well-solvable problems
• Multi-constrained matroidal knapsack problems
• A new upper bound for the multiple knapsack problem

Cites work

• Matroidal relaxations for 0-1 knapsack problems
• Ordered matroids and regular independence systems
• The matroidal knapsack: A class of (often) well-solvable problems

Cited in

(6)

• Implicit cover inequalities
• Matroidal relaxations for 0-1 knapsack problems
• The matroidal knapsack: A class of (often) well-solvable problems
• A new upper bound for the multiple knapsack problem
• scientific article; zbMATH DE number 729909 (Why is no real title available?)
• An improved FPTAS for budgeted laminar matroid independent set

This page was built for publication: New polynomial bounds for matroidal knapsacks

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