Matroidal relaxations for 0-1 knapsack problems

DOI10.1016/0167-6377(93)90026-DMaRDI QIDQ1319682zbMATH OpenOpenAlexFDO

Authors Lígia Amado, Paulo Barcia

Publication date 12 April 1994

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(93)90026-d

zbMATH Keywords

matroidLagrangean relaxationindependence system

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Boolean programming (90C09)

Recommendations

• New polynomial bounds for matroidal knapsacks
• The matroidal knapsack: A class of (often) well-solvable problems
• Multi-constrained matroidal knapsack problems
• STRUCTURE OF OPTIMAL SOLUTIONS OF A KNAPSACK PROBLEM SUBJECT TO A GIVEN TOTAL NUMBER OF VARIABLES USED
• On the optimality of the greedy solutions of the general knapsack problems

Cites work

• Faces for a linear inequality in 0–1 variables
• Heuristic algorithms for the multiple knapsack problem
• The matroidal knapsack: A class of (often) well-solvable problems

Cited in

(7)

• Multi-constrained matroidal knapsack problems
• Maximum 4-block-free matrices and knapsack-type relaxations
• Revisiting \textit{Where are the hard knapsack problems?} via instance space analysis
• New polynomial bounds for matroidal knapsacks
• The matroidal knapsack: A class of (often) well-solvable problems
• scientific article; zbMATH DE number 847586 (Why is no real title available?)
• Knapsack polytopes: a survey

This page was built for publication: Matroidal relaxations for 0-1 knapsack problems

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