Publicação
Greedy Solvable Knapsacks
| dc.contributor.author | Amado, Lígia | |
| dc.contributor.author | Bárcia, Paulo | |
| dc.date.accessioned | 2019-10-25T11:35:13Z | |
| dc.date.available | 2019-10-25T11:35:13Z | |
| dc.date.issued | 1991-08 | |
| dc.description.abstract | The family K of the feasible solutions for a 0-1 Knapsack with positive coefficients, K={l⊂N:Σi∈Iai≤b}, is an independence system over N={1,...,n}. In some cases, for instance when all the ai have the same value, this independence system is a matroid over N. We will say then that the knapsack is greedy solvable. In this paper We study the conditions for a knapsack to be greedy solvable. We present necessary and sufficient conditions, verifiable in polynomial time, for K to be a member of a finite family of matroids over N. | pt_PT |
| dc.description.version | N/A | pt_PT |
| dc.identifier.citation | Amado, Lígia and Bárcia, Paulo, Greedy Solvable Knapsacks (August, 1991). FEUNL Working Paper Series No. 174 | pt_PT |
| dc.identifier.uri | http://hdl.handle.net/10362/85388 | |
| dc.language.iso | eng | pt_PT |
| dc.peerreviewed | no | pt_PT |
| dc.publisher | Nova SBE | pt_PT |
| dc.relation.ispartofseries | FEUNL Working Paper Series;174 | |
| dc.subject | 0-1 Knapsacks | pt_PT |
| dc.subject | Matroids | pt_PT |
| dc.title | Greedy Solvable Knapsacks | pt_PT |
| dc.type | working paper | |
| dspace.entity.type | Publication | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | workingPaper | pt_PT |