PORTUGALIAE<br />MATHEMATICA, Vol. 52, No. 4, pp. 475-480, 1995

PORTUGALIAE
MATHEMATICA
Vol. 52, No. 4, pp. 475-480 (1995)

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home

EMIS Home

When is a 0-1 Knapsack a Matroid?

J. Orestes Cerdeira and Paulo Barcia

Departamento de Matemática, Instituto Superior de Agronomia,
Tapada da Ajuda, 1399 Lisboa Codex - PORTUGAL
E-mail: orestes@isa.utl.pt Universidade Nova de Lisboa, Faculdade de Economia,
Travessa Estev\ ao Pinto, Campolide, 1000 Lisboa - PORTUGAL
E-mail: barcia@fe.unl.pt

Abstract: We give a polynomial time algorithm for deciding whether the set of solutions of a 0-1 knapsack is a matroid.

Keywords: 0-1 knapsack; matroids; subset sum problem.

Full text of the article:

Compressed PostScript file (56 kilobytes)
PDF file (108 kilobytes)

Electronic version published on: 29 Mar 2001. This page was last modified: 27 Nov 2007.

© 1995 Sociedade Portuguesa de Matemática
© 1995–2007 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition