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 464 articles , 3 standard articles )

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

1 2 3 ... 22 23 24 next

  1. Garcia, Stephan Ramon; Omar, Mohamed; O’Neill, Christopher; Yih, Samuel: Factorization length distribution for affine semigroups. II: Asymptotic behavior for numerical semigroups with arbitrarily many generators (2021)
  2. Puerto, Justo; Ricca, Federica; Scozzari, Andrea: Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem (2021)
  3. Autry, Jackson; Gomes, Tara; O’Neill, Christopher; Ponomarenko, Vadim: Elasticity in Apéry sets (2020)
  4. Chirkov, Aleksandr Yu.; Gribanov, Dmitry V.; Zolotykh, Nikolai Yu.: On the proximity of the optimal values of the multi-dimensional knapsack problem with and without the cardinality constraint (2020)
  5. Dauzère-Pérès, Stéphane; Hassoun, Michael: On the importance of variability when managing metrology capacity (2020)
  6. Della Croce, Federico; Scatamacchia, Rosario: An exact approach for the bilevel knapsack problem with interdiction constraints and extensions (2020)
  7. Delorme, Maxence; Iori, Manuel: Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems (2020)
  8. Drake, John H.; Kheiri, Ahmed; Özcan, Ender; Burke, Edmund K.: Recent advances in selection hyper-heuristics (2020)
  9. Fampa, M.; Lubke, D.; Wang, F.; Wolkowicz, H.: Parametric convex quadratic relaxation of the quadratic knapsack problem (2020)
  10. Goldberg, Noam; Poss, Michael: Maximum probabilistic all-or-nothing paths (2020)
  11. Guignard, Monique: Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic (0-1) optimization problems with linear constraints (2020)
  12. Joung, Seulgi; Lee, Kyungsik: Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity (2020)
  13. Morales, Fernando A.; Martínez, Jairo A.: Analysis of divide-and-conquer strategies for the (0-1) minimization knapsack problem (2020)
  14. 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)
  15. Anastasiadis, Eleftherios; Deng, Xiaotie; Krysta, Piotr; Li, Minming; Qiao, Han; Zhang, Jinshan: Network pollution games (2019)
  16. Bergman, David: An exact algorithm for the quadratic multiknapsack problem with an application to event seating (2019)
  17. Bonami, Pierre; Lodi, Andrea; Schweiger, Jonas; Tramontani, Andrea: Solving quadratic programming by cutting planes (2019)
  18. 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)
  19. Della Croce, Federico; Pferschy, Ulrich; Scatamacchia, Rosario: New exact approaches and approximation results for the penalized knapsack problem (2019)
  20. Della Croce, Federico; Pferschy, Ulrich; Scatamacchia, Rosario: On approximating the incremental knapsack problem (2019)

1 2 3 ... 22 23 24 next