-
Previous Article
Integrated inventory model with stochastic lead time and controllable variability for milk runs
- JIMO Home
- This Issue
-
Next Article
An extended lifetime measure for telecommunications networks: Improvements and implementations
Worst-case performance of the successive approximation algorithm for four identical knapsacks
| 1. | Department of Mathematical Sciences, Tsinghua University, Beijing |
References:
| [1] |
A. Caprara and U. Pferschy, Worst-case analysis of the subset sum algorithm for bin packing, Oper. Res. Lett., 32 (2004), 159-166.
doi: 10.1016/S0167-6377(03)00092-0. |
| [2] |
C. Chekuri and S. Khanna, A polynomial time approximation scheme for the multiple knapsack problem, SIAM J. Comput., 35 (2005), 713-728.
doi: 10.1137/S0097539700382820. |
| [3] |
M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979. |
| [4] |
O. H. Ibarra and C. E. Kim, Fast approximation algorithms for the knapsack and sum of subset problem, J. ACM, 22 (1975), 463-468.
doi: 10.1145/321906.321909. |
| [5] |
H. Kellerer, U. Pferschy and D. Pisinger, "Knapsack Problems," Springer-Verlag, Berlin, 2004. |
| [6] |
H. Kellerer and U. Pferschy, A new fully polynomial time approximation scheme for the knapsack problem, J. Comb. Optim., 3 (1999), 59-71. |
| [7] |
D. Pisinger and P. Toth, Knapsack Problems, in "Handbook of Combinatorial Optimization," Vol. 1, Kluwer Academic Publishers, Boston, MA, (1998), 299-428. |
| [8] |
Z. Wang and W. Xing, A successive approximation algorithm for the multiple knapsack problem, J. Comb. Optim., 17 (2009), 347-366.
doi: 10.1007/s10878-007-9116-y. |
show all references
References:
| [1] |
A. Caprara and U. Pferschy, Worst-case analysis of the subset sum algorithm for bin packing, Oper. Res. Lett., 32 (2004), 159-166.
doi: 10.1016/S0167-6377(03)00092-0. |
| [2] |
C. Chekuri and S. Khanna, A polynomial time approximation scheme for the multiple knapsack problem, SIAM J. Comput., 35 (2005), 713-728.
doi: 10.1137/S0097539700382820. |
| [3] |
M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness," A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, CA, 1979. |
| [4] |
O. H. Ibarra and C. E. Kim, Fast approximation algorithms for the knapsack and sum of subset problem, J. ACM, 22 (1975), 463-468.
doi: 10.1145/321906.321909. |
| [5] |
H. Kellerer, U. Pferschy and D. Pisinger, "Knapsack Problems," Springer-Verlag, Berlin, 2004. |
| [6] |
H. Kellerer and U. Pferschy, A new fully polynomial time approximation scheme for the knapsack problem, J. Comb. Optim., 3 (1999), 59-71. |
| [7] |
D. Pisinger and P. Toth, Knapsack Problems, in "Handbook of Combinatorial Optimization," Vol. 1, Kluwer Academic Publishers, Boston, MA, (1998), 299-428. |
| [8] |
Z. Wang and W. Xing, A successive approximation algorithm for the multiple knapsack problem, J. Comb. Optim., 17 (2009), 347-366.
doi: 10.1007/s10878-007-9116-y. |
| [1] |
Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial and Management Optimization, 2013, 9 (3) : 531-547. doi: 10.3934/jimo.2013.9.531 |
| [2] |
Ying Ji, Shaojian Qu, Yeming Dai. A new approach for worst-case regret portfolio optimization problem. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 761-770. doi: 10.3934/dcdss.2019050 |
| [3] |
Konstantinos A. Draziotis, Anastasia Papadopoulou. Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme. Advances in Mathematics of Communications, 2018, 12 (3) : 429-449. doi: 10.3934/amc.2018026 |
| [4] |
Xueling Zhou, Meixia Li, Haitao Che. Relaxed successive projection algorithm with strong convergence for the multiple-sets split equality problem. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2557-2572. doi: 10.3934/jimo.2020082 |
| [5] |
Ruchika Sehgal, Aparna Mehra. Worst-case analysis of Gini mean difference safety measure. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1613-1637. doi: 10.3934/jimo.2020037 |
| [6] |
Xiaoling Sun, Hongbo Sheng, Duan Li. An exact algorithm for 0-1 polynomial knapsack problems. Journal of Industrial and Management Optimization, 2007, 3 (2) : 223-232. doi: 10.3934/jimo.2007.3.223 |
| [7] |
Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 |
| [8] |
Yuzhong Zhang, Fan Zhang, Maocheng Cai. Some new results on multi-dimension Knapsack problem. Journal of Industrial and Management Optimization, 2005, 1 (3) : 315-321. doi: 10.3934/jimo.2005.1.315 |
| [9] |
Hsin-Min Sun, Yu-Juan Sun. Variable fixing method by weighted average for the continuous quadratic knapsack problem. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 15-29. doi: 10.3934/naco.2021048 |
| [10] |
Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 |
| [11] |
Jian Sun, Haiyun Sheng, Yuefang Sun, Donglei Du, Xiaoyan Zhang. Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021116 |
| [12] |
Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $-means problem†. Journal of Industrial and Management Optimization, 2022, 18 (1) : 411-426. doi: 10.3934/jimo.2020160 |
| [13] |
Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $-means problem with penalty. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2277-2287. doi: 10.3934/jimo.2021067 |
| [14] |
Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008 |
| [15] |
Yuyuan Ouyang, Trevor Squires. Some worst-case datasets of deterministic first-order methods for solving binary logistic regression. Inverse Problems and Imaging, 2021, 15 (1) : 63-77. doi: 10.3934/ipi.2020047 |
| [16] |
Ali Fuat Alkaya, Dindar Oz. An optimal algorithm for the obstacle neutralization problem. Journal of Industrial and Management Optimization, 2017, 13 (2) : 835-856. doi: 10.3934/jimo.2016049 |
| [17] |
David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete and Continuous Dynamical Systems, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429 |
| [18] |
Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021197 |
| [19] |
Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Two-person knapsack game. Journal of Industrial and Management Optimization, 2010, 6 (4) : 847-860. doi: 10.3934/jimo.2010.6.847 |
| [20] |
Wenxun Xing, Feng Chen. A-shaped bin packing: Worst case analysis via simulation. Journal of Industrial and Management Optimization, 2005, 1 (3) : 323-335. doi: 10.3934/jimo.2005.1.323 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]