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

Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251

[2]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[3]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[4]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[5]

Qingfang Wang, Hua Yang. Solutions of nonlocal problem with critical exponent. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5591-5608. doi: 10.3934/cpaa.2020253

[6]

Stefano Bianchini, Paolo Bonicatto. Forward untangling and applications to the uniqueness problem for the continuity equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020384

[7]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453

[8]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[9]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075

[10]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171

[11]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[12]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[13]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[14]

Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348

[15]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052

[16]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[17]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[18]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[19]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346

[20]

Laurence Cherfils, Stefania Gatti, Alain Miranville, Rémy Guillevin. Analysis of a model for tumor growth and lactate exchanges in a glioma. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020457

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]