Knapsack

Knapsack problems are the simplest NP-hard problems in combinatorial optimization, as they maximize an objective function subject to a single resource constraint. Several variants of the classical 0-1 knapsack problem will be considered with respect to relaxations, bounds, reductions and other algorithmic techniques for the exact solution. Computational results are presented to compare the actual performance of the most effective algorithms published.


References in zbMATH (referenced in 461 articles , 3 standard articles )

Showing results 1 to 20 of 461.
Sorted by year (citations)

1 2 3 ... 22 23 24 next

  1. Autry, Jackson; Gomes, Tara; O’Neill, Christopher; Ponomarenko, Vadim: Elasticity in Apéry sets (2020)
  2. Dauzère-Pérès, Stéphane; Hassoun, Michael: On the importance of variability when managing metrology capacity (2020)
  3. Della Croce, Federico; Scatamacchia, Rosario: An exact approach for the bilevel knapsack problem with interdiction constraints and extensions (2020)
  4. Delorme, Maxence; Iori, Manuel: Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems (2020)
  5. Drake, John H.; Kheiri, Ahmed; Özcan, Ender; Burke, Edmund K.: Recent advances in selection hyper-heuristics (2020)
  6. Fampa, M.; Lubke, D.; Wang, F.; Wolkowicz, H.: Parametric convex quadratic relaxation of the quadratic knapsack problem (2020)
  7. Goldberg, Noam; Poss, Michael: Maximum probabilistic all-or-nothing paths (2020)
  8. Guignard, Monique: Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic (0-1) optimization problems with linear constraints (2020)
  9. Joung, Seulgi; Lee, Kyungsik: Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity (2020)
  10. Morales, Fernando A.; Martínez, Jairo A.: Analysis of divide-and-conquer strategies for the (0-1) minimization knapsack problem (2020)
  11. Schulze, Britta; Stiglmayr, Michael; Paquete, Luís; Fonseca, Carlos M.; Willems, David; Ruzika, Stefan: On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem (2020)
  12. Anastasiadis, Eleftherios; Deng, Xiaotie; Krysta, Piotr; Li, Minming; Qiao, Han; Zhang, Jinshan: Network pollution games (2019)
  13. Bergman, David: An exact algorithm for the quadratic multiknapsack problem with an application to event seating (2019)
  14. Bonami, Pierre; Lodi, Andrea; Schweiger, Jonas; Tramontani, Andrea: Solving quadratic programming by cutting planes (2019)
  15. Coindreau, Marc-Antoine; Gallay, Olivier; Zufferey, Nicolas; Laporte, Gilbert: Integrating workload smoothing and inventory reduction in three intermodal logistics platforms of a European car manufacturer (2019)
  16. Della Croce, Federico; Pferschy, Ulrich; Scatamacchia, Rosario: On approximating the incremental knapsack problem (2019)
  17. Della Croce, Federico; Pferschy, Ulrich; Scatamacchia, Rosario: New exact approaches and approximation results for the penalized knapsack problem (2019)
  18. Dell’Amico, Mauro; Delorme, Maxence; Iori, Manuel; Martello, Silvano: Mathematical models and decomposition methods for the multiple knapsack problem (2019)
  19. Fang, Ethan X.; Liu, Han; Wang, Mengdi: Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach (2019)
  20. Fischetti, Matteo; Ljubić, Ivana; Monaci, Michele; Sinnl, Markus: Interdiction games and monotonicity, with application to knapsack problems (2019)

1 2 3 ... 22 23 24 next