Online Algorithms for Convex Case Capital Investment

概要

論文の詳細を見る
In a factory, we need to make capital investments in machines for manufacturing a product. In this paper, we deal with the convex case capital investment such that more expensive machines have cheaper production costs. What we with to achieve is to design a good online algorithm that minimizes the sum of the production and capital costs when the production request and investment opportunities in the future are unknown. Azar, et al. proposed an (online) algorithm Convex for the convex case capital investment and showed that it is (4+2√2)-competitive. In this paper, we investigate the competitive ratio of the convex case capital investment more precisely and show that (1) for the convex case capital investment, the competitive ratio of the algorithm Convex is at least 4+2√2-ε for any ε>0 (Theorem 3.3). In the practical point of view, we introduce a notion of “γ-restricted” to the convex case capital investment and show that (2) for the γ-restricted convex case capital investment, the competitive ratio of the algorithm Convex is at most 5+4/(γ−4) for any γ≥6 (Theorem 4.3); (3) for the γ-restricted convex case capital investment, the competitive ratio of the algorithm Convex is at least 5−ε for any ε>0 (Theorem 4.4). Finally, we also show that the competitive ratio of the γ-restricted convex case capital investment is at least 2−ε for any ε>0 (Theorem 5.4).
東北大学の論文