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

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

1 2 3 ... 18 19 20 next

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

1 2 3 ... 18 19 20 next