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

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

1 2 3 ... 17 18 19 next

  1. Christensen, Henrik I.; Khan, Arindam; Pokutta, Sebastian; Tetali, Prasad: Approximation and online algorithms for multidimensional bin packing: a survey (2017)
  2. Kowalczyk, Daniel; Leus, Roel: An exact algorithm for parallel machine scheduling with conflicts (2017)
  3. Blado, Daniel; Hu, Weihong; Toriello, Alejandro: Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes (2016)
  4. Caprara, Alberto; Carvalho, Margarida; Lodi, Andrea; Woeginger, Gerhard J.: Bilevel knapsack with interdiction constraints (2016)
  5. Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano: Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation (2016)
  6. Chen, Danny Z.; Li, Jian; Liang, Hongyu; Wang, Haitao: Matroid and knapsack center problems (2016)
  7. Cunha, Jesus Ossian; Simonetti, Luidi; Lucena, Abilio: Lagrangian heuristics for the quadratic knapsack problem (2016)
  8. Dahmani, Isma; Hifi, Mhand; Wu, Lei: An exact decomposition algorithm for the generalized knapsack sharing problem (2016)
  9. Han, Jinil; Lee, Kyungsik; Lee, Chungmok; Choi, Ki-Seok; Park, Sungsoo: Robust optimization approach for a chance-constrained binary knapsack problem (2016)
  10. He, Cheng; Leung, Joseph Y-T.; Lee, Kangbok; Pinedo, Michael L.: An improved binary search algorithm for the multiple-choice knapsack problem (2016)
  11. Jansen, K.; Land, F.; Land, K.: Bounding the running time of algorithms for scheduling and packing problems (2016)
  12. Laalaoui, Y.; M’Hallah, R.: A binary multiple knapsack model for single machine scheduling with machine unavailability (2016)
  13. Qin, Jin; Xu, Xianhao; Wu, Qinghua; Cheng, T.C.E.: Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem (2016)
  14. Roland, Julien; Figueira, José Rui; De Smet, Yves: Finding compromise solutions in project portfolio selection with multiple experts by inverse optimization (2016)
  15. Schauer, Joachim: Asymptotic behavior of the quadratic knapsack problem (2016)
  16. Vasilyev, Igor; Boccia, Maurizio; Hanafi, Saïd: An implementation of exact knapsack separation (2016)
  17. Wishon, Christopher; Villalobos, J.Rene: Robust efficiency measures for linear knapsack problem variants (2016)
  18. Aardal, Karen; van den Berg, Pieter L.; Gijswijt, Dion; Li, Shanfei: Approximation algorithms for hard capacitated $k$-facility location problems (2015)
  19. Azad, Md.Abul Kalam; Rocha, Ana Maria A.C.; Fernandes, Edite M.G.P.: Solving large 0-1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm (2015)
  20. Balogh, János; Békési, József; Dósa, György; Epstein, Leah; Kellerer, Hans; Levin, Asaf; Tuza, Zsolt: Offline black and white bin packing (2015)

1 2 3 ... 17 18 19 next