New polynomial bounds for matroidal knapsacks

Lígia Amado, Paulo Bárcia

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

The Matroidal Knapsack Problem (MK) consists in finding the maximum weight basis for a given matroid subject to a knapsack constraint. Special cases of this problem are the Multiple Choice Knapsack and the Capacitated Minimal Spanning Tree Problems. Using matroidal relaxations for knapsack problems we build a relaxation for MK. This relaxation produces an upper bound on MK dominating the usual LP-bound and computable using a polynomial number of calls to the greedy algorithm for the matroid.

Original languageEnglish
Pages (from-to)201-210
Number of pages10
JournalEuropean Journal of Operational Research
Volume95
Issue number1
DOIs
Publication statusPublished - 22 Nov 1996

Keywords

  • Matroidal knapsack
  • Matroids
  • Relaxation

Fingerprint Dive into the research topics of 'New polynomial bounds for matroidal knapsacks'. Together they form a unique fingerprint.

Cite this