• 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 & 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. 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. 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, (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. doi: 10.1145/321906.321909. Google Scholar

[5]

H. Kellerer, U. Pferschy and D. Pisinger, "Knapsack Problems,", Springer-Verlag, (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. Google Scholar

[7]

D. Pisinger and P. Toth, Knapsack Problems,, in, (1998), 299. Google Scholar

[8]

Z. Wang and W. Xing, A successive approximation algorithm for the multiple knapsack problem,, J. Comb. Optim., 17 (2009), 347. 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. 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. 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, (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. doi: 10.1145/321906.321909. Google Scholar

[5]

H. Kellerer, U. Pferschy and D. Pisinger, "Knapsack Problems,", Springer-Verlag, (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. Google Scholar

[7]

D. Pisinger and P. Toth, Knapsack Problems,, in, (1998), 299. Google Scholar

[8]

Z. Wang and W. Xing, A successive approximation algorithm for the multiple knapsack problem,, J. Comb. Optim., 17 (2009), 347. 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]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429

[11]

R.G. Duran, J.I. Etcheverry, J.D. Rossi. Numerical approximation of a parabolic problem with a nonlinear boundary condition. Discrete & Continuous Dynamical Systems - A, 1998, 4 (3) : 497-506. doi: 10.3934/dcds.1998.4.497

[12]

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

[13]

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

[14]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[15]

Meng Yu, Jack Xin. Stochastic approximation and a nonlocally weighted soft-constrained recursive algorithm for blind separation of reverberant speech mixtures. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1753-1767. doi: 10.3934/dcds.2010.28.1753

[16]

Giacomo Micheli, Michele Schiavina. A general construction for monoid-based knapsack protocols. Advances in Mathematics of Communications, 2014, 8 (3) : 343-358. doi: 10.3934/amc.2014.8.343

[17]

Andrzej Just, Zdzislaw Stempień. Optimal control problem for a viscoelastic beam and its galerkin approximation. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 263-274. doi: 10.3934/dcdsb.2018018

[18]

Lili Chang, Wei Gong, Guiquan Sun, Ningning Yan. PDE-constrained optimal control approach for the approximation of an inverse Cauchy problem. Inverse Problems & Imaging, 2015, 9 (3) : 791-814. doi: 10.3934/ipi.2015.9.791

[19]

Gilles Carbou, Bernard Hanouzet. Relaxation approximation of the Kerr model for the impedance initial-boundary value problem. Conference Publications, 2007, 2007 (Special) : 212-220. doi: 10.3934/proc.2007.2007.212

[20]

Fabio Camilli, Francisco Silva. A semi-discrete approximation for a first order mean field game problem. Networks & Heterogeneous Media, 2012, 7 (2) : 263-277. doi: 10.3934/nhm.2012.7.263

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]