A Dynamic Programming Heuristic for the Quadratic Knapsack Problem

References

• Balas E, Zemel E (1980) An algorithm for large zero-one knapsack problems. Oper. Res. 28:1130–1154.Link, Google Scholar
• Bellman RE (1957) Exact Solution of the Quadratic Knapsack Problem (Princeton University Press, Princeton, NJ).Google Scholar
• Bhaskara A, Charikar M, Chlamtac E, Feige U, Vijayaraghavan A, eds. (2010) Detecting high log-densities: An 𝒪(n1/4) approximation for densest k-subgraph. Schulman LJ, ed. Proc. 42nd ACM Sympos. Theory Comput. (ACM Press, New York), 201–210.Crossref, Google Scholar
• Billionet A, Calmels F (1996) Linear programming for the quadratic knapsack problem. Eur. J. Oper. Res. 92:310–325.Crossref, Google Scholar
• Caprara A, Pisinger D, Toth P (1999) Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 11:125–137.Link, Google Scholar
• Chaillou P, Hansen P, Mahieu Y (1983) Best network flow bound for the quadratic knapsack problem. Simeone B, ed. Combinatorial Optimization, Lecture Notes in Mathematics, Vol. 1403 (Springer, Berlin), 225–235.Google Scholar
• Dantzig GB (1957) Discrete-variable extremum problems. Oper. Res. 5:266–288.Link, Google Scholar
• Gallo G, Hammer PL, Simeone B (1980) Quadratic knapsack problems. Math. Program. Stud. 12:132–149.Crossref, Google Scholar
• Glover F, Kochenberger G, Alidaee B, Amini M (2002) Solving quadratic knapsack problems by reformulation and tabu search, single constraint case. Pardalos PM, Migdalas A, Burkard RE, eds. Combinatorial and Global Optimization, Series on Applied Mathematics, Vol. 14 (World Scientific, Singapore), 111–121.Crossref, Google Scholar
• Karp RM (1972) Reducibility among combinatorial problems. Miller RE, Thatcher JW, eds. Complexity of Computer Computations (Plenum, New York), 85–103.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin).Crossref, Google Scholar
• Kellerer H, Strusevich VA (2010) Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica 57:769–795.Crossref, Google Scholar
• Khot S (2006) Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36:1025–1071.Crossref, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, Chichester, UK).Google Scholar
• Michelon P, Veilleux L (1996) Lagrangean methods for the 0-1 quadratic knapsack problem. Eur. J. Oper. Res. 92:326–341.Crossref, Google Scholar
• Pisinger D (2007) The quadratic knapsack problem—A survey. Discr. Appl. Math. 155:623–648.Crossref, Google Scholar
• Pisinger D, Rasmussen AB, Sandvik R (2007) Solution of large quadratic knapsack problems through aggressive reduction. INFORMS J. Comput. 19:280–290.Link, Google Scholar
• Rader DJ Jr, Woeginger GJ (2002) The quadratic 0-1 knapsack problem with series-parallel support. Oper. Res. Lett. 30:159–166.Crossref, Google Scholar