The matroidal knapsack: A class of (often) well-solvable problems

DOI10.1016/0167-6377(84)90009-9zbMath0544.90074OpenAlexW2395553881MaRDI QIDQ797497

Paolo M. Camerini, Carlo Vercellis

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0167-6377(84)90009-9

zbMATH Keywords

approximate solutionsLagrangean relaxationprobabilistic analysisupper and lower boundspolynomial algorithmworst case analysiscombinatorial constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (10)

Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach ⋮ Implicit cover inequalities ⋮ A discussion of scalarization techniques for multiple objective integer programming ⋮ Constrained matroidal bottleneck problems ⋮ On matroids with multiple objectives ⋮ In memoriam Paolo M. Camerini ⋮ Note on combinatorial optimization with max-linear objective functions ⋮ New polynomial bounds for matroidal knapsacks ⋮ Multi-constrained matroidal knapsack problems ⋮ Matroidal relaxations for 0-1 knapsack problems

Cites Work

• Complexity of spanning tree problems: Part I
• Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
• A computational study of a multiple-choice knapsack algorithm
• Fast Approximation Algorithms for Knapsack Problems
• The Multiple-Choice Knapsack Problem
• Extreme value theory for a class of discrete distributions with applications to some stochastic processes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The matroidal knapsack: A class of (often) well-solvable problems