Multi-constrained matroidal knapsack problems

DOI10.1007/BF01589104zbMath0682.90074MaRDI QIDQ1824560

Francesco Maffioli, Carlo Vercellis, Paolo M. Camerini

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

approximate solutionsLagrangean relaxationcombinatorial constraints of matroidal naturemulti-constrained knapsack problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (8)

Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms ⋮ Using sparsification for parametric minimum spanning tree problems ⋮ Linear-time algorithms for parametric minimum spanning tree problems on planar graphs ⋮ Decomposable multi-parameter matroid optimization problems. ⋮ In memoriam Paolo M. Camerini ⋮ Note on combinatorial optimization with max-linear objective functions ⋮ Stochastic on-line knapsack problems ⋮ Linear-time algorithms for parametric minimum spanning tree problems on planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The matroidal knapsack: A class of (often) well-solvable problems
• Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems
• A computational study of a multiple-choice knapsack algorithm
• Integer Programming Models for Sales Resource Allocation
• A mathematical programming system for preference and compatibility maximized menu planning and scheduling
• The Traveling-Salesman Problem and Minimum Spanning Trees

This page was built for publication: Multi-constrained matroidal knapsack problems