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

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

1 2 3 ... 18 19 20 next

  1. Diaz, Juan Esteban; Handl, Julia; Xu, Dong-Ling: Integrating meta-heuristics, simulation and exact techniques for production planning of a failure-prone manufacturing system (2018)
  2. Fischetti, Matteo; Monaci, Michele; Sinnl, Markus: A dynamic reformulation heuristic for generalized interdiction problems (2018)
  3. Gadegaard, Sune Lauth; Klose, Andreas; Nielsen, Lars Relund: An improved cut-and-solve algorithm for the single-source capacitated facility location problem (2018)
  4. Kung, Ling-Chieh; Liao, Wei-Hung: An approximation algorithm for a competitive facility location problem with network effects (2018)
  5. Zhen, Lu; Wang, Kai; Wang, Shuaian; Qu, Xiaobo: Tug scheduling for hinterland barge transport: a branch-and-price approach (2018)
  6. Christensen, Henrik I.; Khan, Arindam; Pokutta, Sebastian; Tetali, Prasad: Approximation and online algorithms for multidimensional bin packing: a survey (2017)
  7. Della Croce, Federico; Salassa, Fabio; Scatamacchia, Rosario: A new exact approach for the 0-1 collapsing knapsack problem (2017)
  8. Edirisinghe, Chanaka; Jeong, Jaehwan: Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time (2017)
  9. Fomeni, Franklin Djeumou: A new family of facet defining inequalities for the maximum edge-weighted clique problem (2017)
  10. Furini, Fabio; Ljubić, Ivana; Sinnl, Markus: An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem (2017)
  11. Haahr, Jørgen Thorlund; Lusby, Richard M.; Wagenaar, Joris Camiel: Optimization methods for the train unit shunting problem (2017)
  12. Keskin, Muhammed Emre: A column generation heuristic for optimal wireless sensor network design with mobile sinks (2017)
  13. Kobayashi, Yusuke; Takazawa, Kenjiro: Randomized strategies for cardinality robustness in the knapsack problem (2017)
  14. Kowalczyk, Daniel; Leus, Roel: An exact algorithm for parallel machine scheduling with conflicts (2017)
  15. Ou, Jinwen; Zhong, Xueling: Order acceptance and scheduling with consideration of service level (2017)
  16. Pisinger, David; Saidi, Alima: Tolerance analysis for 0-1 knapsack problems (2017)
  17. Polyakovskiy, S.; Neumann, F.: The packing while traveling problem (2017)
  18. Simon, Jay; Apte, Aruna; Regnier, Eva: An application of the multiple knapsack problem: the self-sufficient marine (2017)
  19. Anastasiadis, Eleftherios; Deng, Xiaotie; Krysta, Piotr; Li, Minming; Qiao, Han; Zhang, Jinshan: New results for network pollution games (2016)
  20. Blado, Daniel; Hu, Weihong; Toriello, Alejandro: Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes (2016)

1 2 3 ... 18 19 20 next