تقرير
Asymptotic optimality of dynamic first-fit packing on the half-axis
| العنوان: | Asymptotic optimality of dynamic first-fit packing on the half-axis |
|---|---|
| المؤلفون: | Ernst, Philip, Stolyar, Alexander |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Probability, Computer Science - Data Structures and Algorithms, 90B15, 60K25 |
| الوصف: | We revisit a classical problem in dynamic storage allocation. Items arrive in a linear storage medium, modeled as a half-axis, at a Poisson rate $r$ and depart after an independent exponentially distributed unit mean service time. The arriving item sizes are assumed to be independent and identically distributed (i.i.d.) from a common distribution $H$. A widely employed algorithm for allocating the items is the ``first-fit'' discipline, namely, each arriving item is placed in the the left-most vacant interval large enough to accommodate it. In a seminal 1985 paper, Coffman, Kadota, and Shepp [6] proved that in the special case of unit length items (i.e. degenerate $H$), the first-fit algorithm is asymptotically optimal in the following sense: the ratio of expected empty space to expected occupied space tends towards $0$ as the occupied space tends towards infinity. In a sequel to [6], the authors of [5] conjectured that the first-fit discipline is also asymptotically optimal for non-degenerate $H$. In this paper we provide the first proof of first-fit asymptotic optimality for a non-degenerate distribution $H$, namely the case when items can be of sizes 1 and 2. Specifically, we prove that, under first-fit, the steady-state packing configuration, scaled down by $r$, converges in distribution to the optimal limiting packing configuration, i.e. the one with smaller items on the left, larger items on the right, and with no gaps between. Comment: 11 pages, 1 figure |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2404.03797 |
| رقم الأكسشن: | edsarx.2404.03797 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |