American Institute of Mathematical Sciences

Advanced
  • 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
July  2012, 8(3): 651-656. doi: 10.3934/jimo.2012.8.651

Worst-case performance of the successive approximation algorithm for four identical knapsacks

Zhenbo Wang 1,

1. 

Department of Mathematical Sciences, Tsinghua University, Beijing

Received  August 2011 Revised  February 2012 Published  June 2012

This paper studies the worst-case performance of the successive approximation algorithm for four identical knapsacks. The algorithm packs the knapsacks successively by using an exact algorithm on the remaining items for each single knapsack. We show that it is an $\frac{8}{11}$-approximation algorithm, and the bound is tight.
Keywords: successive approximation algorithm, Approximation algorithm, multiple knapsack problem, worst-case analysis., knapsack problem.
Mathematics Subject Classification: Primary: 68Q25, 90B9.
Citation: Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

H. Kellerer, U. Pferschy and D. Pisinger, "Knapsack Problems," Springer-Verlag, Berlin, 2004.  Google Scholar

[6]

H. Kellerer and U. Pferschy, A new fully polynomial time approximation scheme for the knapsack problem, J. Comb. Optim., 3 (1999), 59-71.  Google Scholar

[7]

D. Pisinger and P. Toth, Knapsack Problems, in "Handbook of Combinatorial Optimization," Vol. 1, Kluwer Academic Publishers, Boston, MA, (1998), 299-428.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

H. Kellerer, U. Pferschy and D. Pisinger, "Knapsack Problems," Springer-Verlag, Berlin, 2004.  Google Scholar

[6]

H. Kellerer and U. Pferschy, A new fully polynomial time approximation scheme for the knapsack problem, J. Comb. Optim., 3 (1999), 59-71.  Google Scholar

[7]

D. Pisinger and P. Toth, Knapsack Problems, in "Handbook of Combinatorial Optimization," Vol. 1, Kluwer Academic Publishers, Boston, MA, (1998), 299-428.  Google Scholar

[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.  Google Scholar

[1]

Jing Zhou, Dejun Chen, Zhenbo Wang, Wenxun Xing. A conic approximation method for the 0-1 quadratic knapsack problem. Journal of Industrial & 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 & 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 & 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 & Management Optimization, 2021, 17 (4) : 1613-1637. doi: 10.3934/jimo.2020037
[6]

Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521
[7]

Xiaoling Sun, Hongbo Sheng, Duan Li. An exact algorithm for 0-1 polynomial knapsack problems. Journal of Industrial & Management Optimization, 2007, 3 (2) : 223-232. doi: 10.3934/jimo.2007.3.223
[8]

Yuzhong Zhang, Fan Zhang, Maocheng Cai. Some new results on multi-dimension Knapsack problem. Journal of Industrial & 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 & 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 & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117
[11]

Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $-means problem with penalty. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021067
[12]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021116
[13]

Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $-means problem†. Journal of Industrial & Management Optimization, 2022, 18 (1) : 411-426. doi: 10.3934/jimo.2020160
[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 & 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 & 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 & 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 & Management Optimization, 2021  doi: 10.3934/jimo.2021197
[19]

Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Two-person knapsack game. Journal of Industrial & 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 & Management Optimization, 2005, 1 (3) : 323-335. doi: 10.3934/jimo.2005.1.323

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (37)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy