×

The matroidal knapsack: A class of (often) well-solvable problems. (English) Zbl 0544.90074

Summary: A general class of problems, defined in terms of matroids, is recognized to include as special cases a variety of knapsack problems, subject to combinatorial constraints. A polynomial algorithm, based on Lagrangean relaxation, is proposed: A worst case and a probabilistic analysis demonstrate its ability to compute tight upper and lower bounds for the optimum, together with good approximate solutions.

MSC:

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

References:

[1] Anderson, C. W., Extreme value theory for a class of discrete distributions with applications to some stochastic processes, J. Appl. Probability, 7, 99-113 (1970) · Zbl 0192.54202
[2] Armstrong, R. D.; Kung, D. S.; Sinha, P.; Zoltners, A. A., A computational study of a multiple-choice knapsack algorithm, ACM Transactions on Mathematical Software, 9, 184-198 (1983) · Zbl 0512.68029
[3] Ausiello, G.; Marchetti, A.; Protasi, M., Probabilistic analysis of the solution of the knapsack problem, (Drenick, R. F.; Kozin, F., System Modeling and Optimization (1982), Springer: Springer Berlin), 557-565 · Zbl 0497.90043
[4] T. Brylawski, “Constructions”, in: H. Crapo, G.C. Rota and N. White, eds., Combinatorial Geometries; T. Brylawski, “Constructions”, in: H. Crapo, G.C. Rota and N. White, eds., Combinatorial Geometries · Zbl 0596.05013
[5] P.M. Camerini, G. Galbiati and F. Maffioli, “Complexity of spanning tree problems, part II”, to appear.; P.M. Camerini, G. Galbiati and F. Maffioli, “Complexity of spanning tree problems, part II”, to appear. · Zbl 0445.90088
[6] D’Atri, G., Probabilistic analysis of the knapsack problem, (T.R. 7, Groupe de Recherche 22 (1978), Centre National de la Recherche Scientifique: Centre National de la Recherche Scientifique Paris)
[7] M.A.H. Dempster, M.L. Fisher, L. Jansen, B.J. Lageweg, J.K. Lenstra and A.H.G. Rinnooy Kan, “Analysis of heuristics for stochastic programming: Results for hierarchical scheduling problems”, to appear in Mathematics of Operations Research; M.A.H. Dempster, M.L. Fisher, L. Jansen, B.J. Lageweg, J.K. Lenstra and A.H.G. Rinnooy Kan, “Analysis of heuristics for stochastic programming: Results for hierarchical scheduling problems”, to appear in Mathematics of Operations Research · Zbl 0532.90078
[8] Galambos, J., The Asymptotic Theory of Extreme Order Statistics (1978), Wiley: Wiley New York · Zbl 0381.62039
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[10] Gerla, M., The design of store-and-forward (S/F) networks for computer communications, (Report UCLA-ENG-7319 (1973), University of California: University of California Los Angeles)
[11] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York · Zbl 0358.68059
[12] Lawler, E. L., Fast approximation algorithms for knapsack problems, Math. Oper. Res., 4, 339-356 (1979) · Zbl 0425.90064
[13] Lucker, G. S., On the average difference between the solutions to linear and integer knapsack problems, (T.R. 152 (1980), Department of Information and Computer Science, Univ. of California: Department of Information and Computer Science, Univ. of California Irvine)
[14] Sihna, P.; Zoltners, A. A., The multiple-choice knapsack problem, Operations Research, 27, 503-515 (1979) · Zbl 0406.90052
[15] Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press London · Zbl 0343.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.