Renting Servers for Multi-Parameter Jobs in the Cloud
Yaqiao Li Mahtab Masoori Lata Narayanan Denis Pankratov


Deep multi-prototype capsule networks
    [
    Received September 15, 1996; accepted March 16, 1997
========================================================

plain


§ INTRODUCTION


One of the most famous problems in online computation is the bin packing problem which has received a lot of attention among researchers <cit.>. Given a set of items with a positive size, and a bin capacity, the objective is to pack all the items in the minimum possible number of bins such that the total size of items assigned to a bin does not exceed the bin capacity. For simplicity, it is generally assumed that the item sizes lie between 0 and 1 and the bins all have unit capacity. This problem is online in the sense that the items come in a sequential manner and the algorithm has to place a new item in a bin without having any knowledge about the upcoming items. 
Dynamic bin packing  is a generalization of the bin packing problem <cit.>, in which items not only have an arrival time and a size, but also a duration. 
The objective function is the same as the classic bin packing problem; minimizing the total number of bins that is used to pack all the items. Dynamic bin packing has been extensively used to model various resource allocation problems, highlighting its adaptability in optimizing packing scenarios for dynamic settings <cit.>.

Li et al. <cit.> introduced MinUsageTime Dynamic Bin Packing, a new variant of Dynamic Bin Packing. The problem is also known as Renting Servers in the Cloud (), and 
is primarily motivated by job allocation to servers in the cloud.  For example, users make requests for virtual machines (VMs) with specific requirements to a cloud service provider such as Microsoft Azure, which then has to assign VMs to physical servers with sufficient capacity. The power and other costs incurred by the service provider are directly proportional to the total duration that servers are kept active. Optimal assignment decisions can reduce fragmentation which can result in dramatic cost savings <cit.>. 
As another application, cloud gaming companies such as GaiKai, OnLive, and StreamMyGame rent servers from public cloud companies and are charged using a pay-as-you-go model. A customer's request to play a game is assigned to one of the rented servers that has enough capacity to serve the request. The rental cost paid by the gaming company is directly proportional to the duration of time that the servers are rented. 

These situations are modeled by the problem, which has been studied in both non-clairvoyant  and clairvoyant settings, see, e.g.  <cit.>. Recently, Murhekar et al.  <cit.> initiated the study of for multi-parameter jobs. 
In this setting, jobs with resource requirements for multiple parameters (e.g. number of GPUs, memory, network bandwidth etc.) arrive to the system in an online manner and must be assigned by the algorithm to servers with fixed capacity along each of these dimensions.   In the non-clairvoyant setting, the arrival time of a job and its resource requirements, given as a size vector, are revealed to the algorithm when the job arrives, but its duration is only known when it departs. In the clairvoyant setting, the finishing time of a job is also known to the algorithm when it arrives. Jobs  must be assigned to servers immediately after arriving, and the algorithm's decisions are irrevocable, as the cost of moving a job mid-execution to another server is assumed to be prohibitive.  The objective of the problem is to minimize the total cost of all rented servers, where  the cost of a server is proportional to the duration for which it is rented/utilized.







The performance of online algorithms is measured by the notion of competitive ratio. This ratio represents the worst-case comparison, considering all inputs, between the cost achieved by the online algorithm and the cost achieved by an optimal offline solution that has complete knowledge of the entire input instance in advance.



 §.§ Our contributions

In this paper, we study the d-dimensional problem, when job sizes are d-dimensional vectors and the size of a job in any dimension is normalized to lie between 0 and 1, and the server capacity in each dimension is 1. We consider both the clairvoyant and non-clairvoyant versions of the problem. Our main results in this paper are summarized below:


    

    
  * We introduce a subset of algorithms called monotone algorithms and propose a new clairvoyant algorithm within this category called , which assigns a new job to the server with enough remaining capacity that would incur the least additional cost. We prove that all monotone algorithms including have a competitive ratio of 3d μ+1, where μ is the ratio between the maximum and minimum duration of jobs in the input sequence. The proof uses a new technique compared to those used in <cit.> and <cit.>. 

We remark here that the proof of a 6μ+8 upper bound on the competitive ratio of given in <cit.> also works for for 1-dimensional .  However, we are able to derive a better upper bound with our technique, which moreover generalizes to any monotone algorithm and d-dimensional . 
    The upper bound is  tight as a lower bound of Ω(d μ) was shown on the competitive ratio of algorithms in <cit.>. 

    


    
  * 
 
    We demonstrate a very general direct sum property of the problem by showing how to transform any algorithm  for dimension 1 to a corresponding algorithm ^⊕ d for dimension d, with competitive ratio scaling exactly by a factor of d. As a corollary, we obtain the first clairvoyant algorithm for d-dimensional , with competitive ratio Θ(d√(logμ)).


    
  * We adapt, for the first time, an online graph coloring lower bound construction in <cit.> to prove lower bounds for d-dimensional . Specifically, we prove a lower bound of Ω(d μ) for both deterministic and randomized algorithms for  d-dimensional non-clairvoyant when μ≤log d - 2, and a lower bound of  Ω(d) for the clairvoyant case. Connections between online vector bin packing and online graph coloring have been explored in  <cit.>. 
 

      
    
     
  * We conduct experiments in the average-case scenario, evaluating nearly all existing algorithms for  using randomly generated synthetic data. Our findings show that the algorithm  outperforms other algorithms, whether clairvoyant or non-clairvoyant, in the vast majority of cases. 







 §.§ Organization
 
 The related work is summarized in Section <ref>. Formal definitions and notation are introduced in Section <ref>. In Section <ref>, we define a new subclass of the algorithms for which we call  the monotone algorithms, and prove an upper bound of the competitive ratio using a new proof technique. In Section  <ref>, we describe a direct sum property of algorithms for and obtain as a corollary an upper bound for d-dimensional clairvoyant . In Section <ref>,  we prove lower bounds for deterministic and randomized algorithms for in both clairvoyant and non-clairvoyant settings by adapting techniques in online graph coloring.  The experimental results are presented in Section <ref>. Finally, we draw the conclusion and list some open problems in Section <ref>.




§ PREVIOUS WORK




Bin packing is one of the best-studied problems in combinatorial optimization, and extensive research has been done on proving tight bounds on the competitive ratio of online algorithms for the problem <cit.>. 
A well-studied class of algorithms is , in which the guiding principle is to always use existing bins when possible. Well-known algorithms such as , , and fall into this class. A rather large class of algorithms has been shown to have a tight competitive ratio of 1.7 for the bin packing problem <cit.>. The best known upper bound for bin packing is achieved by Advanced Harmonic   <cit.> and has a competitive ratio of 1.57829. The current best lower bound is 1.54278, as shown in <cit.>.

In the online vector bin packing problem, item sizes are given as d-dimensional vectors and bins have capacity 1 in each dimension. The online algorithm assigns items to bins such that the capacity constraints are respected in every dimension. 
Garey et al. <cit.> showed that  Generalized  has a competitive ratio at most d+0.7. Azar et al. <cit.>, using connections to online graph coloring, proved a lower bound Ω(d^1-ϵ) for any algorithm. 












Coffman et al. <cit.> introduced dynamic bin packing: items have size as well as duration, and the objective function is still to minimize the number of bins. 
Wong et al.  <cit.> established the current best lower bound 2.66 of the competitive ratio for any algorithm, they also showed that has an upper bound 2.897. The performance of various algorithms such as , modified , and have been studied in  <cit.> etc.





The 1-dimensional and d-dimensional problems were introduced in  Li et al. <cit.> and Murhekar et al. <cit.>, respectively. Except  <cit.>, all existing literature on studies only dimension 1. 
For  non-clairvoyant 1-dimensional ,
Li et al. <cit.> proved a lower bound of μ+1 for algorithms.
Later, Kamali and Lopez-Ortiz <cit.> showed that μ is in fact a lower bound for any deterministic algorithm. The current best upper bound for is μ+3, which was proved in the PhD thesis of Ren  <cit.>.
Masoori et al. <cit.> studied the performance ratio of for uniform-duration jobs and for restricted servers and showed better bounds on the competitive ratio of in these settings. 
Kamali and Lopez-Ortiz <cit.> considered the algorithm and proved that it has competitive ratio of 2μ + 1. They also introduced a new algorithm called the Move-to-Front (), which places the next job in the most recently used bin. They proved that the competitive ratio of is at most 6μ +7.
The clairvoyant setting has been studied in <cit.>. In particular, Azar et al. <cit.> proposed the hybrid algorithm () , and proved a tight bound of  Θ(√(logμ)) on its competitive ratio. 

Murhekar et al. <cit.> initiated the study of  non-clairvoyant d-dimensional . They proved that has an upper bound (2μ +1)d +1, which in particular improves the previous upper bound of in <cit.> for d=1 to 2 μ + 2.
They also generalized various upper and lower bounds of algorithms such as and from dimension 1 to dimension d. In particular, they showed a  lower bound of d(μ +1) for algorithms. 

 







 


Finally,  <cit.> also presented experiments on random inputs to compare different algorithms and show various non-trivial phenomena. In particular, Kamali and Lopez-Ortiz <cit.> demonstrated that in general performs the best among all known non-clairvoyant algorithms at dimension 1, which was recently further confirmed by experiments for dimension d in Murhekar et al. <cit.>.  





To the best of our knowledge, the study of clairvoyant d-dimensional and randomized algorithms for is missing in the literature. This work partially fills this gap.




§ NOTATION AND PRELIMINARIES



For n ∈ℕ, let [n] denote the set {1,2,⋯, n}. The L_∞ norm of a vector v ∈ℝ_≥ 0 ^d is denoted by v_∞ and equals max_j ∈ [d] v_j. We shall make frequent use of the following classical inequalities:

     
For any set of vectors v_1, v_2, ⋯, v_n ∈ℝ_≥ 0 ^d, we have the following: 

    ∑_i=1 ^n v_i_∞≤∑_i=1 ^n v_i_∞≤  d ·∑_i=1 ^n v_i_∞





The input to a d-dimensional problem is = {σ_1, σ_2, …, σ_n } – a list of jobs  where each job σ_i ∈ is a triple  (a_i, f_i, _i), denoting the arrival time, finishing time, and size/resource demand of σ_i. 
We assume that the jobs are presented to the algorithm in the order of arrival, that is, a_1 ≤ a_2 ≤⋯≤ a_n.  We refer to f_i-a_i as the duration of the job σ_i. The duration of every job lies between 1 and μ, that is, 
1 ≤ f_i - a_i ≤μ for every job σ_i. The utilization of the job σ_i, denoted by (σ_i), is defined as (σ_i) = (f_i - a_i) ·_i_∞.


Each job has multi-dimensional resource demands, i.e., _i ∈ (0,1)^d 
where _i^j denotes the size of the job σ_i in the j^th dimension for j∈ [d]. We assume that an algorithm for has access to a supply of identical servers of capacity 1 in each dimension, i.e, the size of each server is 1^d. Thus, for every time t the combined size of jobs in a particular dimension assigned to a particular server and active at time t must not exceed 1. We denote the sum of sizes of jobs active at time t by s(, t), i.e., s(, t) = ∑_i : a_i ≤ t < f_i s_i. 
For a server S alive at time t, we use S(t) to denote the sum of sizes of all jobs that have been scheduled on S and are alive at time t. 
As previously mentioned, the cost associated with each server corresponds to the total duration it remains open, and the overall cost of the algorithm is the sum of the costs of all servers. The following example gives a sample input and solution.

  



In this example we have d = 2. The input sequence σ consists of four jobs, σ_1 = (0, 6, s_1 = [0.5,0.2]),
σ_2 = (1, 4, s_2 = [0.2, 0.9] ),σ_3 = (3, 9, s_3 = [0.2, 0.3] ),   σ_4 = (5, 8, s_4 = [0.6, 0.1]) . Figure <ref> shows a possible assignment of these jobs to servers. The algorithm opens the first server for σ_1. However, upon the arrival of σ_2, a new server is opened since the first server lacks the capacity in the second dimension to accommodate it. When the third job σ_3 arrives, it is assigned to the first server. However, for σ_4, a new server must be opened as the first server does not have enough capacity in the first dimension, and the second server is already closed.

The cost of each server is determined by its opening and closing times. The first server's cost is 9 (opening at 0 and finishing at 9), while the second and third servers both have a cost of 3. The total cost of the algorithm is the sum of the costs of all servers, resulting in a total cost of 15.
























We shall sometimes also use r to denote an arbitrary job in σ. In this case, we use the notation
    r = (a(r),f(r), (r))


and we use
    (r)_j
to denote the j^th coordinate of the size vector (r).
The two key parameters of an instance , usually called the span and the utilization <cit.>, are defined respectively below,

    () = | ∪_i ∈ [n] [a_i, f_i) |,   () = ∑_i =1 ^ n(σ_i).

Without loss of generality, we assume that ∪_i ∈ [n] [a_i, f_i) = [0, T), that is,  arises from a single uninterrupted interval, and the first job arrives at time 0.



For an algorithm  and t ∈ [0,T) we use (, t) to denote the number of servers opened by  that are active at time t. We use () to denote the total cost of  on input , i.e., the sum of durations of servers opened by . Similar notation is used for . Observe that




    () = ∫_0 ^ T(, t) dt,  and


    () = ∫_0 ^ T(, t) dt.





We note the following general lower bound on ().


 
  ∫_0^T ⌈s(, t)_∞⌉ dt ≤() 



    As the capacity of each server is 1 for every dimension j ∈ [d]; any algorithm needs at least ⌈s(, t)_∞⌉ servers to pack the total load at any time t.
    
    Therefore, (,t) ≥
    ⌈s(, t)_∞⌉. Using Proposition <ref>, we can conclude: 
       
    ∫_0^T ⌈s(, t)_∞⌉ dt ≤∫_0 ^ T(, t) dt = ().





 
      () ≥max{(), ()/d}.



An online algorithm  is said to be asymptotically ρ-competitive if there exists a constant c>0 such that for all input sequences σ:

    (σ) ≤ρ·(σ) + c.
 
The infimum over all such ρ is denoted by ρ() and is called the competitive ratio of . If c = 0 then the algorithm is called strictly ρ-competitive.  



Lastly, we use  notation 1(C) for the indicator function that evaluates to 1 if the condition C is satisfied, and it evaluates to 0 otherwise.











































§ MONOTONE ALGORITHMS
  

An algorithm for is said to be an algorithm if it opens a new server only in case that a new incoming job cannot be accommodated on any of the currently active servers. Most algorithms use an ordering of active servers, and assign the next job to the first server in the ordering with enough available space to accommodate the job. In this case, we say that the algorithm employs an ordering. For example, orders servers based on their opening times, orders servers based on their remaining capacity, and moves the server to which a job is assigned to the first position in the ordering. Observe that the ordering of servers could be fixed as in and , or it could change when a job arrives, as in , , and , as well as when a job leaves, as in and . 

Consider an algorithm  that employs an ordering. We say that a server S is higher in the ordering than S' at time t if S appears closer to the beginning of the ordering than S'. Consider t < t' and define A(t, t') to be the set of servers that are alive at t and t'.
 
    An algorithm  is called monotone if 
    
        
  * it employs an ordering, and
        
  * for every t < t' and every server S ∈ A(t, t'): if S did not receive any new jobs during the interval (t, t') then every server in A(t, t') that is higher than S in the ordering at time t is still higher than S in the ordering at time t'.
    

Note that for a monotone algorithm a server S can move up in the ordering between t and t' only if either some server that was higher than S at time t was released before t', or S received a job during the interval (t, t').  

It is clear that algorithms employing a static ordering such as and have the monotone property. Observe that in , a server that receives a job moves to the first position in the ordering, and the relative position of other servers stays the same. Since the only way for a server to move ahead of other servers in the ordering is for it to receive a job, obeys the monotone property. However, in , a server may move down in the ordering when a job departs, causing the server to have more available space. Thus does not obey the monotone property.

We propose a new monotone algorithm, that surprisingly has not been studied earlier: 






: Order servers in decreasing order of their finishing times, that is, the maximum of the finishing times of jobs currently in the server. Assign the newly arrived job to the first server in the order that has sufficient capacity. If no such server exists, open a new server and assign the job to it.



is a natural and easy-to-implement algorithm that uses the greedy heuristic of assigning the incoming job to the server that will incur the least additional cost to the algorithm. Observe that a server S moves ahead of another server S' in the ordering if and only if S receives a job that causes its finishing time to be higher than that of S'.
Therefore obeys the monotone property specified in Definition <ref>. We note that it is a clairvoyant algorithm.


We need the following lemma before we prove the main result of this section. We denote the sum of L_∞ norms of sizes of jobs with arrival time in the interval (t, t') for t < t' by s_∞(, t, t'), i.e., s_∞(, t, t') = ∑_i : t < a_i < t's_i_∞. 


    ∫_0^T s_∞(, t-α, t) dt = α∑_i = 1^n s_i_∞.  






    ∫_0^T s_∞(, t-α, t) dt    = ∫_0^T ∑_i = 1^n 1(t-α < a_i < t) s_i_∞ dt
       = ∑_i = 1^n  ∫_0^T 1(t-α < a_i < t) s_i_∞ dt
       = ∑_i = 1^n s_i_∞∫_0^T 1(t-α < a_i < t)  dt
       = ∑_i = 1^n αs_i_∞.


















Now, we are ready to prove the main result of this section.


    Let  be a monotone algorithm. Then we have ρ() ≤ 3μ d +1.



We claim that for an arbitrary t it holds that

    (, t) ≤ s_∞(, t-2μ, t) + s_∞(, t-μ, t) + 1.

Observe that each server in A(t-μ, t) must have received a job during the time interval (t-μ, t), otherwise a server alive at time t-μ would have been released by time t, since the duration of each job is at most μ. Suppose there are q servers in A(t-μ,t) named A_1, A_2, …, A_q, ordered according to the ordering of  at time t-μ. Let t_i be the earliest time in (t-μ, t) when a job with the size vector s_i arrived in server A_i. Let B(t-μ, t) denote the set of new servers that were opened during time (t-μ, t) that are still alive at time t. Suppose there are p such servers called B_1, B_2,…, B_p ordered by their opening times t'_1, t'_2, …, t'_p.  Let s'_i be the size vector of the first job placed into B_i. See Figure <ref> for an illustration.
Note that we have (, t) = p + q.



Consider some i ∈{2, …, q}. Observe that A_i-1 preceded A_i in the ordering of  at time t-μ, no job arrived in A_i during time interval (t-μ, t_i), and  is monotone. Thus, A_i-1 precedes A_i in the ordering of  immediately prior to arrival of job s_i. Thus,  must have tried placing s_i into server A_i-1 at time t_i, but could not fit it in (since s_i was ultimately placed into A_i). This happened because in some coordinate the total size of jobs in server A_i-1 plus the size of the job s_i in that coordinate exceeded the capacity. Thus, we can conclude that

    s_i + A_i-1(t_i)_∞ > 1.

For the B_i servers,  since  is an algorithm (it opens a new server only if it has to), we have:

    s'_1 + A_q(t'_1)_∞ > 1 s'_i + B_i-1(t'_i)_∞ > 1 2 ≤ i ≤ p


Also, note that 

    ∑_i = 2^q A_i-1(t_i)_∞+ A_q(t'_1)_∞ + ∑_i=2^pB_i-1(t'_i)_∞≤ s_∞(, t-2μ, t),

since all jobs that are alive in server A_i-1 at time t_i, as well as in A_q at time t'_1, must have arrived between t-2μ and t, and the A_i and the B_j servers partition the set of relevant jobs. In addition, we have 

    ∑_i = 2^q s_i_∞  + s'_1_∞ +∑_i=2^p s'_i _∞≤ s_∞(, t-μ, t),

since the s_i and the s'_i jobs have arrival times between t-μ and t, and the jobs are distinct.

Combining the observations in (<ref>) and (<ref>), we obtain 

    q+p-1    < ∑_i = 2^q s_i + A_i-1(t_i)_∞ + s'_1 + A_q(t'_1)_∞
       + ∑_i=2^p s'_i + B_i-1(t'_i)_∞
       ≤ s_∞(, t-2μ, t) + s_∞(, t-μ, t),

where the second inequality follows from Proposition <ref> and application of  (<ref>) and (<ref>). This establishes Inequality (<ref>).

To finish the proof of the theorem, we integrate this  inequality over possible values of t, i.e.:
 
    ()    = ∫_0^T (, t) dt 
       ≤∫_0^T ( s_∞(, t-2μ, t) + s_∞(, t-μ, t) + 1 )dt 
       = 2μ∑_i = 1^n s_i_∞ + μ∑_i = 1^n s_i_∞  + ()
       ≤ 3 μ() + ()
       ≤ 3μ d () + (),

 where the second equality follows from two applications of Lemma <ref>, and the last inequality is an application of Proposition <ref>.


We note that there is not much room for improvement of the bound in the above theorem, because Murhekar et al. <cit.> proved a lower bound of (μ +1)d for any algorithm.



    
    (μ+1)d ≤ρ(), ρ() ≤ 3dμ+1



As mentioned earlier,  the proof of a 6μ+8 upper bound on the competitive ratio of given in <cit.> also works for in the 1-dimensional case. However, Corollary <ref> improves this bound. We conjecture that the correct bound on the competitive ratio of is μ d + O(d).

































































    







































































§ A DIRECT-SUM PROPERTY OF 
 


















Given an arbitrary algorithm  for 1-dimensional  , we define an algorithm, call it ^⊕ d, that works for  d-dimensional , as follows. Let σ be an input instance for the d-dimensional problem. We partition σ as follows:

    σ = σ^(1)∪⋯∪σ^(d),

where
    σ^(j)
is the subset of jobs r for which 
    (r)_∞ 
is achieved at the j-th dimension. When (r)_∞ is achieved in more than one dimension, we break the tie arbitrarily. It is easy to see that this partitioning can be done online. Each σ^(j) will be assigned to a different set of servers. 



The algorithm ^⊕ d is defined as follows: on the arrival of a job r, decide online a unique dimension j in which its size is maximum, and assign r ∈σ^(j). Next apply the algorithm  (for 1-dimensional ) to process σ^(j), pretending that the instance is 1-dimensional by only looking at the size at the j-th coordinate, and ignoring the sizes of other dimensions, and assigning to servers that only contain jobs in σ^(j).


    









 
    Let  be an arbitrary deterministic  algorithm for 1-dimensional . Then, ^⊕ d  works correctly for any d-dimensional , and 
        ρ(^⊕ d) = d·ρ(). 
    Moreover, the guarantee on the competitive ratio holds for both strict and asymptotic competitive ratios.



    Firstly, we show that the algorithm ^⊕ d does not violate the size constraint, i.e., the total size of all jobs in every server does not exceed 1^d. 
    To see this, consider an arbitrary  job r ∈σ and suppose it is put into a bin B by ^⊕ d. By the definition of ^⊕ d, we know before r is put into B, either server  B is empty (i.e., has not been created yet) in which case after r is assigned to server B the size constraint is trivially respected, or server B is nonempty. In the latter case,  it only contains jobs in σ^(j). In this case, we have
    
    (r) + B(t)_∞ 
            = (r)_j + B(t)_j ≤ 1,

    where the equality follows from the fact that every job in server B
is in σ^(j)
    and also r ∈σ^(j). The inequality follows by the fact that we apply algorithm  on r ∈σ^(j).

    Next, we show 
        ρ(^⊕ d) ≤ d·ρ().
    By an abuse of notation, let (σ^(j)) denote the cost of ^⊕ d(σ) on the subset of inputs σ^(j). Since
        σ^(j)⊆σ,
    one has
        (σ^(j)) ≤(σ)
    for every j. 
    Let '(σ^(j)) denote the cost of the optimal solution that processes σ^(j) by only focusing on the size of the j-th dimension. Then, for every ρ > ρ() there exists a c > 0 such that
        (σ^(j)) ≤ρ·'(σ^(j)) + c
    for every j.
    Observe that we have
        '(σ^(j)) = (σ^(j)).
    This is because every job in σ^(j) satisfies that the size at the j-th dimension is the largest. With these, and by the definition of ^⊕ d, we have
    
    ^⊕ d(σ)
               = ∑_j ∈ [d](σ^(j)) 
       ≤∑_j ∈ [d]( ρ·'(σ^(j))  + c ) 
       = ∑_j ∈ [d](ρ·(σ^(j)) + c ) 
       ≤∑_j ∈ [d](ρ·(σ) + c )
            = d ·ρ·(σ) + cd.

    Since cd is a constant independent of input, and this inequality holds for all ρ > ρ(), it follows that ρ(^⊕ d) ≤ d ρ(). Moreover, if c = 0 then cd = 0, so the competitive ratio guarantee preserves strictness.

    Lastly, we show 
        ρ(^⊕ d) ≥ d·ρ().
    Let H be an arbitrary 1-dimensional instance, from which we construct a d-dimensional instance σ as follows. For every job 
        h=(a(h), f(h), s(h)) ∈ H,
    create d jobs in σ that have the same arrival and finishing time as h, and the size vectors are the d column vectors of the matrix
        s(h) · I_d
    where I_d is the d× d identity matrix. Clearly, every σ^(j) is simply a copy of H in dimension j, while having 0's in all other dimensions. Hence, 
        ^⊕ d(σ) = d ·(H).
    Furthermore, Observe that
        (H) = (σ),  
    where here by an abuse of notation we use (H) to denote the cost of the optimal algorithm for the 1-dimensional instance H, and (σ) to denote the cost of the optimal algorithm for the d-dimensional instance σ. Hence,
    
    ρ(^⊕ d) 
            ≥^⊕ d(σ)/(σ)  
            = d ·(H)/(σ)  
            = d ·(H)/(H).

    Because H is arbitrary, the desired lower bound follows.




In <cit.>, the Hybrid Algorithm  is defined for 1-dimensional clairvoyant , and is shown to have a competitive ratio Θ(√(logμ)). 

   
    The algorithm ^⊕ d for d-dimensional clairvoyant has a competitive ratio 
        Θ(d√(logμ)).





        




































§ LOWER BOUNDS VIA ONLINE GRAPH COLORING
    

 In this section, we show lower bounds on the competitive ratio of any algorithm for d-dimensional . We consider deterministic algorithms in Section <ref> for both the clairvoyant and non-clairvoyant versions of the problem. In Section <ref>,
 we give lower bounds for randomized algorithms for both versions of the problem.
 


 §.§ Deterministic algorithms
   

For 1-dimensional non-clairvoyant , it is shown <cit.>  that μ is a lower bound for any deterministic algorithm. By adapting the online graph coloring lower bound construction from Halldórsson-Szegedy <cit.>, we show a Ω(dμ)
lower bound for  d-dimensional non-clairvoyant . For readers familiar with the online graph construction in <cit.>, a size vector in the proof of Theorem <ref> below corresponds to a vertex in the online graph, and the size vectors of the jobs are chosen in the way such that jobs that fit into one server correspond to an independent set of vertices of the online graph. The idea of applying online graph coloring to online vector bin packing has been discussed in <cit.>.


 
    There exists a constant d_0 (which can take d_0=280) such that for every dimension
        d ≥ d_0 
    and 
        μ≤log d - 2,
    every deterministic algorithm for non-clairvoyant has a competitive ratio ≥d/log^3 d·μ.
    For clairvoyant , the lower bound 
        Ω( max{√(logμ), d/log^2 d})
    holds.







    Let  be an arbitrary deterministic algorithm for d-dimensional non-clairvoyant . 
Choose k to be the largest integer for which 
        d ≥ d' = 2k  k· k ≥ 2^2k.
     Let  denote the adversary, which will adaptively construct an instance 
        σ = (σ_1, …, σ_d')
    consisting of d' jobs, such that  uses at least
        d'/k
    servers on σ, while  uses at most 2k servers. In fact,  will construct a solution using no more than 2k servers.     Note that all jobs arrive at the same time 0. At the end of d' steps, once all jobs have been processed by , the adversary specifies the finish times of all jobs. 
    
    
    
    
    
    
    
    
    

    

    
    
    
    
    
    To avoid confusion, we call the servers used by  bins, while the servers used by  will be called servers. We name the 2k servers that will be used by  as 1,2,…,2k. For an arbitrary job r ∈σ, 
 
   let  (r) ∈ [2k] denote the server to which  assigns r. 
    Let B be an arbitrary bin used by , and let B̂_≤ i denote the set of jobs in B after the first i jobs have been processed, and let B_≤ i denote the sum of the sizes of these jobs. 
    
     Define
    
    (B, i) := {(r): r ∈B̂_≤ i} ,

    i.e., it is the set of servers that the adversary used to assign jobs present in bin B after the first i jobs have been processed. 
    
   
 
    
      
   
    


    
    
    In step i, the adversary specifies the job σ_i, whose size is defined as follows. Let X denote the set of servers used by  that have exactly k jobs placed in them after the first i-1 jobs have been processed. We define 
    
    _i = {(B, i-1): B ∈ X }.

    Note that _i is a set of subsets of [2k]; each element of _i is the set of servers in which the adversary placed the jobs of k-sized bins of .  
    The adversary chooses an arbitrary subset A_i of size k
    
    A_i ∈[2k]  k - _i,

  


Since each distinct subset of [2k] in _i corresponds to k jobs in the input sequence σ, and recalling that the length of σ is d'=2k  kk, the set A_i always exists. 
  

The adversary now defines _i ∈ [0,1]^d' as follows: 
    
    _i^j =
            
                0,      if j<i and (σ_j) ∈ A_i, 
    
                1/d,      if j<i and (σ_j) ∉A_i, 
    
                1,      if j=i, 
    
                0,      if j>i.


The adversary assigns σ_i to an arbitrary server Q ∈ A_i. We show below that this is a valid assignment, that is, it does not violate capacity constraints.  

 

Let 
        Q ∈ A_i
    denote an arbitrary server in A_i. Then
    
    _i + Q(i-1)_∞≤ 1


    
  Indeed, by (<ref>),
         σ_j ∈Q̂(i-1)
     implies
         _i^j = 0.
     Also, because j<i, again by (<ref>) one has _j^i = 0.
 
 The claim follows.
    
  The adversary now presents job σ_i to  and suppose  assigns σ_i to bin B. Next, we show that after the assignment, bin B (and indeed any bin of ) contains at most k jobs.

 
 
  
  
    



 


























        
        
    
    
    
    
  








    
    
    
    
    




 
|Â(i)|≤ k for every bin A in use by  after i jobs have been processed. 


Assume this is true inductively after i-1 jobs have been processed. Since σ_i was added to bin B, we only need to argue that bin B had at most k-1 jobs after i-1 jobs were processed. Suppose instead that |B̂(i-1)| = k. Then (B, i-1) ∈_i, and so A_i ≠(B, i-1). 







    Since both A_i and (B, i-1) are of size k, there must exist at least one job
        σ_j ∈B̂(i-1)
    for which
        (σ_j) ∉A_i.
    This implies
        _i^j + _j^j = 1/d + 1 > 1.
    Hence,
        _i
    does not fit into bin B, which contradicts the choice of B by .
    

Claim <ref> shows that the optimal assignment uses at most 2k servers while Claim <ref> shows that  needs at least d'/k bins to assign the jobs in σ.  


    
   
    





    












































































    
    































    

    
    
    We are now ready to determine the choice of f_i, the finishing time of job σ_i. Observe that there exists at least one server of the adversary,  call it Q, such that jobs in Q̂_≤ d' appear in at least
        (d'/k)/(2k) = d'/2k^2
    distinct bins of . 
    The adversary sets the duration of jobs Q̂_≤ d' to be μ, and the duration of all other jobs to be 1.  
    
    Hence, the cost of  is at most
        2k-1 + μ,
    while the cost of  is at least
        d'μ /2k^2. Using the fact that for k ≥ 4, we have 
        d' = 2k  k· k ≥ 2^2k,  the competitive ratio of   is at least    






    
    
    
    
    
    
    


    
    d'μ /2k^2/2k-1 + μ≥d'/8k^3·μ≥d'/log^3 d'·μ,

    provided
        μ≤ 2k,
    and k ≥ 4. Next, observe that 
    
    
    
    

    
    
    
    
    
    
    d    < 2k+1  k+1· (k+1)
                ≤2k+1  k+1· k+ 2^2k+1≤ 2 2k  k· k+ 2^2k+1
       ≤ 2d' + 2d'  = 4d'

    Hence,
        d'/log^3 d'·μ≥d/4 log^3 d·μ
    which gives the desired bound on the competitive ratio for dimension d>280 (which ensures that k ≥ 4), and 
        μ≤log (d/4) = log d - 2.

    Finally, if the model is clairvoyant, the adversary sets all jobs to be of duration 1, and obtains a lower bound of competitive ratio 
        (d/k)/(2k) = d/2k^2 = Ω(d/log^2 d)
    that is independent of μ. The other lower bound 
        Ω(√(logμ))
    comes from the lower bound for 1-dimensional clairvoyant established in <cit.>.






 §.§ Randomized algorithms
  

 
    In 1-dimensional non-clairvoyant ,
    any randomized algorithm has a competitive ratio at least
        1-e^-1/2·μ.



    We use Yao's principle.  Consider the following distributional input: k^2 jobs each of size 1/k, uniformly at random pick k among k^2 jobs to be of duration μ, and let the rest k^2-k jobs to be of duration 1. 
    Let  be an arbitrary deterministic algorithm. We show that in expectation  has cost Ω(kμ). Since  has cost 
        ≤ k-1  + μ,
    this gives the competitive ratio Ω(μ) as desired. 
    
    Let
        A_1, …, A_m
    be the m servers that  uses for the above instance. Let
        |A_i|
    denote the number of jobs in A_i, then
        1≤ |A_i| ≤ k.
    We partition  these m servers into p groups 
        B_1, …, B_p-1, B_p
    such that the number of jobs in each group B_i contains ≥ k jobs and < 2k jobs, except perhaps the last group B_p which may contain less than k jobs. Note that such a partition exists by simply partitioning greedily. Hence,
        p ≥ k^2 / 2k = k/2.
    Let |B_i| denote the number of jobs in group B_i.
    Then, for  every 
        1 ≤ i ≤ p-1, 
    
    [B_i  contains at least one job of duration μ]
            = 1 -    k^2 -|B_i|  k/k^2  k
       ≥ 1 - k^2 -k  k/k^2  k≥ 1 - (1-1/k)^k
            ≥ 1 - e^-1.

    Let 
        X_i ∈{0,1} 
    be a random variable denoting whether group B_i contains some job of duration μ or not. Then, by the linearity of expectation, the expected cost of  is at least
    
    μ·[∑_i=1^p-1 X_i ]
               = μ·∑_i=1^p-1[X_i] 
            ≥μ· (p-1) (1-e^-1)  
       ≥μ· (k/2 - 1) (1-e^-1).

    Hence, the competitive ratio is at least
        1-e^-1/2·k-2/k-1+μ·μ.
    For every μ, since we can pick k to be arbitrarily large, we get the ratio is at least 
        1-e^-1/2·μ 
    as claimed.





 
    There exists a constant d_0 (can take d_0=280) such that for every dimension
        d ≥ d_0 
    and 
        μ≤log d - 2,
    every randomized algorithm for d-dimensional non-clairvoyant has a competitive ratio 
        ≥Ω(d/log^4 d·μ).
    For d-dimensional clairvoyant , the lower bound 
        Ω(d/log^2 d)
    holds.



    We apply Yao's principle. 
    In <cit.>, it is shown that the online graph lower bound construction can be modified to work against randomized algorithms, with only a loss of a constant. We refer the interested reader to the original paper <cit.> for  details. Here we only give the necessary modifications, based on the proof given in Theorem <ref>. The oblivious adversary constructs a distributional input, as follows. 
    
        
  * The adversary uniformly at random picks a server Q ∈ [2k]; 
        
        
  * In step (<ref>), the adversary instead chooses a random subset A_i ⊆ [2k] of size k;

        
  * the vector _i is defined in the same way;

        
  * the adversary assigns _i to a random server X ∈ A_i;

        
  * if X=Q, the adversary sets the duration of _i to be μ, otherwise to be 1.
    
     This finishes the construction of the distributional input. Note that the adversary is oblivious. 
     
    By the same argument in <cit.>, under this distributional input, one can show that any deterministic algorithm uses in expectation
        Ω(d/k)
    bins. Note that adversary still uses at most 2k servers, with cost at most
        2k-1 + μ. 
    Hence, as in the deterministic proof, there exists at least one adversary's server Q^*, such that jobs in this server appear in at least
        Ω(d/k) / 2k = Ω(d/k^2)
    algorithm's bins. Since the adversary randomly picks a server Q and sets jobs in it to be of duration μ, we conclude that in expectation the algorithm has cost at least
        ≥1/2k·Ω(d/k^2) ·μ
        = Ω(dμ /k^3).
    Hence, the expected competitive ratio is at least
        Ω(dμ /k^3)/2k-1 + μ≥Ω(d μ/k^4),
    where
        k = Θ(log d),
    as claimed.
    For the clairvoyant case, the lower bound follows by setting all jobs to be of duration 1.










§ EXPERIMENTS
   




 In this section, we provide a thorough evaluation of the average-case performance of almost all existing non-clairvoyant as well as clairvoyant algorithms for the problem. 
 
 

 §.§ Experimental setup
 

 We evaluate the performance of different algorithms using randomly generated input sequences for d-dimensional , for d ∈{1, 2, 5}, closely adhering to the experimental setup detailed in <cit.> for the 1-dimensional case. In the experiments, we assume that each server has size E^d where E = 1000, and each job is assumed to have a size in {1,2, ⋯, E}^d.
 For a given integral span value T; for T ∈{1000, 5000 ,10000}, we assume that each job arrives at an integral time step within the interval [0, T-μ] and has an integral duration in [1, μ], for μ∈{1,2,5,10,100}. Each experimental instance comprises a sequence of n = 10000 jobs, with the size and duration of each job selected randomly from their respective ranges, assuming a uniform distribution. The reported upper bound on competitve ratio of each studied algorithm is computed as the ratio of the average cost of the algorithm over 100 input sequences, and the average of the lower bound on  given by Lemma <ref> for these instances. 


All our experiments were executed on a personal laptop with a Dual-core 2.3 GHz Intel Core i5 CPU. The laptop had 8 GB of RAM. The laptop was running Mac OS version 12.6.4. The code was written in C++ using VS code version 1.38.1. 



 §.§ Implemented algorithms

We  implemented both clairvoyant and non-clairvoyant algorithms. The non-clairvoyant algorithms  we implemented are:


    
  * :  which keeps only one open server at each time.

    
  * Modified: which  assigns jobs with sizes greater than a specific threshold separately from the other jobs using the algorithm.

    
  * : monotone that orders servers in increasing order of opening time. 
 
  * : monotone that orders servers in decreasing order of opening time. 

    
  * Modified: which assigns jobs with sizes greater than a specific threshold separately from the other jobs using the algorithm.

    
  * : that orders servers in increasing order of 
remaining capacity.

    
  * : that orders servers in decreasing order of 
remaining capacity.   


  * : algorithm that orders servers randomly. 

    
  * : monotone that orders servers in decreasing order of the last time a job was assigned to it. 
 



In our experiments, similar to <cit.>, we adopt the parameters for Modifiedand Modifiedas E^d/(μ +1) and E^d/(μ +7), respectively. This choice of values is designed to optimize the competitive ratio of these algorithms, as indicated in <cit.>.



The clairvoyant algorithms we implemented are:


    
  * Departure Strategy <cit.>: the span is split into intervals of length τ each, where τ >0 is a constant. Classifies jobs into categories according to their departure times. Each category contains all  jobs that depart in a time interval of length τ.

    
  * Duration Strategy <cit.>: classifies the jobs into categories such that the max/min job duration ratio for each category is a given constant α. Given a base job duration b, each category includes all the jobs with durations between b α ^i-1 and b α ^i for an integer i.

    
  * Hybrid Algorithm () <cit.>:  classifies jobs according to their length and their arrivals. Suppose the maximum duration of jobs in the input sequence is μ. Then all the jobs whose lengths are in range [2^i-1, 2^i] for integer 1≤ i ≤⌈logμ⌉ +1 and whose arrival times are in time interval [(c-1) 2^i, c2^i) for an integer c are put into the same category. 
  
    
  * : monotone as defined in Section <ref>.

    
  * New Hybrid: ^⊕ d as defined in Section <ref>.


















 §.§ Experimental results

Our experimental results for d ∈{1,2,5} are shown in Tables <ref>, <ref> and  <ref>, respectively. We validated our results against those in <cit.> for d=1 and for the algorithms implemented there. Our results are slightly different as we use a better lower bound to compute the competitive ratio; when using the same lower bound as <cit.>, our results match exactly.

First we note that for all algorithms, the experimentally derived competitive ratio on random inputs is much better than the worst-case bounds derived theoretically. This is not surprising as the worst-case inputs are carefully constructed to beat the given algorithm and are unlikely to occur in practice. Comparing the three tables, we see that the competitive ratio for every algorithm and every value of T and μ increases with increasing d. In general, the competitive ratio also increases with μ, keeping other parameters constant. 

We note that many algorithms have versions that separate servers into separate categories, and assign jobs to servers in a particular category based on their sizes. In general, such modifications of algorithms do not perform better than the original versions on random inputs, even though they have better worst-case competitive ratios. For example, performs worse than , performs worse than , and New Hybrid performs worse than in our experiments. We can also see that all clairvoyant algorithms except classify jobs and servers into different categories, and do not have good performance. 

An interesting finding is that has the best performance in almost all cases, among all clairvoyant and non-clairvoyant algorithms. Clearly, being a clairvoyant algorithm uses the information on finishing time of jobs to its advantage. However, the other clairvoyant algorithms generally do not exhibit good performance, with the exception of for the case μ=1. It is important to note that is the only monotone algorithm among the clairvoyant algorithms we have implemented. Note that, the other clairvoyant algorithms do not belong to the monotone algorithms category.

Among non-clairvoyant algorithms, the best algorithms are generally and , which are also both monotone algorithms. Surprisingly, 

as in <cit.>, in our experiments is one of the better algorithms, especially for higher values of μ, where its performance ratio equals or betters that of and [While also has excellent performance in the experiments of <cit.>, it does not beat for any value of d or μ. However, their experimental setup is somewhat different to ours and that in <cit.>.].  Recall that the worst-case competitive ratio of is unbounded as shown in <cit.>. 

  





 In <cit.> and <cit.>, two key factors, namely alignment and packing are identified as contributing to the performance of an algorithm for . The first factor is about how effectively jobs are aligned into servers in terms of their durations, while the second factor evaluates how tightly the jobs are packed together in servers. algorithms (except ) do well in terms of packing, but do not consider alignment. tries to align jobs but does not do as well with packing. The authors of <cit.> stipulate that by assigning the next job to the server that has the most recently arrived job, succeeds in terms of aligning jobs well in terms of time, while it also succeeds in packing since it is an algorithm.

is also an algorithm and therefore does well in terms of packing. By assigning to the server which contains the job that will finish the last, we may say that aligns even better than . 

A final interesting finding is that the difference in performance between the algorithms appears to narrow for d=5. Further research is needed to understand this phenomenon, but one reason could be that because the sizes of jobs in different dimensions are chosen independently, it is harder for any algorithm to achieve a good packing, which diminishes the difference between the algorithms.
 
 












§ CONCLUSION AND OPEN PROBLEMS


In this paper, we studied the d-dimensional problem. We introduced a sub-family of algorithms called monotone algorithms, and showed that monotone algorithms achieve competitive ratio Θ(d μ). We also introduced a natural clairvoyant algorithm that is a monotone algorithm. We showed how to lift 1-dimensional algorithms for to work in d dimensions via a general direct-sum theorem.  We also established a Ω̃(d μ) lower bound for the non-clairvoyant setting under the assumption that μ≤log d - 2. Finally, we conducted experiments that demonstrate that the newly introduced algorithm is among the best performing algorithms (both clairvoyant and non-clairvoyant) in the average-case scenario. 



The following is a list of open problems that are suggested by this work:


    
  * Close the gap between upper and lower bounds in Corollary <ref>. In particular, we conjecture that ρ(Greedy) ≤ d μ + O(d).

    
  * Does there exist a randomized algorithm for 1-dimensional clairvoyant with competitive ratio O(1)?

    
  * Can one remove the constraint μ≤log d - 2 in Theorems <ref> and <ref>?

    
  * For d-dimensional clairvoyant , is Ω(d√(logμ)) a lower bound for any algorithm?

    
  * Do the results from the experimental section carry over to real-life industrial instances?
   
    
   

   
   




 

abbrv


