×

The quadratic 0-1 knapsack problem with series-parallel support. (English) Zbl 1010.90067

Summary: We consider various special cases of the quadratic 0-1 knapsack problem (QKP) for which the underlying graph structure is fairly simple. For the variant with edge series–parallel graphs, we give a dynamic programming algorithm with pseudo-polynomial time complexity, and a fully polynomial time approximation scheme. In strong contrast to this, the variant with vertex series–parallel graphs is shown to be strongly NP-complete.

MSC:

90C27 Combinatorial optimization
90C39 Dynamic programming
90C59 Approximation methods and heuristics in mathematical programming
65Y20 Complexity and performance of numerical algorithms

Software:

Knapsack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Billionnet, Maximizing a quadratic tree-structured pseudo-boolean function with a cardinality constraint, Manuscript.; A. Billionnet, Maximizing a quadratic tree-structured pseudo-boolean function with a cardinality constraint, Manuscript.
[2] Billionnet, A.; Calmels, F., Linear programming for the 0-1 quadratic knapsack problem, Eur. J. Oper. Res., 92, 310-325 (1996) · Zbl 0912.90221
[3] Billionnet, A.; Faye, A.; Soutif, E., A new upper-bound for the 0-1 quadratic knapsack problem, Eur. J. Oper. Res., 112, 664-672 (1999) · Zbl 0933.90049
[4] Caprara, A.; Pisinger, D.; Toth, P., Exact solution of the quadratic knapsack problem, INFORMS J. Comput., 11, 125-137 (1999) · Zbl 1034.90521
[5] P. Chaillou, P. Hansen, Y. Mahieu, Best Network Flow Bounds for the Quadratic Knapsack Problem, Lecture Notes in Mathematics, Vol. 1403, Springer, New York, 1986, pp. 226-235.; P. Chaillou, P. Hansen, Y. Mahieu, Best Network Flow Bounds for the Quadratic Knapsack Problem, Lecture Notes in Mathematics, Vol. 1403, Springer, New York, 1986, pp. 226-235. · Zbl 0678.90061
[6] Duffin, R. J., Topology of series-parallel networks, J. Math. Anal. Appl., 10, 303-318 (1965) · Zbl 0128.37002
[7] Gallo, G.; Hammer, P. L.; Simeone, B., Quadratic knapsack problems, Math. Prog., 12, 132-149 (1980) · Zbl 0462.90068
[8] Gallo, G.; Simeone, S., On the supermodular knapsack problem, Math. Prog., 45, 295-309 (1988) · Zbl 0682.90063
[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] Hammer, P. L.; Rader, D. J., Efficient methods for solving quadratic 0-1 knapsack problems, INFOR, 35, 170-182 (1997) · Zbl 0888.90121
[11] C. Helmberg, F. Rendl, R. Weismantel, Quadratic knapsack relaxations using cutting planes and semidefinite programming, Lecture Notes in Computer Science, Vol. 1084, Springer, Berlin, 1996, pp. 175-189.; C. Helmberg, F. Rendl, R. Weismantel, Quadratic knapsack relaxations using cutting planes and semidefinite programming, Lecture Notes in Computer Science, Vol. 1084, Springer, Berlin, 1996, pp. 175-189. · Zbl 1415.90073
[12] Ibarra, O.; Kim, C. E., Fast approximation algorithms for the knapsack and sum of subset problems, J. ACM, 22, 463-468 (1975) · Zbl 0345.90049
[13] Johnson, E. L.; Mehrotra, A.; Nemhauser, G. L., Min-cut clustering, Math. Prog., 62, 133-151 (1993) · Zbl 0807.90117
[14] Lawler, E. L., Fast approximation schemes for knapsack problems, Math. Oper. Res., 4, 339-356 (1979) · Zbl 0425.90064
[15] Michelon, P.; Veilleux, L., Lagrangean methods for the 0-1 quadratic knapsack problem, European J. Oper. Res., 92, 326-341 (1996) · Zbl 0912.90222
[16] D.J. Rader, Valid inequalities and facets of the quadratic 0-1 knapsack polytope, RUTCOR Research Report 16-97, RUTCOR, Rutgers University, 1997.; D.J. Rader, Valid inequalities and facets of the quadratic 0-1 knapsack polytope, RUTCOR Research Report 16-97, RUTCOR, Rutgers University, 1997.
[17] Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM, 29, 623-641 (1982) · Zbl 0485.68055
[18] Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series-parallel digraphs, SIAM J. Comput., 11, 298-313 (1982) · Zbl 0478.68065
[19] C. Witzgall, Mathematical methods of site selection for electronic message systems (EMS), NBS Internal Report, 1975.; C. Witzgall, Mathematical methods of site selection for electronic message systems (EMS), NBS Internal Report, 1975.
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.