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

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[2]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[3]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[4]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[5]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[6]

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192
[7]

Enkhbat Rentsen, Battur Gompil. Generalized nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[8]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[9]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[10]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[11]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[12]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[13]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[14]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1757-1778. doi: 10.3934/dcdss.2020453
[15]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090
[16]

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

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037
[18]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[19]

Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021035
[20]

Gaurav Nagpal, Udayan Chanda, Nitant Upasani. Inventory replenishment policies for two successive generations price-sensitive technology products. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021036

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences