A note: An improved upper bound for the online inventory problem with bounded storage and order costs

摘要

This work gives an improved competitive analysis for an online inventory problem with bounded storage and order costs proposed by Larsen and Wohlk (2010). We improve the upper bound of the competitive ratio from (2 + 1/k) root M/m to less than 4/5(2 + 1/k)root M/m, where k, M and m are parameters of the given problem. The key idea is to use linear-fractional programming and primal-dual analysis methods to find the upper bound of a central inequality. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.