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

Showing results 1 to 20 of 377.
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. Edirisinghe, Chanaka; Jeong, Jaehwan: Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time (2017)
  3. Fomeni, Franklin Djeumou: A new family of facet defining inequalities for the maximum edge-weighted clique problem (2017)
  4. Furini, Fabio; Ljubić, Ivana; Sinnl, Markus: An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem (2017)
  5. Haahr, Jørgen Thorlund; Lusby, Richard M.; Wagenaar, Joris Camiel: Optimization methods for the train unit shunting problem (2017)
  6. Kobayashi, Yusuke; Takazawa, Kenjiro: Randomized strategies for cardinality robustness in the knapsack problem (2017)
  7. Kowalczyk, Daniel; Leus, Roel: An exact algorithm for parallel machine scheduling with conflicts (2017)
  8. Ou, Jinwen; Zhong, Xueling: Order acceptance and scheduling with consideration of service level (2017)
  9. Anastasiadis, Eleftherios; Deng, Xiaotie; Krysta, Piotr; Li, Minming; Qiao, Han; Zhang, Jinshan: New results for network pollution games (2016)
  10. Blado, Daniel; Hu, Weihong; Toriello, Alejandro: Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes (2016)
  11. Caprara, Alberto; Carvalho, Margarida; Lodi, Andrea; Woeginger, Gerhard J.: Bilevel knapsack with interdiction constraints (2016)
  12. Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano: Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation (2016)
  13. Chen, Danny Z.; Li, Jian; Liang, Hongyu; Wang, Haitao: Matroid and knapsack center problems (2016)
  14. Cunha, Jesus Ossian; Simonetti, Luidi; Lucena, Abilio: Lagrangian heuristics for the quadratic knapsack problem (2016)
  15. Czibula, Oliver G.; Gu, Hanyu; Zinder, Yakov: A Lagrangian relaxation-based heuristic to solve large extended graph partitioning problems (2016)
  16. Czibula, Oliver G.; Gu, Hanyu; Zinder, Yakov: Scheduling personnel retraining: column generation heuristics (2016)
  17. Dahmani, Isma; Hifi, Mhand; Wu, Lei: An exact decomposition algorithm for the generalized knapsack sharing problem (2016)
  18. Han, Jinil; Lee, Kyungsik; Lee, Chungmok; Choi, Ki-Seok; Park, Sungsoo: Robust optimization approach for a chance-constrained binary knapsack problem (2016)
  19. He, Cheng; Leung, Joseph Y-T.; Lee, Kangbok; Pinedo, Michael L.: An improved binary search algorithm for the multiple-choice knapsack problem (2016)
  20. Jansen, K.; Land, F.; Land, K.: Bounding the running time of algorithms for scheduling and packing problems (2016)

1 2 3 ... 17 18 19 next