# Dynamic Vector Bin Packing for
Online Resource Allocation in the Cloud

Aniket Murhekar111University of Illinois at Urbana-Champaign, USA
<EMAIL_ADDRESS>David Arbour222Adobe Research, USA
<EMAIL_ADDRESS>
Tung Mai333Adobe Research, USA
<EMAIL_ADDRESS>
Anup Rao444Adobe Research, USA
<EMAIL_ADDRESS>
###### Abstract

Several cloud-based applications, such as cloud gaming, rent servers to
execute jobs which arrive in an online fashion. Each job has a resource
demand, such as GPU requirement, and must be dispatched to a cloud server
which has enough resources to execute the job, which departs after its
completion. Under the “pay-as-you-go” billing model, the server rental cost is
proportional to the total time that servers are actively running jobs. The
problem of efficiently allocating a sequence of online jobs to servers without
exceeding the resource capacity of any server while minimizing total server
usage time can be modelled as a variant of the dynamic bin packing problem
(DBP), called MinUsageTime DBP [21].

In this work, we initiate the study of the problem with multi-dimensional
resource demands (e.g. CPU/GPU usage, memory requirement, bandwidth usage,
etc.), called MinUsageTime Dynamic Vector Bin Packing (DVBP). We study the
competitive ratio (CR) of Any Fit packing algorithms for this problem. We show
almost-tight bounds on the CR of three specific Any Fit packing algorithms,
namely First Fit, Next Fit, and Move To Front. We prove that the CR of Move To
Front is at most $(2\mu+1)d+1$, where $\mu$ is the ratio of the max/min item
durations. For $d=1$, this implies a significant improvement over the
previously known upper bound of $6\mu+7$ [18]. We then prove the CR of First
Fit and Next Fit are bounded by $(\mu+2)d+1$ and $2\mu d+1$, respectively.
Next, we prove a lower bound of $(\mu+1)d$ on the CR of any Any Fit packing
algorithm, an improved lower bound of $2\mu d$ for Next Fit, and a lower bound
of $2\mu$ for Move To Front in the 1-D case. All our bounds improve or match
the best-known bounds for the 1-D case. Finally, we experimentally study the
average-case performance of these algorithms on randomly generated synthetic
data, and observe that Move To Front outperforms other Any Fit packing
algorithms.

##  1 Introduction

Bin packing is an extensively studied problem in combinatorial optimization
[11]. The goal of the classical bin packing problem is to pack a given set of
items with different sizes into the smallest number of identical bins such
that the total size of items in each bin does not exceed the capacity of the
bin. The dynamic bin packing problem (DBP) [9] is a generalization of the
classical bin packing problem, where items can arrive and depart over time,
and the objective is to minimize the number of bins used over time. Dynamic
bin packing naturally models several resource allocation problems, including
those arising in cloud computing [30, 19].

Motivated by cloud computing applications where the goal is to dispatch jobs
arriving in an online fashion to servers, with the objective of minimizing the
server usage time, Li, Tang, and Cai [21] introduced a variant of dynamic bin
packing called MinUsageTime Dynamic Bin Packing. In this variant, items appear
in an online fashion and must be packed into resource-bounded bins. When an
item (job) arrives, it must immediately be dispatched to a bin (server) which
has enough resources to accommodate (execute) the job. The objective is to
minimize the total time that bins are active, i.e., contain at least one
active item that has not yet departed. Moreover, due to overheads involved in
migrating jobs from one server to another, it is assumed that the placement of
an item to a bin is irrevocable. The objective function, the total usage time
of the bins, naturally models the power consumption or rental cost of the
servers. Below we discuss two concrete applications motivating the
MinUsageTime Dynamic Bin Packing problem, one faced by cloud service provider
and the other by the cloud service user.

#### Virtual machine placement on physical servers.

A popular way that cloud resource providers offer their services to users is
through the use of Virtual Machines (VMs). Users can request VMs with certain
resource demands, and in turn cloud resource managers place these VMs on
physical servers with sufficient resource capacity to serve the VM requests.
Minimizing the total usage time of the physical machines can directly lead to
power and cost savings on the cloud provider end [5, 23]. As [15] suggests,
even a 1% improvement in packing efficiency can lead to cost savings of
roughly $100 million per year for Microsoft Azure. By viewing the VM requests
as items and the physical servers as bins, the problem of minimizing the usage
time of physical machines therefore directly translates to the MinUsageTime
DBP problem.

#### Cloud gaming and other cloud user applications.

Several organizations offer their services to customers by renting servers (as
VMs) from on-demand public cloud providers such as Amazon EC2. They are
typically charged according to their server usage times in hourly or monthly
basis following the “pay-as-you-go” billing model [26]. Minimizing the
organization’s server renting cost is therefore equivalent to minimizing the
usage time of the rented servers, thus reducing to the MinUsageTime DBP
problem where customer jobs are viewed as items and rented servers as bins
[21, 18, 32, 22, 28, 2]. Organizations such as GaiKai [12], OnLive[24], and
StreamMyGame [31] offer cloud based gaming services where computer games run
on rented cloud servers, thereby saving players from the overheads involved in
set-up and maintenance of the hardware/software infrastructure required for
the game. A request from a customer to play a game is dispatched to a gaming
server which has enough resources such as GPU or bandwidth to run the game
instance, which runs until the customer stops playing the game. In this
context, the gaming service providers can greatly benefit by employing
efficient algorithms that dispatch customers’ game requests to rented servers
minimize the server rental cost.

MinUsageTime Dynamic Bin Packing is therefore a problem of commercial and
industrial importance, and has consequently also received theoretical interest
in recent years to analyze the performance of online algorithms for the
problem [21, 18, 32, 22, 28, 27, 2, 5]. The performance of an online algorithm
is usually measured in terms of its competitive ratio (CR) [4], which is the
worst-case ratio between the quality (e.g. total server renting cost) of
algorithm’s solution to the quality of the solution produced by an optimal,
offline algorithm. In this paper, we study the non-clairvoyant version of the
problem, wherein the departure time of an item is unknown upon its arrival. In
the context of cloud gaming, this models customers being able to play games
for durations unknown to the cloud gaming service.

Existing work has primarily focused on Any Fit packing algorithms, which is a
well-studied family of algorithms for the classical bin packing problem. An
Any Fit packing algorithm is an algorithm that opens a new bin only when an
incoming item cannot be packed in any of the existing open bins. Any Fit
packing algorithms are useful and well-studied because they take decisions
based on the current system state and not its history, leading to a desirable
simplicity in implementation and explainability, and a low computational and
memory footprint.

Li, Tang, and Cai [21, 22] showed that the competitive ratio of any Any Fit
packing algorithm for the MinUsageTime DBP problem is at least $\mu+1$, where
$\mu$ is the ratio of the max/min item durations. A series of works [21, 22,
32, 28] showed that the competitive ratio of First Fit, a specific Any Fit
packing algorithm which tries to pack a new item into the earliest opened bin
that can accommodate the item, is at most $\mu+3$. Likewise, Next Fit, which
keeps only one open bin at a time to pack items, was shown to have a CR of at
least $2\mu$ [32, 28] and at most $2\mu+1$ [18]. On the other hand, Best Fit,
which tries to pack a new item into bin with highest load, was shown to have
an unbounded CR [22]. Kamali and López-Ortiz [18] studied another Any Fit
packing algorithm called Move To Front, which tries to pack a new item into
the bin which was most recently used. They showed that Move To Front has an
(asymptotic) competitive ratio of at most $6\mu+7$, and conjectured that the
CR is at most $2\mu+1$. They also performed an average-case experimental study
of these algorithms, and found that Move To Front had the best average-case
performance, closely followed by First Fit and Best Fit.

#### Modelling Multi-dimensional Resources Demands.

All of the above previous works assumed the item sizes to be one-dimensional.
They assume items/jobs have a single dominant resource, such as CPU or GPU
demand. However, in practice, the resources demands of an item/job such as a
VM request or a game instance are multi-dimensional, e.g., CPU and GPU usage,
memory requirement, bandwidth usage, etc. In the bin packing literature, the
multi-dimensional version is a problem of great significance and is
extensively studied [8, 25]. The multidimensional nature of demand usually
makes the problem much more challenging [33]. In this work, we study the
generalization of the MinUsageTime DBP problem called MinUsageTime Dynamic
Vector Bin Packing (DVBP) where the sizes of items and bins are
$d$-dimensional vectors. The design of online algorithms for DVBP and the
analysis of their competitive ratios is therefore a natural and practically
important problem, and was indicated as an important direction for future work
by previous papers [27, 32, 28].

###  1.1 Our Contributions

In this work, we initiate the study of the multi-dimensional version of the
MinUsageTime DBP problem, called MinUsageTime Dynamic Vector Bin Packing
(henceforth referred to simply as DVBP), where item and bin sizes are
$d$-dimensional vectors. We analyze the competitive ratios of Any Fit packing
algorithms for the problem, including four specific algorithms: First Fit,
Next Fit, Best Fit and Move To Front. Table 1 summarizes the best known bounds
on the CR of these algorithms, and contrasts our results with previous work.
Our contributions are summarized below.

  * •

We prove an upper bound of $(2\mu+1)d+1$ on the competitive ratio of Move To
Front for DVBP. For $d=1$, this implies a significant improvement on the
previously known upper bound of $6\mu+7$ shown by Kamali and López-Ortiz [18]
to $2\mu+2$, and nearly settles their conjecture of the CR being $2\mu+1$.
Central to our result is a novel decomposition of the usage periods of the
bins used by Move To Front into two classes of intervals, and carefully
analyzing the cumulative cost of intervals in each class.

  * •

We prove an upper bound of $(\mu+2)d+1$ on the competitive ratio of First Fit,
and of $2\mu d+1$ for Next Fit. These results rely on new lower bounds on the
cost of the optimum solution for the $d$-D case. Our upper bounds then follow
by combining these bounds with analysis techniques inspired from upper bound
results for the 1-D case [28, 18]. Note that the competitive ratio of Best Fit
is unbounded even for the 1-D case [22].

  * •

We prove a lower bound of $(\mu+1)d$ on the competitive ratio of any Any Fit
packing algorithm for DVBP. We also show a lower bound of $2\mu d$ on the CR
of Next Fit and of $\max\\{2\mu,(\mu+1)d\\}$ for Move To Front. In conjunction
with our upper bound results, these results show almost-tightness for the CR
of First Fit and Next Fit for the $d$-D case, and of Move To Front for the 1-D
case. Our results improve or match all known lower bounds for the 1-D case
[21, 22, 28, 32, 18]. Due to the multi-dimensionality of the problem, lower
bound results of the 1-D case do not directly translate to the $d$-D case, and
hence we design new constructions to establish the lower bounds.

At a high level, our constructions use carefully-designed sequences of items
which force an Any Fit algorithm to open $\Omega(d\cdot k)$ bins for a
parameter $k$, each of which contain an item of small size but long-duration,
thus leading to a cost of $\approx\mu$ per bin. The optimal solution however
packs all the small items into a single bin with cost $\approx\mu$ and the
other items into $k$ bins with cost $\approx 1$, resulting in a total cost of
$O(k+\mu)$, thus implying CR of $\Omega(\mu d)$.

  * •

We perform an average-case experimental study of these algorithms on randomly
generated synthetic data. We observe that Move To Front outperforms other Any
Fit packing algorithms, with First Fit and Best Fit also performing well on
average.

Algorithm |  Lower Bound $(d=1)$ |  Upper Bound $(d=1)$ |  Lower Bound $(d\geq 1)$ |  Upper Bound $(d\geq 1)$
---|---|---|---|---
Any Fit |  $\mu+1$ [22, 28] |  $\infty$ |  $(\mu+1)d$ (Thm. 5) |  $\infty$
Move To Front |  $2\mu$ (Thm. 8) |  $2\mu+2$ (Thm. 2), improves [18] |  $\max\\{2\mu,(\mu+1)d\\}$ (Thm. 8) |  $(2\mu+1)d+1~{}~{}~{}~{}~{}$ (Thm. 2)
First Fit |  $\mu+1$ [22, 28] |  $\mu+3$ [28] |  $(\mu+1)d$ (Thm. 5) |  $(\mu+2)d+1~{}~{}~{}~{}~{}$ (Thm. 3)
Next Fit |  $2\mu$ [32] |  $2\mu+1$ [18] |  $2\mu d$ (Thm. 6) |  $2\mu d+1$ (Thm. 4)
Best Fit |  Unbounded [22] |  $\infty$ |  Unbounded [22] |  $\infty$
Table 1: Summary of the best known upper and lower bounds on the competitive
ratio of algorithms for the MinUsageTime Dynamic Vector Bin Packing problem in
$d$ dimensions. $\mu$ denotes the ratio of max/min item durations. Colored
cells highlight our results.

Given its bounded competitive ratio indicating good performance against
adversarial examples, as well as good average-case performance, our
theoretical and experimental results lead us to concur with the recommendation
of [18] that Move To Front is the algorithm of choice for practical solutions
to the DVBP problem, even in higher dimensions.

###  1.2 Further Related Work

Classical bin packing is known to be NP-hard even in the offline case [13].
There is extensive work on designing algorithms with good competitive ratio
for online versions of this problem [17, 10, 11], with 1.54037 and 1.58889
being the best-known lower and upper bounds [3, 29]. In online vector bin
packing, the item sizes are $d$-dimensional vectors. Garey et al. [14] showed
that a generalization of First Fit has a CR of $d+0.7$, and Azar et al. [1]
showed an information-theoretic lower bound of $\Omega(d^{1-\varepsilon})$.
For further results on multi-dimensional versions of bin packing, we refer the
reader to the survey [8]. On the practical side, Panigrahy et al. [25] studied
heuristics for the offline vector bin packing problem.

Dynamic bin packing with the objective of minimizing the number of bins is
also the subject of several works [9, 7, 6, 16]. Coffman et al. [9] showed
that First Fit has a competitive ratio of between 2.75 to 2.897, and Wong et
al. [34] showed a lower bound of 2.667 on the CR of any online algorithm. A
further generalization called the fully dynamic bin packing problem, in which
already packed items can be moved to different bins, has also been studied in
[16].

The MinUsageTime dynamic bin packing problem has been studied in several
recent works [21, 18, 32, 22, 28, 27, 2, 5]; Table 1 cites the relevant prior
work on the non-clairvoyant version of the problem. In the clairvoyant version
of the problem the departure time of an item is known when it arrives [27, 2].
This problem is known to have an algorithm with a $O(\sqrt{\log\mu})$
competitive ratio, with a matching lower bound [2]. The interval scheduling
problem [20] is also closely related; see [27, 5] and references therein. In
the presence of additional information about future load, algorithms with
improved CR were presented by [5]. To the best of our knowledge, the multi-
dimensional version of the MinUsageTime DBP problem has not been studied,
though it finds mention as a direction for future work in [27, 32, 28].

#### Organization.

The rest of the paper is organized as follows. Section 2 introduces notation,
relevant definitions, packing algorithms, and useful preliminary observations.
Section 3, 4, and 5 establish upper bounds on the competitive ratios of Move
To Front, First Fit, and Next Fit, respectively. Section 6 presents lower
bounds on competitive ratio of any Any Fit packing algorithm and certain
improved lower bounds for specific algorithms. Section 7 discusses our
experimental results examining the average-case performance of various Any Fit
packing algorithms on randomly generated synthetic data. Finally, some
concluding remarks and directions for future work are presented in Section 8.

##  2 Notation and Preliminaries

For $n\in\mathbb{N}$, let $[n]$ denote the set $\\{1,2,\dots,n\\}$. The
$L_{\infty}$ norm of a vector a vector $\mathbf{v}\in\mathbb{R}_{\geq 0}^{d}$
is denoted by $\lVert\mathbf{v}\rVert_{\infty}$ and equals
$\max_{i\in[d]}\mathbf{v}_{j}$. We will use the following simple properties of
the $L_{\infty}$ norm, which are proved in Appendix A.1 for completeness.

######  Proposition 1.

The $L_{\infty}$ norm satisfies the following.

  1. (i)

For a vector $\mathbf{v}\in\mathbb{R}_{\geq 0}^{d}$ and a constant $c\geq 0$,
$\lVert
c\cdot\mathbf{v}\rVert_{\infty}=c\cdot\lVert\mathbf{v}\rVert_{\infty}$.

  2. (ii)

For any set of vectors $\mathbf{v}_{1},\dots,\mathbf{v}_{n}\in\mathbb{R}_{\geq
0}^{d}$, we have:

$\bigg{\lVert}{\sum_{i=1}^{n}\mathbf{v}_{i}}\bigg{\rVert}_{\infty}\leq\sum_{i=1}^{n}\lVert\mathbf{v}_{i}\rVert_{\infty}\leq
d\cdot\bigg{\lVert}{\sum_{i=1}^{n}\mathbf{v}_{i}}\bigg{\rVert}_{\infty}.$

###  2.1 Problem Definition

We now formally define the online MinUsageTime Dynamic Vector Bin Packing
(DVBP) problem.

#### Problem Instance.

Let $d\in\mathbb{N}$ denote the number of resource dimensions, i.e., CPU,
memory, I/O, etc. We let $\mathcal{R}$ denote the list of items. Each item
$r\in\mathcal{R}$ is specified by a tuple $(a(r),e(r),\mathbf{s}(r))$, where
$a(r),e(r)\in\mathbb{Q}_{\geq 0}$ and $\mathbf{s}(r)$ denote the arrival time,
departure time, and the size of the item, respectively. Note that each item
has multi-dimensional resource demands, i.e.,
$\mathbf{s}(r)\in\mathbb{R}_{\geq 0}^{d}$ where $\mathbf{s}(r)_{j}$ denotes
the size of the item in the $j^{th}$ dimension, for $j\in[d]$. Without loss of
generality, we assume that bins have unit capacity in each dimension, i.e.,
the size of a bin is $\mathbf{1}^{d}$ and that $\mathbf{s}(r)\in[0,1]^{d}$ for
each $r\in\mathcal{R}$ by normalization. Further, let
$\mathbf{s}(\mathcal{R})=\sum_{r\in\mathcal{R}}\mathbf{s}(r)$.

For an item $r\in\mathcal{R}$, let $I(r)=[a(r),e(r))$ denote the active
interval555For technical reasons $I(r)$ is half open, i.e., the item $r$ has
departed at time $e(r)$. of item $r$, and we say that item $r$ is active in
the interval $I(r)$. Let $\ell(I(r))=e(r)-a(r)$ denote the length of interval
$I(r)$, i.e., the duration of item $r$. W.l.o.g, we assume
$\min_{r\in\mathcal{R}}\ell(I(r))=1$, and define
$\mu:=\max_{r\in\mathcal{R}}\ell(I(r))$. Thus, $\mu$ denotes the ratio of the
max/min item durations. Finally, let
$\mathsf{span}(\mathcal{R})=\ell(\cup_{r\in\mathcal{R}}I(r))$ denote the total
length of time for which at least one item of $\mathcal{R}$ is active.

#### Problem Objective.

We focus on the non-clairvoyant setting without recourse. This means that an
online algorithm must pack an item immediately into a single bin when it
arrives, and that the algorithm cannot repack items. Moreover, when an item
arrives the algorithm does not have any knowledge of when it will depart. Let
$P_{\mathcal{A},\mathcal{R}}$ denote the packing of the items $\mathcal{R}$ by
the algorithm $\mathcal{A}$. Let $B_{1},\dots,B_{m}$ be the bins opened by
$\mathcal{A}$, and let $R_{i}$ be the items placed on bin $B_{i}$. We assume
the cost of using a bin for an interval $I$ equals its length $\ell(I)$. Then
the cost of the packing $P_{\mathcal{A},\mathcal{R}}$ is defined as the total
usage time of all the bins, i.e.,

$\mathsf{cost}(\mathcal{A},\mathcal{R})=\sum_{i=1}^{m}\mathsf{span}(R_{i}).$
(1)

With this problem objective, our goal is to compute a packing of $\mathcal{R}$
that minimizes the above cost.

An empty bin is opened the first time it receives an item, and remains open as
long as it contains an active item. When an open bin becomes empty, i.e., all
items packed in it depart, we say that it is closed. We can assume that once a
bin is closed, it is never opened again, i.e., no item is packed in it again.
This assumption is justified because bins are indistinguishable, and an idle
bin has zero cost. Thus, a bin which has two usage periods $[a,b)$ and $[c,d)$
separated by an idle period $[b,c)$ can be replaced by two bins active between
$[a,b)$ and $[c,d)$ respectively, without any change in the cost. Thus we can
assume that the usage period of each bin is a single interval. Likewise, we
assume that $\cup_{r\in\mathcal{R}}I(r)$ equals the single interval
$[0,\mathsf{span}(\mathcal{R}))$, otherwise we can consider each interval of
$\cup_{r\in\mathcal{R}}I(r)$ as a separate sub-problem.

###  2.2 Any Fit Packing Algorithms

We now discuss the Any Fit family of algorithms, which are adaptations of
standard bin packing algorithms to the DVBP problem. An Any Fit packing
algorithm maintains a list $L$ of open bins, and does not open a new bin upon
the arrival of an item $r$, if $r$ can be packed into an open bin in $L$. Its
pseudocode is given in Algorithm 1.

Different Any Fit packing algorithms differ in how an open bin $b\in L$ is
selected to accommodate an item $r$ (Line 4), and how the list $L$ is modified
(Lines 9 and 12). In this work, we focus on the following four Any Fit packing
algorithms:

  * •

Move To Front. Bins in the list $L$ are maintained in order of most-recent
usage. Thus, when an item $r$ arrives, $r$ is placed in the bin $b$ which
appears earliest in $L$ and can accommodate $r$, else a new bin $b$ is opened.
Immediately $b$ is moved to the front of the list $L$ as it is the most
recently used bin.

  * •

First Fit. Bins in the list $L$ are maintained in increasing order of opening
time. Thus, an item $r$ is placed in the earliest open bin that can hold $r$.

  * •

Next Fit. At any given time, $|L|=1$, i.e., at each time Next Fit maintains
one open bin in $L$ as a designated current bin. When an item $r$ does not fit
into the current bin, the current bin is released and a new bin is opened to
pack $r$ and is made the current bin.

  * •

Best Fit. An item $r$ is placed in the “most-loaded” bin. When $d=1$, the load
of a bin containing a set of items $R$ is simply $\mathbf{s}(R)$. For $d\geq
2$, there is no unique way of computing the load $w(R)$ of set $R$ from the
load vector $\mathbf{s}(R)$. A few options are:

    * –

Max load, i.e., $w(R)=\lVert\mathbf{s}(R)\rVert_{\infty}$,

    * –

Sum of loads, i.e., $w(R)=\lVert\mathbf{s}(R)\rVert_{1}$,

    * –

$L_{p}$-norm of the load, i.e., $w(R)=\lVert\mathbf{s}(R)\rVert_{p}$, for
$p\geq 2$.

Algorithm 1 Any Fit Packing Algorithm

1:$L\leftarrow\\{b\\}$, where $b$ is an empty open bin $\triangleright$ List
of open bins

2:repeat:

3: if an item $r$ arrives then

4: if $r$ fits in an open bin of $L$ then

5: Choose a bin $b\in L$ that can hold $r$

6: else

7: Open a new bin $b$ and add $b$ to $L$

8: Pack item $r$ in bin $b$

9: Modify $L$ as needed

10: if an item $r$ departs then

11: Remove closed bins from $L$

12: Modify $L$ as needed

#### Competitive Ratio.

We measure the performance of an online algorithm $\mathcal{A}$ by its
competitive ratio, i.e., the worst-case ratio between the cost of the packing
produced by algorithm $\mathcal{A}$ and the cost of the packing produced by
the optimal offline algorithm which can repack items [4]. For a list of items
$\mathcal{R}$, denote the optimal, offline cost by
$\mathsf{OPT}(\mathcal{R})$. An algorithm $\mathcal{A}$ is said to be
$\alpha$-competitive (for $\alpha\geq 1$) if for all item lists $\mathcal{R}$,
we have
$\mathsf{cost}(\mathcal{A},\mathcal{R})\leq\alpha\cdot\mathsf{OPT}(\mathcal{R})$.
Naturally, we desire algorithms where $\alpha$ is as small as possible.

###  2.3 Lower bounds on the Optimum Cost

To analyze the competitive ratio of online algorithms, it is useful to place
lower bounds on the optimum cost. To this end, let
$\mathbf{s}(\mathcal{R},t)=\sum_{r\in\mathcal{R}:t\in I(r)}\mathbf{s}(r)$
denote the total size of items that are active at time $t$. Let
$\mathsf{OPT}(\mathcal{R},t)$ denote the number of bins the optimal offline
algorithm has open at time $t$, equivalently, it is the smallest number of
bins into which all items active at time $t$ can be repacked. Then:

$\mathsf{OPT}(\mathcal{R})=\int_{\min_{r\in\mathcal{R}}a(r)}^{\max_{r\in\mathcal{R}}e(r)}\mathsf{OPT}(\mathcal{R},t)dt.$
(2)

The following lemma presents $d$-dimensional generalizations of lower bounds
on OPT introduced in earlier works [22, 28].

######  Lemma 1.

The following are lower bounds on $\mathsf{OPT}(\mathcal{R})$.

  1. (i)

$\mathsf{OPT}(\mathcal{R})\geq\int_{\min_{r\in\mathcal{R}}a(r)}^{\max_{r\in\mathcal{R}}e(r)}\lceil\lVert\mathbf{s}(\mathcal{R},t)\rVert_{\infty}\rceil\>dt$

  2. (ii)

$\mathsf{OPT}(\mathcal{R})\geq\frac{1}{d}\sum_{r\in
R}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\ell(I(r))$

  3. (iii)

$\mathsf{OPT}(\mathcal{R})\geq\mathsf{span}(\mathcal{R})$

###### Proof.

The definition of $\mathbf{s}(\mathcal{R},t)$ and the size of bins being
$\mathbf{1}^{d}$ implies that any algorithm needs at least
$\lceil\mathbf{s}(\mathcal{R},t)_{j}\rceil$ bins to pack the total load on the
$j^{th}$ dimension, for any $j\in[d]$. Thus,
$\mathsf{OPT}(\mathcal{R},t)\geq\max_{j\in[d]}\lceil\mathbf{s}(\mathcal{R},t)_{j}\rceil=\lceil\lVert\mathbf{s}(\mathcal{R},t)\rVert_{\infty}\rceil$.
Using (2), we obtain (i).

Define the time-space utilization of an item $r$ as
$u(r)=\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\ell(I(r))$. The following shows
that the total time-space utilization of all items is a lower bound on
$d\cdot\mathsf{OPT}$, thus proving (ii).

$\displaystyle\mathsf{OPT}(\mathcal{R})$
$\displaystyle\geq\int_{\min_{r\in\mathcal{R}}a(r)}^{\max_{r\in\mathcal{R}}e(r)}\lVert\mathbf{s}(\mathcal{R},t)\rVert_{\infty}\>dt$
(using (i))
$\displaystyle\geq\int_{\min_{r\in\mathcal{R}}a(r)}^{\max_{r\in\mathcal{R}}e(r)}\bigg{\lVert}{\sum_{r:t\in
I(r)}\mathbf{s}(r)}\bigg{\rVert}_{\infty}dt$ (def of
$\mathbf{s}(\mathcal{R},t)$)
$\displaystyle\geq\frac{1}{d}\int_{\min_{r\in\mathcal{R}}a(r)}^{\max_{r\in\mathcal{R}}e(r)}\sum_{r:t\in
I(r)}\lVert\mathbf{s}(r)\rVert_{\infty}\>dt$ (using Prop 1)
$\displaystyle=\frac{1}{d}\sum_{r\in\mathcal{R}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\ell(I(r)).$
(swap order)

Lastly, observe that since at least one bin is needed for each time $t$ that
an item is active, we have $\mathsf{OPT}(\mathcal{R},t)\geq 1$ for each time
instant $t\in[0,\mathsf{span}(\mathcal{R}))$. Together with (2), this implies
(iii).

Note that the lower bound (i) is tighter than both (ii) and (iii). ∎

##  3 Upper Bound on the Competitive Ratio of Move To Front

In this section we prove the first main result of our paper.

######  Theorem 2.

The competitive ratio of Move To Front for the MinUsageTime Dynamic Vector Bin
packing problem in $d$-dimensions is at most $(2\mu+1)d+1$.

For $d=1$, our result implies that Move To Front has a competitive ratio of at
most $2\mu+2$. This significantly improves the result of Kamali and López-
Ortiz [18], who showed that Move To Front has an asymptotic competitive ratio
of $6\mu+7$, i.e., for any item list $\mathcal{R}$, they showed
$\mathsf{cost}(\text{MF},\mathcal{R})\leq(6\mu+7)\cdot\mathsf{OPT}(\mathcal{R})+3(\mu+1)$.
Our result also nearly settles their conjecture of the CR being $2\mu+1$.
Their analysis decomposes the active span into segments of length $(\mu+1)$
and compares the cost of OPT with the cost of Move To Front in each such
interval. It turns out that this decomposition is sub-optimal. Instead, we
directly use the nature of the Move To Front algorithm and develop a novel
decomposition of the usage periods of each bin $B$ into intervals based on
whether or not in the interval $B$ is the most recently used bin. We now prove
Theorem 2.

Suppose Move To Front uses $m$ bins $B_{1},B_{2},\dots,B_{m}$ on an input
sequence $\mathcal{R}$. As mentioned earlier, we can assume that
$\cup_{r\in\mathcal{R}}I(r)=[0,\mathsf{span}(\mathcal{R}))$ and that the usage
period of each bin is an interval For $i\in[m]$, let
$I_{i}=\mathsf{span}(R_{i})$ denote the usage period/active interval of bin
$B_{i}$, where $R_{i}$ is the set of items packed in $B_{i}$. The cost of Move
To Front (MF) can be expressed as
$\mathsf{cost}(MF,\mathcal{R})=\sum_{i=1}^{m}\ell(I_{i})$.

Recall that Move To Front maintains a list $L$ of open bins in the order of
their most-recent usage. We say a bin is a leader at time $t$ if it is in the
front of the list $L$ at time $t$. We call an interval $I$ a leading interval
for bin $B$ if $B$ is a leader at every time instant in $I$. If Move To Front
packs an item into a bin $B$, then $B$ is immediately made the leader. Thus,
if a bin $B$ is not a leader at time $t$, then it cannot accept a new item at
$t$. Based on the above definition, we partition the active interval of each
bin $B$ into intervals which alternate between leading intervals for $B$ and
non-leading intervals for $B$. Clearly the time at which a bin is opened
begins a leading period for the bin. Thus, for each $i\in[m]$, the interval
$I_{i}$ is sequentially partitioned into $2n_{i}$ (half-open) intervals as
$I_{i}=P_{i,1}\cup Q_{i,1}\cup P_{i,2}\cup Q_{i,2}\cup\cdots\cup
P_{i,n_{i}}\cup Q_{i,n_{i}}$, where each $P_{i,j}$ is a leading interval for
bin $B_{i}$ and $Q_{i,j}$ is a non-leading interval for $j\in[n_{i}]$. Since
empty intervals have zero cost, we can assume that all intervals except
perhaps the last non-leading intervals of each bin are non-empty, i.e.,
perhaps $Q_{i,n_{i}}=\emptyset$. This decomposition is illustrated in Figure 1
with red/thick lines representing leading intervals and blue/thin lines
representing non-leading intervals. Using this decomposition, one can write
the cost as:

$\mathsf{cost}(MF,\mathcal{R})=\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\bigg{(}\ell(P_{i,j})+\ell(Q_{i,j})\bigg{)}.$
(3)

Figure 1: Shows the usage periods of 3 bins used by Move To Front decomposed
into leading (red/thick intervals) and non-leading intervals (blue/thin
intervals). The span is also indicated.

We analyze the two summands of (3) separately. First we show:

######  Claim 1.

$\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\ell(P_{i,j})\leq\mathsf{OPT}(\mathcal{R}).$

###### Proof.

At each time $t$, exactly one bin is the leader, hence the leading intervals
of bins $B_{i}$ and $B_{i^{\prime}}$ are disjoint, i.e, $P_{i,j}\cap
P_{i^{\prime},j^{\prime}}=\emptyset$ for any $i,i^{\prime}\in[m]$,
$j\in[n_{i}]$, and $j^{\prime}\in[n_{i^{\prime}}]$. Since at each time
$t\in[0,\mathsf{span}(\mathcal{R}))$ some bin is the leader, one can
immediately observe that all the leading intervals partition the interval
$[0,\mathsf{span}(\mathcal{R}))$ (see Figure 1). Combined with Lemma 1 (iii),
we arrive at Claim 1:

$\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\ell(P_{i,j})=\mathsf{span}(\mathcal{R})\leq\mathsf{OPT}(\mathcal{R}).\qed$

We now analyze $\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\ell(Q_{i,j})$. For some
$i\in[m]$ and $j\in[n_{i}]$, consider a non-leading interval $Q_{i,j}$
beginning at time $t_{i,j}$, which is preceded by a leading interval $P_{i,j}$
which ends at $t_{i,j}$. The reason that bin $B_{i}$ ceased to be a leader at
time $t_{i,j}$ is because some other bin $B_{i^{\prime}}$ received a new item
$r_{i,j}$ and became the leader at time $t_{i,j}$. Thus, the algorithm was
unable to pack item $r_{i,j}$ in bin $B_{i}$, the previous leader. Let
$R_{i,j}\subseteq R_{i}$ be the set of items active in bin $i$ at the start of
the interval $Q_{i,j}$, i.e. at time $t_{i,j}$. Then it must be mean that for
some dimension $k\in[d]$, $(\mathbf{s}(r_{i,j})+\mathbf{s}(R_{i,j}))_{k}>1$,
or equivalently
$\lVert\mathbf{s}(r_{i,j})+\mathbf{s}(R_{i,j})\rVert_{\infty}>1$. Together
with Proposition 1, we obtain:

$\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\ell(Q_{i,j})<\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(r_{i,j})+\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(Q_{i,j})$
(4)
$\displaystyle\leq\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(r_{i,j})\rVert_{\infty}\cdot\ell(Q_{i,j})+\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(Q_{i,j}),$

We analyze the two summands of (4) separately. First we show:

######  Claim 2.

$\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(r_{i,j})\rVert_{\infty}\cdot\ell(Q_{i,j})\leq\mu\cdot
d\cdot\mathsf{OPT}(\mathcal{R}).$

###### Proof.

Observe that since no new item is packed in a bin $B_{i}$ during a non-leading
interval $Q_{i,j}$, we have $\ell(Q_{i,j})\leq\mu$, since each item has a
duration of at most $\mu$. Moreover, the items $r_{i,j}$ are distinct, since
each $r_{i,j}$ is uniquely associated with the interval $Q_{i,j}$. Using these
observations, we obtain the claim as follows:

$\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(r_{i,j})\rVert_{\infty}\cdot\ell(Q_{i,j})\leq\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(r_{i,j})\rVert_{\infty}\cdot\mu$
$\displaystyle\leq\mu\cdot\bigg{(}\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(r_{i,j})\rVert_{\infty}\cdot\ell(I(r_{i,j}))\bigg{)}\quad\>(\text{since
}\ell(I(r))\geq 1)$
$\displaystyle\leq\mu\cdot\bigg{(}\sum_{r\in\mathcal{R}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\ell(I(r))\bigg{)}$
$\displaystyle\leq\mu\cdot
d\cdot\mathsf{OPT}(\mathcal{R}).\quad\qquad\qquad\qquad\qquad\text{(using
Lem.~{}\ref{lem:lb-opt} (ii))}$

∎

We next analyze the second summand of (4).

######  Claim 3.

$\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(Q_{i,j})\leq(\mu+1)\cdot
d\cdot\mathsf{OPT}(\mathcal{R})$.

###### Proof.

Using Proposition 1, observe the following:

$\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(Q_{i,j})\leq\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\sum_{r\in
R_{i,j}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\ell(Q_{i,j})$ (5)
$\displaystyle=\sum_{i=1}^{m}\sum_{r\in
R_{i}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\bigg{(}\sum_{j\in[n_{i}]:r\in
R_{i,j}}\ell(Q_{i,j})\bigg{)},$

where the last equality follows by changing the order of summation.

Consider an item $r\in R_{i}$, and let $j^{-},j^{+}\in[n_{i}]$ be such that
$r\in R_{i,j}$ for all $j\in[j^{-},j^{+}]$, i.e., item $r$ is active during
the intervals $Q_{i,j^{-}},\dots,Q_{i,j^{+}}$. Since $r$ is active during the
start of each interval $Q_{i,j}$ for each $j\in[j^{-},j^{+}]$, we have
$\cup_{j=j^{-}}^{j^{+}-1}\ell(Q_{i,j})\subseteq I(r)$. This implies:

$\sum_{j\in[n_{i}]:r\in
R_{i,j}}\ell(Q_{i,j})=\sum_{j=j^{-}}^{j^{+}-1}\ell(Q_{i,j})+\ell(Q_{i,j^{+}})\leq\ell(I(r))+\mu,$
(6)

where we used $\ell(Q_{i,j^{+}})\leq\mu$. Using the above in eq. (5), we
obtain:

$\displaystyle\sum_{i=1}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(Q_{i,j})$
$\displaystyle\leq\sum_{i=1}^{m}\sum_{r\in
R_{i}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\bigg{(}\sum_{j\in[n_{i}]:r\in
R_{i,j}}\ell(Q_{i,j})\bigg{)}$ (from (5))
$\displaystyle\leq\sum_{i=1}^{m}\sum_{r\in
R_{i}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot(\ell(I(r))+\mu)$ (from (6))
$\displaystyle\leq(\mu+1)\cdot\bigg{(}\sum_{r\in\mathcal{R}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\ell(I(r)))\bigg{)}$
(since $\ell(I(r))\geq 1$) $\displaystyle\leq(\mu+1)\cdot
d\cdot\mathsf{OPT}(\mathcal{R}),$ (using Lem. 1 (ii))

thus proving Claim 3. ∎

Claims 1,2 and 3 together with equations (3) and (4) imply:

$\mathsf{cost}(MF,\mathcal{R})\leq((2\mu+1)d+1)\cdot\mathsf{OPT}(\mathcal{R}),$

thus proving Theorem 2.

##  4 Upper Bound on the Competitive Ratio of First Fit

In this section, we prove an upper bound on the CR of First Fit.

######  Theorem 3.

The competitive ratio of First Fit for the MinUsageTime Dynamic Vector Bin
packing problem is at most $(\mu+2)d+1$.

Let $B_{1},\dots,B_{m}$ be the bins used by First Fit (FF) to pack an item
sequence $\mathcal{R}$. For $i\in[m]$, let $R_{i}\subseteq\mathcal{R}$ be the
items packed in bin $B_{i}$, and let $I_{i}=[I_{i}^{-},I_{i}^{+})$ denote the
active interval of $B_{i}$. We assume bins are indexed according to their
opening times, i.e., $I_{1}^{-}\leq\dots\leq I_{m}^{-}$.

Figure 2: Shows the decomposition of the usage periods of 3 bins used by First
Fit. The span is also indicated.

The cost of the First Fit packing is given by
$\mathsf{cost}(FF,\mathcal{R})=\sum_{i=1}^{m}\ell(I_{i})$. Following the ideas
of [28], we decompose each interval $I_{i}$ as follows. Let $t_{i}$ denote the
latest closing time of bins opened before $B_{i}$, i.e.,
$t_{i}=\max(I_{i}^{-},\max_{j<i}I_{j}^{+})$. Then we partition
$I_{i}=P_{i}\cup Q_{i}$, where $P_{i}=[I_{i}^{-},\min(I_{i}^{+},t_{i}))$ and
$Q_{i}=[\min(I_{i}^{+},t_{i}),I_{i}^{+})$. Note that $P_{1}=\emptyset$. The
decomposition is illustrated in Figure 2. Therefore, the cost of the packing
is:

$\mathsf{cost}(FF,\mathcal{R})=\sum_{i=2}^{m}\ell(P_{i})+\sum_{i=1}^{m}\ell(Q_{i}).$
(7)

######  Claim 4.

$\sum_{i=1}^{m}\ell(Q_{i})=\mathsf{span}(\mathcal{R})\leq\mathsf{OPT}(\mathcal{R}).$

###### Proof.

The claim follows directly from the definition of the decomposition (see Fig.
2) and Lemma 1 (iii). ∎

Let us now define $R^{\prime}_{i}\subseteq R_{i}$ to be an inclusion-wise
minimal cover of the interval $P_{i}$. That is, the union of active intervals
of items in $R^{\prime}_{i}$ covers $P_{i}$, but any $J\subset R^{\prime}_{i}$
does not cover $P_{i}$. Let $r_{i,1},\dots,r_{i,n_{i}}$ be the $n_{i}$ items
in $R^{\prime}_{i}$, sorted by their arrival time. By the minimality of
$R^{\prime}_{i}$, each item in $R^{\prime}_{i}$ has a distinct arrival time.
Thus we can index the items so that
$a(r_{i,1})<a(r_{i,2})<\dots<a(r_{i,n_{i}})$. Moreover, the minimality of
$R^{\prime}_{i}$ also implies that ending times of the items are in sorted
order, i.e., $e(r_{i,1})<e(r_{i,2})<\dots<e(r_{i,n_{i}})$; if not, an item can
be removed from $R^{\prime}_{i}$ while still covering $P_{i}$, thus
contradicting the minimality of $R^{\prime}_{i}$.

We now decompose each non-empty interval $P_{i}$ into $n_{i}$ disjoint periods
$P_{i}=P_{i,1}\cup\dots\cup P_{i,n_{i}}$ where
$P_{i,j}=[a(r_{i,j}),a(r_{i,j+1}))$ for $1\leq j<n_{i}$ and
$P_{i,n_{i}}=[a(r_{i,n_{i}}),\min(I_{i}^{+},t_{i}))$. Since this is a
partition of $P_{i}$, we have $\ell(P_{i})=\sum_{j=1}^{n_{i}}\ell(P_{i,j})$
for each $i\geq 2$.

For an item $r_{i,j}\in R^{\prime}_{i}$, we refer to the largest index bin
with index less than $i$ which is open at time $a(r_{i,j})$ as the blocking
bin666[28] use the terminology supplier bin instead $B(i,j)$ for the item
$r_{i,j}$ and the interval $P_{i,j}$. Note that since an item $r_{i,j}$ is
placed in bin $B_{i}$, all previously opened bins including the blocking bin
$B(i,j)$ could not pack $r_{i,j}$ when it arrived. Thus:

$\lVert\mathbf{s}(r_{i,j})+\mathbf{s}(R_{i,j})\rVert_{\infty}>1,$

where $R_{i,j}$ is the set of items in $B(i,j)$ that are active at time
$a(r_{i,j})$. Using this, we have:

$\displaystyle\sum_{i=2}^{m}\sum_{j=1}^{n_{i}}\ell(P_{i,j})<\sum_{i=2}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(r_{i,j})+\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(P_{i,j})$
(8)
$\displaystyle\leq\sum_{i=2}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(r_{i,j})\rVert_{\infty}\cdot\ell(P_{i,j})+\sum_{i=2}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(P_{i,j}),$

We analyze the summands of (8) separately. We first have:

######  Claim 5.

$\sum_{i=2}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(r_{i,j})\rVert_{\infty}\cdot\ell(P_{i,j})\leq
d\cdot\mathsf{OPT}(\mathcal{R}).$

###### Proof.

By definition of $P_{i,j}$, we have $P_{i,j}\subseteq I(r_{i,j})$. Thus,
$\ell(P_{i,j})\leq\ell(I(r_{i,j}))$. Lemma 1 (ii) then proves the claim. ∎

The next claim analyzes the second summand of (8).

######  Claim 6.

$\sum_{i=2}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(P_{i,j})\leq(\mu+1)\cdot
d\cdot\mathsf{OPT}(\mathcal{R}).$

###### Proof.

Let $\hat{R}=\cup_{i=2}^{m}\cup_{j=1}^{n_{i}}R_{i,j}$ be the set of all items
belonging to bins considered as blocking bins by items in
$\\{R^{\prime}_{i}\\}_{i\geq 2}$. We have:

$\displaystyle\sum_{i=2}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(P_{i,j})\leq\sum_{i=2}^{m}\sum_{j=1}^{n_{i}}\sum_{r\in
R_{i,j}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\ell(P_{i,j})$ (9)
$\displaystyle=\sum_{r\in\hat{R}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\bigg{(}\sum_{(i,j):r\in
R_{i,j}}\ell(P_{i,j})\bigg{)},$

where the last inequality follows by changing the order of summation. Now for
a fixed $r\in\hat{R}$ which is packed in some bin $B$, consider two distinct
items $r_{i,j}$ and $r_{i^{\prime},j^{\prime}}$ s.t. $r\in R_{i,j}\cap
R_{i^{\prime},j^{\prime}}$. We will show that $P_{i,j}\cap
P_{i^{\prime},j^{\prime}}=\emptyset$.

  * •

For $i=i^{\prime}$, this follows from the fact that
$\\{P_{i,j}\\}_{j=1}^{n_{i}}$ partitions $P_{i}$.

  * •

For $i\neq i^{\prime}$, let $i<i^{\prime}$ w.l.o.g. Then since $r_{i,j}$ and
$r_{i^{\prime},j^{\prime}}$ have the same blocking bin $B$, it must be the
case that when $r_{i^{\prime},j^{\prime}}$ arrives, $B_{i}$ must be closed,
otherwise $B_{i}$ would be the blocking bin for $r_{i^{\prime},j^{\prime}}$.
Thus, $r_{i,j}$ must have departed when $r_{i^{\prime},j^{\prime}}$ arrives,
implying that $P_{i,j}\cap P_{i^{\prime},j^{\prime}}=\emptyset$.

Thus for a given $r\in\hat{R}$, the set of intervals $P_{i,j}$ s.t. $r\in
R_{i,j}$ are pairwise disjoint. Hence we can observe that for each
$r\in\hat{R}$:

$\sum_{(i,j):r\in R_{i,j}}\ell(P_{i,j})\leq\max_{(i,j):r\in
R_{i,j}}e(r_{i,j})-\min_{(i,j):r\in R_{i,j}}a(r_{i,j}).$ (10)

Note that since each $r\in\hat{R}$ is active at the arrival time of an item
$r_{i,j}$ s.t. $r\in R_{i,j}$, we have $a(r)\leq a(r_{i,j})\leq e(r)$. Thus,
$e(r_{i,j})\leq\mu+a(r_{i,j})\leq\mu+e(r)$. Putting these in (10), we obtain:

$\sum_{(i,j):r\in
R_{i,j}}\ell(P_{i,j})\leq\mu+e(r)-a(r)\leq\mu+\ell(I(r))\leq(\mu+1)\cdot\ell(I(r)).$

Using the above in (9) with Lemma 1 (ii), we see that

$\displaystyle\sum_{i=2}^{m}\sum_{j=1}^{n_{i}}\lVert\mathbf{s}(R_{i,j})\rVert_{\infty}\cdot\ell(P_{i,j})\leq\sum_{r\in\hat{R}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\bigg{(}\sum_{(i,j):r\in
R_{i,j}}\ell(P_{i,j})\bigg{)}$
$\displaystyle\leq(\mu+1)\cdot\sum_{r\in\hat{R}}\lVert\mathbf{s}(r)\rVert_{\infty}\cdot\ell(I(r))\leq(\mu+1)\cdot
d\cdot\mathsf{OPT}(\mathcal{R}),$

thus proving the claim. ∎

Claims 4, 5 and 6 together with equations (7) and (8) imply:

$\mathsf{cost}(FF,\mathcal{R})\leq((\mu+2)d+1)\cdot\mathsf{OPT}(\mathcal{R}),$

thus proving Theorem 3.

##  5 Upper Bound on the Competitive Ratio of Next Fit

In this section, we prove an upper bound on the CR of Next Fit.

######  Theorem 4.

The competitive ratio of Next Fit for the MinUsageTime Dynamic Vector Bin
packing problem is at most $2\mu d+1$.

Let $B_{1},\dots,B_{m}$ be the bins used by Next Fit (NF) to pack an item
sequence $\mathcal{R}$. As before, for $i\in[m]$, let
$R_{i}\subseteq\mathcal{R}$ be the items packed in bin $B_{i}$, and let
$I_{i}$ denote the active interval of $B_{i}$. We have
$\mathsf{cost}(NF,\mathcal{R})=\sum_{i=1}^{m}\ell(I_{i})$.

Recall that Next Fit maintains one current bin at a time into which it tries
to pack incoming items. Following [18], we decompose the usage period $I_{i}$
of a bin $B_{i}$ into two intervals $P_{i}$ and $Q_{i}$ based on when Next Fit
considered $B_{i}$ as the current bin. We decompose the interval
$I_{i}=[I_{i}^{-},I_{i}^{+})$ as $I_{i}=P_{i}\cup Q_{i}$, where
$P_{i}=[I_{i}^{-},t_{i})$ and $Q_{i}=[t_{i},I_{i}^{+})$, with $t_{i}\in I_{i}$
denoting the time at which $B_{i}$ was released. Thus, $P_{i}$ is the time
period when $B_{i}$ was considered the current bin and $Q_{i}$ is the time
period when $B_{i}$ ceased to the current bin.

Using the above interval-decomposition, we can write the cost as
$\mathsf{cost}(NF,\mathcal{R})=\sum_{i=1}^{m}\ell(P_{i})+\sum_{i=1}^{m}\ell(Q_{i})$.
Note that at each time $t$, exactly one bin is current, hence $P_{i}\cap
P_{i^{\prime}}=\emptyset$ for all $i\neq i^{\prime}$. Further at each time
some bin is current, hence we conclude that the intervals
$\\{P_{i}\\}_{i\in[m]}$ partition the interval
$[0,\mathsf{span}(\mathcal{R})]$. Together with Lemma 1 (iii), this gives:

$\sum_{i=1}^{m}\ell(P_{i})=\mathsf{span}(\mathcal{R})\leq\mathsf{OPT}(\mathcal{R}).$
(11)

Next, observe that at a bin $B_{i}$ was released at time $t_{i}$ because an
item $r_{i}$ could not be packed into $B_{i}$. This means:

$\lVert\mathbf{s}(R^{\prime}_{i})+\mathbf{s}(r_{i})\rVert_{\infty}>1,$ (12)

where $R^{\prime}_{i}\subseteq R_{i}$ denotes the items packed in $B_{i}$
which are active at $t_{i}$. Moreover, since a bin $B_{i}$ is released at
$t_{i}$, it does not receive any new item in the period $Q_{i}$. Thus
$\ell(Q_{i})\leq\mu$, for each $i\in[m]$. We use these observations to prove
the following.

$\displaystyle\sum_{i=1}^{m}\ell(Q_{i})<\sum_{i=1}^{m}\lVert\mathbf{s}(R^{\prime}_{i})+\mathbf{s}(r_{i})\rVert_{\infty}\cdot\ell(Q_{i})$
(using (12))
$\displaystyle\leq\mu\cdot\sum_{i=1}^{m}\lVert\mathbf{s}(R^{\prime}_{i})+\mathbf{s}(r_{i})\rVert_{\infty}$
(since $\ell(Q_{i})\leq\mu$)
$\displaystyle\leq\mu\cdot\sum_{i=1}^{m}\sum_{r\in
R^{\prime}_{i}}\lVert\mathbf{s}(r)\rVert_{\infty}+\mu\cdot\sum_{i=1}^{m}\lVert\mathbf{s}(r_{i})\rVert_{\infty}$
(using Prop. 1) $\displaystyle\leq
2\mu\cdot\sum_{r\in\mathcal{R}}\lVert\mathbf{s}(r)\rVert_{\infty}\leq
2\mu\cdot d\cdot\mathsf{OPT}(\mathcal{R}),$ (using Lemma 1 (ii))

where the last transition uses the observation that each item
$r\in\mathcal{R}$ can appear in the summation at most twice: once in some
$R^{\prime}_{i}$ and once as some $r_{i}$. Together with (11), we conclude
that $\mathsf{cost}(NF,\mathcal{R})\leq(2\mu
d+1)\cdot\mathsf{OPT}(\mathcal{R})$, thus proving Theorem 4.

##  6 Lower Bounds on the Competitive Ratio of Any Fit Packing Algorithms

In this section, we prove lower bounds on the competitive ratio of algorithms
belonging to the Any Fit packing algorithm family. Our first result applies to
all algorithms in this family.

######  Theorem 5.

The competitive ratio of any Any Fit packing algorithm for the MinUsageTime
Dynamic Vector Bin Packing problem in $d$-dimensions is at least $(\mu+1)d$.

###### Proof.

We present the following worst-case adversarial example against which any Any
Fit algorithm $\mathcal{A}$ has competitive ratio at least $(\mu+1)d$. Let
$k\geq 1$ be a parameter. Let $\varepsilon,\varepsilon^{\prime}\in(0,1)$ be
such that $\varepsilon>\varepsilon^{\prime}$, $d^{2}\varepsilon k<1$,
$d\varepsilon>2\varepsilon^{\prime}$, and $\varepsilon(1+d)<1$.

We first construct a sequence of $n=2\cdot d\cdot k$ items labelled as
$\mathcal{R}_{0}=\\{1,2,\dots,2dk-1,2dk\\}$. To specify the size of the items,
we partition them into groups $G_{0},G_{1},G_{2},\dots,$ and $G_{d}$. Here
$G_{0}=\\{j\in[2dk]:j\text{ is even}\\}$ is the set of even-indexed items. The
size of an item $j$ in $G_{0}$ is the following vector:

$\mathbf{s}(j)=\begin{bmatrix}d\varepsilon-\varepsilon^{\prime}&&d\varepsilon-\varepsilon^{\prime}&&\cdots&&d\varepsilon-\varepsilon^{\prime}\end{bmatrix},$

i.e., a vector equal to
$(d\varepsilon-\varepsilon^{\prime})\cdot\mathbf{1}^{d}$.

For $i\in[d]$, the group $G_{i}$ is the set $\\{2m-1:(i-1)\cdot k+1\leq m\leq
i\cdot k\\}$ of $k$ items, i.e., odd-indexed items in the range
$[2(i-1)k+1,2ik]$. The size of an item $j\in G_{i}$ is the vector with
$(1-d\varepsilon)$ in the $i^{th}$ dimension and $\varepsilon$ everywhere
else, i.e.,

$\mathbf{s}(j)=\begin{bmatrix}\varepsilon&&\cdots&&(1-d\varepsilon)&&\cdots&&\varepsilon\end{bmatrix}.$

The items $\mathcal{R}_{0}=\\{1,2,\dots,2dk\\}$ arrive in that order at time
0, and their active interval is $[0,1)$. Consider the execution of an Any Fit
packing algorithm $\mathcal{A}$. Items $1$ and $2$ are initially placed into a
single bin $B_{1}$ after which the bin is loaded at
$(1-d\varepsilon+d\varepsilon-\varepsilon^{\prime})=1-\varepsilon^{\prime}$ in
dimension 1. Now no item $j$ for $j\geq 3$ cannot be packed into $B_{1}$ since
the load in dimension 1 would exceed the capacity as we have
$1-\varepsilon^{\prime}+\varepsilon>1$ and
$1-\varepsilon^{\prime}+(d\varepsilon-\varepsilon^{\prime})>1$. Hence another
bin $B_{2}$ is opened. Continuing in this manner, one can observe that at
least $dk$ bins $B_{1},B_{2},\dots,B_{dk}$ are created, with bins
$B_{(i-1)k+1},\dots,B_{ik}$ being loaded at level $(1-\varepsilon^{\prime})$
in dimension $i$ and at $(\varepsilon+d\varepsilon-\varepsilon^{\prime})$ in
other dimensions, for $i\in[d]$. Thus,
$\mathsf{cost}(\mathcal{A},\mathcal{R}_{0})\geq dk$.

On the other hand, $\mathsf{OPT}(\mathcal{R}_{0})\leq k+1$. This is because
all the even-indexed items of $G_{0}$ can be packed into one bin $B_{0}$ since
$(d\varepsilon-\varepsilon^{\prime})\cdot(dk)<1$. The remaining items can be
packed into $k$ bins, each of which contains exactly one item from $G_{i}$,
for each $i\in[d]$. This is a feasible packing since the load on the $j^{th}$
dimension of any such bin is
$(1-d\varepsilon)+(d-1)\cdot\varepsilon=1-\varepsilon<1$.

We now introduce a sequence $\mathcal{R}_{1}$ of $dk$ identical items, each of
which are loaded at $\varepsilon^{\prime}$ in each dimension. These items
arrive just before any items of $\mathcal{R}_{0}$ depart and their active
interval is $[1,\mu+1)$. Consider the execution of $\mathcal{A}$ on
$\mathcal{R}_{0}\cup\mathcal{R}_{1}$. As argued earlier, $\mathcal{A}$ opens
at least $dk$ bins which are loaded at at most $(1-\varepsilon^{\prime})$ in
each dimension (since $(1+\varepsilon)d<1$, and exactly at
$(1-\varepsilon^{\prime})$ in one dimension. Thus, each item of
$\mathcal{R}_{1}$ will be packed in a separate bin by $\mathcal{A}$. This is
because $\mathcal{A}$ is an Any Fit packing algorithm and will not open a new
bin since the $dk$ items of $\mathcal{R}_{1}$ can be packed in the $dk$ bins
created by $\mathcal{A}$ while packing $\mathcal{R}_{0}$. Subsequently, items
in $\mathcal{R}_{0}$ depart, and each of the $dk$ bins contain one item each
from $\mathcal{R}_{1}$ in the period $[1,\mu+1)$. Thus we have
$\mathsf{cost}(\mathcal{A},\mathcal{R}_{0}\cup\mathcal{R}_{1})\geq dk(1+\mu)$.

On the other hand, the optimal algorithm can pack all items of
$\mathcal{R}_{1}$ into the bin $B_{0}$ which held all even-indexed items,
since
$(d\varepsilon-\varepsilon^{\prime})dk+dk\cdot\varepsilon^{\prime}=d^{2}\varepsilon
k<1$. Thus only bin $B_{0}$ has an usage period of length $\mu+1$ while the
remaining $k$ bins have a usage period of length $1$ since they only contain
items from $\mathcal{R}_{0}$. Thus,
$\mathsf{OPT}(\mathcal{R}_{0}\cup\mathcal{R}_{1})\leq k+1+\mu$. Thus the
competitive ratio of $\mathcal{A}$ is:

$CR(\mathcal{A})\geq\frac{\mathsf{cost}(\mathcal{A},\mathcal{R}_{0}\cup\mathcal{R}_{1})}{\mathsf{OPT}(\mathcal{R}_{0}\cup\mathcal{R}_{1})}\geq\frac{dk(\mu+1)}{k+\mu+1}=\frac{(\mu+1)d}{1+(\mu+1)/k}$

Since $k$ is an arbitrary parameter, in the limit $k\rightarrow\infty$, we
have $CR(\mathcal{A})\geq(\mu+1)d$ for any Any Fit packing algorithm
$\mathcal{A}$, proving the claimed lower bound. ∎

Figure 3: Illustrates the load on bins used by any Any Fit packing algorithm
$\mathcal{A}$ on the item list $\mathcal{R}_{0}\cup\mathcal{R}_{1}$. Part (a)
shows $\mathcal{A}$ opens $dk$ bins in the time period $[0,1)$ where bins
$B_{(i-1)k+1},\dots,B_{ik}$ have load $1-\varepsilon^{\prime}$ in dimension
$i$. Part (b) shows that $\mathcal{A}$ packs $dk$ items of $\mathcal{R}_{1}$
at time $1$, fully loading each bin $B_{(i-1)k+1},\dots,B_{ik}$ in dimension
$i$. Part (c) shows the time period $[1,\mu+1)$ when items of
$\mathcal{R}_{0}$ have departed and each bin contains one item from
$\mathcal{R}_{1}$.

The execution of any Any Fit packing algorithm $\mathcal{A}$ on the item list
$\mathcal{R}_{0}\cup\mathcal{R}_{1}$ in illustrated in Figure 3. We now prove
a stronger lower bound against Next Fit using a different construction.

######  Theorem 6.

The competitive ratio of Next Fit for the MinUsageTime Dynamic Vector Bin
Packing problem is at least $2\mu d$.

###### Proof.

We present the following worst-case adversarial example against which Next Fit
has a competitive ratio at least $2\mu d$. Let $k\geq 2$ be an even integer.
Let $\varepsilon,\varepsilon^{\prime}\in(0,1)$ be such that
$\varepsilon^{\prime}>2d\varepsilon$ and $\varepsilon^{\prime}dk<1$. We
construct a sequence of $n=2\cdot d\cdot k$ items labelled as
$\mathcal{R}=\\{1,2,\dots,2dk\\}$. As before, we partition the items into
groups $G_{0},G_{1},\dots,G_{d}$, where $G_{0}=\\{j\in[2dk]:j\text{ is
even}\\}$ is the set of even-indexed items. The size of an item $j\in G_{0}$
is $\varepsilon^{\prime}\cdot\mathbf{1}^{d}$, i.e.,

$\mathbf{s}(j)=\begin{bmatrix}\varepsilon^{\prime}&&\varepsilon^{\prime}&&\cdots&&\varepsilon^{\prime}\end{bmatrix}.$

For $i\in[d]$, the group $G_{i}$ is the set $\\{2m-1:(i-1)\cdot k+1\leq m\leq
i\cdot k\\}$ of $k$ items, i.e., odd-indexed items in the range
$[2(i-1)k+1,2ik]$. The size of an item $j\in G_{i}$ is the vector with
$(1-d\varepsilon)$ in the $i^{th}$ dimension and $\varepsilon$ everywhere
else, i.e.,

$\mathbf{s}(j)=\begin{bmatrix}\varepsilon&&\cdots&&(\frac{1}{2}-d\varepsilon)&&\cdots&&\varepsilon\end{bmatrix}.$

Items $\mathcal{R}=\\{1,2,\dots,2dk\\}$ arrive in that order at time 0. The
active interval of items in $G_{0}$ is $[0,\mu)$ and of those in
$\cup_{i=1}^{d}G_{i}$ is $[0,1)$.

Consider the execution of Next Fit (NF) on $\mathcal{R}$. Items $1$ and $2$
are placed in one bin $B_{1}$, which is then loaded at
$1/2-d\varepsilon+\varepsilon^{\prime}$. Item $3$ does not fit in $B_{1}$
since the load on dimension 1 would then be
$2(1/2-d\varepsilon)+\varepsilon^{\prime}>1$. Thus NF closes $B_{1}$ and opens
a bin $B_{2}$ to accommodate item $3$, after which item $4$ is also placed in
$B_{2}$. Continuing this way, one observes that NF creates $k$ bins to pack
the items $\\{1,2,\dots,2k\\}$, with the last bin $B_{k}$ being loaded at
$(1/2-d\varepsilon+\varepsilon^{\prime})$ in dimension 1 and
$(\varepsilon+\varepsilon^{\prime})$ in other dimensions. Subsequently, items
$(2k+1)$ which is loaded at $(1/2-d\varepsilon)$ in dimension 2, and
item$(2k+2)$ can also be placed in $B_{k}$, since
$(\varepsilon+\varepsilon^{\prime}+1/2-d\varepsilon+\varepsilon^{\prime})<1$.
This loads the bin $B_{k}$ at
$(1/2-d\varepsilon+\varepsilon+2\varepsilon^{\prime})$ in dimension 2.
Consequently, item $(2k+3)$ cannot be placed in this bin since it has load
$(1/2-d\varepsilon)$ in dimension 2. Thus NF closes $B_{k}$ and opens another
bin. It can be seen that for the rest of the items in $\\{2k+3,\dots,4k\\}$,
NF opens $(k-1)$ bins, similar to the execution on items $\\{1,\dots,2k\\}$.
Continuing this way for $(d-1)$ more phases, with phase $i$ corresponding to
packing of the items in $\\{2(i-1)k+1,\dots,2ik\\}$ for $2\leq i\leq d$, one
can observe that NF opens $k+(k-1)+\cdots+(k-1)=1+(k-1)d$ bins. Since each bin
contains at least one even-indexed item, each bin is active for a duration of
$\mu$. Thus, $\mathsf{cost}(NF,\mathcal{R})\geq(1+(k-1)d)\mu$.

On the other hand, $\mathsf{OPT}(\mathcal{R})\leq\mu+k/2$. This is because the
optimal algorithm can pack all items of $G_{0}$ into a single bin, since
$\varepsilon^{\prime}\cdot dk<1$. This bin will be active in the interval
$[0,\mu)$, leading to a cost of $\mu$. The remaining items can be packed into
$k/2$ bins, each of which contains exactly two items from $G_{i}$, for each
$i\in[d]$. This is a feasible packing since the load on the $j^{th}$ dimension
of any such bin is $2\cdot(1/2-d\varepsilon)+(d-1)\cdot
2\cdot\varepsilon=1-2\varepsilon<1$. Each such bin is active for the interval
$[0,1)$, contributing a cost of 1. Thus the competitive ratio of Next Fit
satisfies:

$CR(NF)\geq\frac{\mathsf{cost}(NF,\mathcal{R})}{\mathsf{OPT}(\mathcal{R})}\geq\frac{(1+(k-1)d)\mu}{\mu+k/2}=\frac{2\mu(d+\frac{1}{k-1})}{\frac{k}{k-1}+\frac{2\mu}{k-1}}.$

Since $k$ is arbitrary, in the limit $k\rightarrow\infty$, we have $CR(NF)\geq
2\mu d$, proving the claimed lower bound. ∎

Note that our lower bounds (Theorems 5 and 6) match the lower bound of
$(\mu+1)$ for Any Fit packing algorithms [22, 28] and $2\mu$ for Next Fit [32]
for the one-dimensional case. However the one-dimensional examples of [22, 32]
do not generalize to multiple dimensions, and hence the new constructions of
Theorems 5 and 6 are needed. We also record that the competitive ratio of Best
Fit can be unbounded, even for $d=1$, as was shown in [22].

######  Theorem 7 ([22]).

The competitive ratio of Best Fit for the MinUsageTime Dynamic Vector Bin
Packing problem is unbounded.

Lastly, we examine the competitive ratio of Move To Front.

######  Theorem 8.

The competitive ratio of the Move To Front algorithm for the MinUsageTime
Dynamic Vector Bin Packing problem is at least $\max\\{2\mu,(\mu+1)d\\}$.

###### Proof.

Note that the lower bound of $(\mu+1)d$ follows from Theorem 5 since Move To
Front is an Any Fit packing algorithm. For the lower bound of $2\mu$, consider
the following one-dimensional example.

For a parameter $n\geq 1$, let $\mathcal{R}=\\{1,2,\dots,4n\\}$ be a sequence
of $4n$ items which arrive in that order at time $0$. The odd-indexed items
have size $1/2$ and active interval $[0,1)$. The even-indexed items have size
$1/(2n)$ and active interval $[0,\mu)$.

Consider the execution of Move To Front on $\mathcal{R}$. Items $1$ and $2$
are placed into a single bin $B_{1}$, which is then loaded at $1/2+1/(2n)$.
Therefore item 3 does not fit into bin $B_{1}$, and a new bin $B_{2}$ is
opened to accommodate item $3$. Since $B_{2}$ is now the most-recently used
bin, it is moved ahead of $B_{1}$, and therefore receives the next item $4$,
leading to a load of $1/2+1/(2n)$. Now item $5$ cannot be placed in either
$B_{1}$ or $B_{2}$, causing another bin to be opened. Continuing this way, we
can observe that Move To Front (MF) will create $2n$ bins. Since each bin
contains an even-indexed item, each bin will be active for a duration of
$\mu$. Thus $\mathsf{cost}(MF,\mathcal{R})=2n\cdot\mu$.

On the other hand, the optimum algorithm can pack all the even-indexed items
into one bin since there are $2n$ such items of size $1/(2n)$. This bin is
active in $[0,\mu)$. The remaining $2n$ odd-indexed items of size $1/2$ each
can be paired up an placed in $n$ bins, each of which is active in $[0,1)$
This implies $\mathsf{OPT}(\mathcal{R})\leq\mu+n$. Thus the competitive ratio
of Move To Front satisfies:

$CR(MF)\geq\frac{\mathsf{cost}(MF,\mathcal{R})}{\mathsf{OPT}(\mathcal{R})}\geq\frac{2n\mu}{\mu+n}=\frac{2\mu}{1+\frac{\mu}{n}}.$

Since $n$ is arbitrary, in the limit $n\rightarrow\infty$, we have $CR(NF)\geq
2\mu$, proving the claimed lower bound. We note that the same example was used
by [28, 32] to establish a lower bound of $2\mu$ on the competitive ratio of
Next Fit. ∎

######  Remark 1.

The above theorem implies that the lower bound is $2\mu$ for $d=1$, and
$(\mu+1)d$ for $d\geq 2$. We leave improving the lower bound of Move To Front
for $d\geq 2$ as an interesting open question.

##  7 Experimental Evaluation

In this section, we perform an experimental study evaluating the average-case
performance of several Any Fit packing algorithms.

#### Experimental Setup.

In addition to Move To Front, First Fit and Next Fit, we study the following
Any Fit algorithms:

  1. 1.

Best Fit, with the load of a bin containing a set $R$ of items is defined as
$w(R)=\lVert\mathbf{s}(R)\rVert_{\infty}$.

  2. 2.

Worst Fit, which tries to place an item in the least loaded bin.

  3. 3.

Last Fit, which in contrast with First Fit, tries to place an item in the bin
which with the latest opening time.

  4. 4.

Random Fit, which tries to place an item in a bin selected uniformly at random
from the list of open bins.

We evaluate the performance of these algorithms on randomly-generated input
sequences. Our experimental setup closely follows the setup of [18] for the
1-D case. In $d$-dimensions, we assume that each bin has size
$\mathbf{B}^{d}$, for integers $d,B\geq 1$. Each item is assumed to have a
size in $\\{1,2,\dots,B\\}^{d}$. For an integral value $T$ of the span, we
assume each item arrives at an integral time step in $[0,T-\mu]$ and has an
integral duration in $[1,\mu]$, for integral $\mu\geq 1$. Each instance in our
experiment is a sequence of $n$ items, where the size and duration of each
item is selected randomly from their ranges, assuming a uniform distribution.
For different settings of the parameters as described in Table 2, we generate
$m=1000$ input instances. Since the computation of the optimal packing is NP-
hard, we evaluate the performance of an algorithm by comparing its packing
cost to the lower bound on OPT from Lemma 1 (i).

Parameter | Description | Value
---|---|---
$d$ | Num. dimensions | $\\{1,2,5\\}$
$n$ | Sequence length | $n=1000$
$\mu$ | Max. item length | $\\{1,2,5,10,100,200\\}$
$T$ | Sequence span | $T=1000$
$B$ | Bin size | $B=100$
Table 2: Summary of experimental parameters

Our experimental results are shown in Figure 4. For each combination of
parameters $d\in\\{1,2,5\\}$ and $\mu\in\\{1,2,5,10,100,200\\}$, we plot the
average performance of our algorithms in consideration, with error bars
measuring the standard deviation.

(a) $d=1$

(b) $d=2$

(c) $d=5$

Figure 4: Average-case performance of Any Fit packing algorithms for different
values of $\mu$ and $d$. Error bars measure std. deviation.

#### General Observations.

We observe that Move To Front has the best average-case performance among all
algorithms, even in multiple dimensions. Close in performance are First Fit
and Best Fit, which have nearly identical performance (the blue and brown
curves are nearly superimposed), with First Fit having generally lower
variance. Following these are Next Fit, Last Fit and Random Fit with the
performance of Next Fit degrading with higher values of $\mu$, i.e., longer
jobs on average. As expected, Worst Fit has the worst performance since it
packs items inefficiently. Random Fit and Worst Fit are also seen to have a
higher variance indicating a high variability in performance. In contrast,
Move To Front, First Fit and Best Fit have low variance in performance.

#### Packing and Alignment.

We attempt to intuitively explain our experimental results. As [18] discuss,
the quality of a solution is influenced by packing and alignment. Packing
refers to how tightly items are packed together and how much space is wasted,
while alignment refers to how well-aligned items are in terms of their
durations. Better packing leads to improved performance since lower number of
bins need to be opened. Better alignment saves on cost because if items
arriving at almost the same time are packed together then in expectation they
all depart together, preventing solutions in which multiple bins are active,
each containing a small number of long-duration jobs.

The performance of Best Fit (resp. Worst Fit) can therefore be explained due
to its excellent (resp. poor) packing. Next Fit generally should lead to well-
aligned solutions since it tries to fit items into one bin, however does not
factor packing into consideration as it only maintains one open bin. On the
other hand, Move To Front does relatively well on both fronts: by using the
most recently-used bin it leads to well-aligned solutions, and since it keeps
all bins open it does not open many new bins like Next Fit. These intuitive
ideas can also be used to explain the observation that the performance of Next
Fit worsens with large $\mu$: for larger $\mu$, it is more likely that bins
remain open for a longer duration, hence it is better to avoid opening many
new bins (which is what Next Fit does) to save cost.

#### Theory vs Practice.

Our work invites an interesting discussion contrasting theory and practice.
While the competitive ratio (CR) of Best Fit is theoretically unbounded, it
has a good average-case performance in practice. In contrast, although the CR
of Next Fit is theoretically bounded, it does not do as well in practice.
Finally, although the bound on the CR of First Fit is lower than the proved
lower bound on the CR of Move To Front, on average Move To Front has better
performance than First Fit. These observations suggest theoretically studying
the average-case performance of these algorithms against input sequences
arising from specific distributions (such as the uniform distribution
considered in our experiments) as an interesting direction for future
research.

##  8 Concluding Remarks

In this paper, we studied the MinUsageTime Dynamic Vector Bin Packing problem,
where the size of an item is a $d$-dimensional vector, modelling multi-
dimensional resources like CPU/GPU, memory, bandwidth, etc. We proved almost-
tight lower and upper bounds on the competitive ratio (CR) of Any Fit packing
algorithms such as Move To Front, First Fit and Next Fit. Notably, we showed
that Move To Front has a CR of $(2\mu+1)d+1$, thus significantly improving the
previously known upper bound of $6\mu+7$ for the 1-D case. Our experiments
show that Move To Front has superior average-case performance than other Any
Fit packing algorithms.

We discuss some interesting directions for future work. The first is to close
the gap between the upper and lower bounds presented in this paper.
Concretely, investigating if the lower bound of $\max\\{2\mu,(\mu+1)d\\}$ on
the CR of Move To Front can be improved to $2\mu d$ is a natural first step.
Another direction is to design algorithms with improved CR for small number of
dimensions, such as $d=2$. Lastly, studying the problem when given additional
information about the input, perhaps obtained using machine learning
algorithms, is another direction for future work. For instance, studying the
clairvoyant DVBP problem, where the duration of an item is accurately known at
the time of its arrival, is an interesting question.

## References

  * [1] Yossi Azar, Ilan Reuven Cohen, Seny Kamara, and Bruce Shepherd.  Tight bounds for online vector bin packing.  In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’13, page 961–970, New York, NY, USA, 2013. Association for Computing Machinery.  doi:10.1145/2488608.2488730.
  * [2] Yossi Azar and Danny Vainstein.  Tight bounds for clairvoyant dynamic bin packing.  ACM Trans. Parallel Comput., 6(3), oct 2019.  doi:10.1145/3364214.
  * [3] János Balogh, József Békési, and Gábor Galambos.  New lower bounds for certain classes of bin packing algorithms.  In Klaus Jansen and Roberto Solis-Oba, editors, Approximation and Online Algorithms, pages 25–36, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [4] Allan Borodin and Ran El-Yaniv.  Online computation and competitive analysis.  1998\.
  * [5] Niv Buchbinder, Yaron Fairstein, Konstantina Mellou, Ishai Menache, and Joseph (Seffi) Naor.  Online virtual machine allocation with lifetime and load predictions.  In Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’21, page 9–10, New York, NY, USA, 2021. Association for Computing Machinery.  doi:10.1145/3410220.3456278.
  * [6] Joseph Chan, Prudence W. H. Wong, and Fencol C. C. Yung.  On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis, volume 4112 of Lecture Notes in Computer Science, pages 309–319.  Springer Finance, 2006.
  * [7] Wun-Tat Chan, Tak-Wah Lam, and Prudence W. H. Wong.  Dynamic bin packing of unit fractions items.  In Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, and Moti Yung, editors, Automata, Languages and Programming, pages 614–626, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
  * [8] Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali.  Approximation and online algorithms for multidimensional bin packing: A survey.  Computer Science Review, 24:63–79, 2017.  URL: https://www.sciencedirect.com/science/article/pii/S1574013716301356, doi:https://doi.org/10.1016/j.cosrev.2016.12.001.
  * [9] E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson.  Dynamic bin packing.  SIAM Journal on Computing, 12(2):227–258, 1983.  arXiv:https://doi.org/10.1137/0212014, doi:10.1137/0212014.
  * [10] Edward Coffman and Janos Csirik.  Performance Guarantees for One-Dimensional Bin Packing, pages 32–1.  05 2007.  doi:10.1201/9781420010749.pt4.
  * [11] Edward G. Coffman Jr., János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo.  Bin Packing Approximation Algorithms: Survey and Classification, pages 455–531.  Springer New York, New York, NY, 2013.  doi:10.1007/978-1-4419-7997-1_35.
  * [12] Gaikai, https://en.wikipedia.org/wiki/Gaikai.
  * [13] Michael R. Garey and David S. Johnson.  Computers and Intractability; A Guide to the Theory of NP-Completeness.  W. H. Freeman and Co., USA, 1990.
  * [14] M.R Garey, R.L Graham, D.S Johnson, and Andrew Chi-Chih Yao.  Resource constrained scheduling as generalized bin packing.  Journal of Combinatorial Theory, Series A, 21(3):257–298, 1976\.  URL: https://www.sciencedirect.com/science/article/pii/0097316576900017, doi:https://doi.org/10.1016/0097-3165(76)90001-7.
  * [15] Ori Hadary, Luke Marshall, Ishai Menache, Abhisek Pan, David Dion, Esaias E Greeff, Star Dorminey, Shailesh Joshi, Yang Chen, Mark Russinovich, and Thomas Moscibroda.  Protean: Vm allocation service at scale.  In OSDI. USENIX, October 2020.  URL: https://www.microsoft.com/en-us/research/publication/protean-vm-allocation-service-at-scale/.
  * [16] Zoran Ivković and Errol L. Lloyd.  Fully dynamic algorithms for bin packing: Being (mostly) myopic helps.  In Thomas Lengauer, editor, Algorithms—ESA ’93, pages 224–235, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg.
  * [17] David S. Johnson.  Near-optimal bin packing algorithms.  1973\.
  * [18] Shahin Kamali and Alejandro López-Ortiz.  Efficient online strategies for renting servers in the cloud.  In Giuseppe F. Italiano, Tiziana Margaria-Steffen, Jaroslav Pokorný, Jean-Jacques Quisquater, and Roger Wattenhofer, editors, SOFSEM 2015: Theory and Practice of Computer Science, pages 277–288, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.
  * [19] Ragini Karwayun.  A dynamic energy efficient resource allocation scheme for heterogeneous clouds using bin-packing heuristics.  Algorithms, 9:15–24, 2018.
  * [20] Eugene L. Lawler, Jan Karel Lenstra, Alexander H.G. Rinnooy Kan, and David B. Shmoys.  Chapter 9 sequencing and scheduling: Algorithms and complexity.  In Logistics of Production and Inventory, volume 4 of Handbooks in Operations Research and Management Science, pages 445–522. Elsevier, 1993.  URL: https://www.sciencedirect.com/science/article/pii/S0927050705801896, doi:https://doi.org/10.1016/S0927-0507(05)80189-6.
  * [21] Yusen Li, Xueyan Tang, and Wentong Cai.  On dynamic bin packing for resource allocation in the cloud.  In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’14, page 2–11, New York, NY, USA, 2014\. Association for Computing Machinery.  doi:10.1145/2612669.2612675.
  * [22] Yusen Li, Xueyan Tang, and Wentong Cai.  Dynamic bin packing for on-demand cloud resource allocation.  IEEE Transactions on Parallel and Distributed Systems, 27(1):157–170, 2016.  doi:10.1109/TPDS.2015.2393868.
  * [23] Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska.  Dynamic right-sizing for power-proportional data centers.  IEEE/ACM Transactions on Networking, 21(5):1378–1391, 2013.  doi:10.1109/TNET.2012.2226216.
  * [24] OnLive, https://en.wikipedia.org/wiki/OnLive.
  * [25] Rina Panigrahy, Kunal Talwar, Lincoln Uyeda, and Udi Wieder.  Heuristics for vector bin packing.  January 2011.  URL: https://www.microsoft.com/en-us/research/publication/heuristics-for-vector-bin-packing/.
  * [26] Amazon EC2 Pricing, Accessed 2022-01-08.  URL: https://aws.amazon.com/ec2/pricing/.
  * [27] Runtian Ren and Xueyan Tang.  Clairvoyant dynamic bin packing for job scheduling with minimum server usage time.  In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’16, page 227–237, New York, NY, USA, 2016\. Association for Computing Machinery.  doi:10.1145/2935764.2935775.
  * [28] Runtian Ren, Xueyan Tang, Yusen Li, and Wentong Cai.  Competitiveness of dynamic bin packing for online cloud server allocation.  IEEE/ACM Transactions on Networking, 25(3):1324–1331, 2017.  doi:10.1109/TNET.2016.2630052.
  * [29] Steven S. Seiden.  On the online bin packing problem.  J. ACM, 49(5):640–671, sep 2002.  doi:10.1145/585265.585269.
  * [30] Alexander L. Stolyar and Yuan Zhong.  A large-scale service system with packing constraints: Minimizing the number of occupied servers.  SIGMETRICS Perform. Eval. Rev., 41(1):41–52, jun 2013.  doi:10.1145/2494232.2465547.
  * [31] StreamMyGame, https://en.wikipedia.org/wiki/StreamMyGame.
  * [32] Xueyan Tang, Yusen Li, Runtian Ren, and Wentong Cai.  On first fit bin packing for online cloud server allocation.  In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 323–332, 2016.  doi:10.1109/IPDPS.2016.42.
  * [33] Gerhard J Woeginger.  There is no asymptotic ptas for two-dimensional vector packing.  Information Processing Letters, 64(6):293–297, 1997.
  * [34] Prudence W. H. Wong, Fencol C. C. Yung, and Mihai Burcea.  An 8/3 lower bound for online dynamic bin packing.  In Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee, editors, Algorithms and Computation, pages 44–53, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.

##  Appendix A Missing Proofs

###  A.1 Proof of Proposition 1

See 1

###### Proof.

Part (i) and the first inequality of part (ii) are immediate from the
definition of $L_{\infty}$ norm. The second inequality of part (ii) follows
form the following series of inequalities.

$\displaystyle\sum_{i=1}^{n}\lVert\mathbf{v}_{i}\rVert_{\infty}$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{j=1}^{d}(\mathbf{v}_{i})_{j}$ (since
$\lVert\mathbf{v}_{i}\rVert_{\infty}=\max_{j\in[d]}(\mathbf{v}_{i})_{j}$)
$\displaystyle=\sum_{j=1}^{d}\sum_{i=1}^{n}(\mathbf{v}_{i})_{j}$ (changing the
order of sum) $\displaystyle\leq
d\cdot\max_{j\in[d]}\sum_{i=1}^{n}(\mathbf{v}_{i})_{j}$
$\displaystyle=d\cdot\bigg{\lVert}{\sum_{i=1}^{n}\mathbf{v}_{i}}\bigg{\rVert}_{\infty}.$
(by definition of norm)

∎