• 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

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.
Citation: Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial and 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.

[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]

Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $-means problem with penalty. Journal of Industrial and 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 and 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 and 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 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

Metrics

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

Other articles
by authors

[Back to Top]