Matroidal relaxations for 0-1 knapsack problems

DOI10.1016/0167-6377(93)90026-DzbMATH Open0802.90076OpenAlexW1995917458MaRDI QIDQ1319682FDOQ1319682

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

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

zbMATH Keywords

matroidLagrangean relaxationindependence system

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Maximum 4-block-free matrices and knapsack-type relaxations
• The matroidal knapsack: A class of (often) well-solvable problems
• Knapsack polytopes: a survey
• New polynomial bounds for matroidal knapsacks
• Revisiting \textit{where are the hard knapsack problems?} Via instance space analysis
• Multi-constrained matroidal knapsack problems
• Title not available (Why is that?)

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)