On Approximating the Dynamic and Discrete Network Flow Problem
Bubai Manna Bodhayan Roy Vorapong Suppakitpaisarn

Identifying the ground state phases by spin-patterns in the Shastry-Sutherland model
    Hong-Gang Luo
    Received March XX, 2024; accepted XX XX, 2024
====================================================================================





We examine the dynamic network flow problem under the assumption that the flow consists of discrete units. The dynamic network flow problem is commonly addressed in the context of developing evacuation plans, where the flow is typically treated as a continuous quantity. However, real-world scenarios often involve moving groups, such as families, as single units. We demonstrate that solving the dynamic flow problem with this consideration is APX-hard. Conversely, we present a PTAS for instances where the base graph is a path with a constant number of nodes. We introduce a `ready time' constraint to the minsum bin packing problem, meaning certain items cannot be placed in specific bins, develop a PTAS for this modified problem, and apply our algorithms to the discrete and dynamic flow problem.











§ INTRODUCTION



Flow problems on dynamic graphs <cit.> are considered by many researchers (e.g. <cit.>) because of many reasons. One of the reasons is their relevance in finding evacuation routes during emergencies such as earthquakes or fires <cit.>. In those applications, we aim to move persons in the ways that they arrive at aiding facilities as soon as possible. 
The most common objective function for those problems is minmax, which aims to minimize the time until all persons arrive at facilities. In this work, however, we consider another common objective function called minsum, which aims to minimize the summation of time that each individual needs for their trips.

In 1958, the paper <cit.> solved the problem Maximum Flow Over Time, while their `minmax' variation requested for Quickest Transshipment, which was even studied lately in <cit.>. It has been shown that both objective functions of flow problems can be solved using time-expanded networks <cit.>. However, these temporal graphs can be exponentially large in relation to the input size, making the algorithm pseudo-polynomial. 
For minmax problems, polynomial-time algorithms have been developed for paths <cit.> and trees <cit.>. There are also FPTAS for general graphs when the number of facilities is constant <cit.>. In contrast, minsum problems have only been shown to have polynomial-time algorithms for path graphs <cit.>. 

All known algorithms assume that individuals are distinct and identical, meaning that we can move any number of people over a particular edge as long as the total number does not exceed the edge's capacity. However, this may not always be possible in practice. For example, some groups of people, such as families, must be moved together, and some groups may require emergency aid and should therefore be given higher priority. These considerations must be taken into account when determining how to move people from one location to another.



 §.§ Our Contributions


We define our problem called minsum problem for discrete and weighted set flow on a dynamic network (MS-DWSF) in subsection <ref>. It is clear that the discrete and weighted version is harder than the original problem. Indeed, it is easy to show that it is NP-hard by a reduction to the partition problem[The reduction has been given in our paper under submission.]. 

In Section <ref>, the APX-hardness of MS-DWSF is established. Furthermore, Section <ref> introduces a Polynomial Time Approximation Scheme (PTAS) specifically for instances where the underlying graph is a path graph featuring a single facility, a constant number of nodes, and uniform edge capacities. It's important to highlight that this assumption of uniformity and simplicity in graph structure is similarly adopted in several studies within the realm of dynamic network flows <cit.>. 




We find that in the scenario where the graph forms a path with a single facility, the edge nearest to the facility experiences the highest congestion. Consequently, the challenge of dynamic flow becomes a matter of strategizing the distribution of discrete flows across this edge. This scenario aligns with the principles of the minsum bin packing problem <cit.>, where the dispatch of items at a specific time t can be likened to packing these items into a bin labeled t. Nonetheless, a direct application of bin packing algorithms is not feasible. This is because items originating from nodes distant from the facility require time to approach the nearest node, implying that these items cannot be dispatched prior to a specific time τ. In essence, items cannot be “packed” in a bin numbered less than τ. This observation has led us to explore the minsum bin packing problem with a consideration of “ready time” in our study.

In brief, for each item i, we assign a “ready time” τ_i, indicating that the item cannot be placed in any bin numbered lower than τ_i. We develop a Polynomial Time Approximation Scheme (PTAS) for this modified problem, which, in turn, provides a PTAS for the dynamic network flow problem described earlier. While we draw upon algorithmic concepts from prior research on the minsum bin packing problem, extending these ideas to our context is not straightforward. Consequently, this work introduces several new theoretical contributions.




 §.§ Problem Definitions

In this section, we define our problem called minsum problem for discrete and weighted set flow on a dynamic network (MS-DWSF). 

Consider a graph with n nodes, denoted by V = {1, …, n} and E ⊆{{u,v}, u,v ∈ V}. Each node i has m_i sets of persons to evacuate. These sets of persons are denoted by G_i,1, …, G_i,m_i. For group G, the size of G is denoted by S(G) ∈ℤ_+ and the weight of G is denoted by w(G) ∈ℤ_+. The capacity of edge e is C(e) ∈ℤ_+. In addition, each edge e has distance d(e) ∈ℤ_+, which is the time that persons need to move between two terminals of the edge. 



Let us denote the collection of groups that are at node i at time t by 𝒮_i^(t). We select from 𝒮_i^(t) which groups to be sent along the edge {i, j}∈ E. We denote the collection of groups that we choose to send along e = {i,j} by D_i,j^(t). The summation of group sizes in D_i,j^(t) must not be larger than C, i.e. ∑_G ∈ D_i,j^(t) S(G) ≤ C({i,j}).

For t = 0, we have S_i^(0) = {G_i,1, …, G_i,m_i} for all i.
Let denote A_j,i^(t) be a collection of groups arriving at i from node j at time t. We have

    A_j,i^(t) = 
      D_j,i^(t - d({j, i}))   {j,i}∈ E  and  t ≥ d({j,i}) 
    ∅    otherwise, and

Then, S_i^(t) = S_i^(t - 1)\( ⋃_j:{i,j}∈ E D_i,j^(t)) ∪( ⋃_j:{i,j}∈ E A_j,i^(t)).

Let the set of facilities be F ⊆ V.
The arrival time of G, denoted by α(G) is the smallest time of arrival that the group is at some node in F, i.e. min{t: G ∈⋃_i ∈ F S_i^(t)}. In the MS-DWSF, we aim to minimize ∑_G w(G)α(G).



§ APX-HARDNESS

In this section we show that MS-DWSF is APX-hard when the underlying graph is bipartite.
We reduce from Max-4OCC-3SAT. This is a version of 3SAT where every variable occurs at most four times in the formula, and we need to satisfy as many clauses as possible. It is known to be APX-hard <cit.>. We start from a given 4OCC-3SAT formula θ on n variables x_1, x_2, …, x_n and m clauses C_1, C_2, …, C_m. We construct an instance of MS-DWSF in the following steps (see Figure <ref>):

    
  * Initiate an empty graph G(V,E).
    
  * For every variable x_i ∈θ, add a vertex v_i to V (called a variable vertex).
    
  * For every clause C_j ∈θ, add a vertex u_j to V
    (called a clause vertex).
    
  * For every vertex v_i ∈ V, add four vertices p_i^1, p_i^2, n_i^1 and n_i^2 to V, and place facilities on vertices p_i^2 and n_i^2.
    
  * If x_i ∈ C_j, then add to E the edge (u_j, p_i^1) with capacity 1 and distance 1. Similarly, if  x_i∈ C_j, then add to E the edge (u_j, n_i^1) with capacity 1 and distance 1. 
    
  * For all i ∈ [1,n], add to E the four edges (x_i,p_i^1), (x_i,n_i^1), (p_i^1,p_i^2) and (n_i^1,n_i^2), with capacity 4 and distance 1 each.
    
  * On each v_i, place a group g_i with size 4 and weight 5. On each u_j, place a group h_j with size 1 and weight 1


We have the following lemma.

There is a constant c such that MS-DWSF cannot be approximated better than a factor of (1+c) in polynomial time.
    

 
Consider any scheduling on the constructed graph. Each facility is at distance 2 from the unit weighted groups of at most 4 clause vertices, since we reduced from a 4OCC-3SAT formula. On the other hand, the groups at the variable vertices each carry a weight 5. So,
to optimize the minsum, the groups from every variable vertex must reach the corresponding facilities at time 2, contributing 10n to the minsum. Since these groups weigh 4 units, this stops the unit weight groups from reaching the same facilities at time 2. Thus it is clear that such a scheduling actually corresponds to an assignment to the underlying 3SAT formula; if the group at v_i goes to the facility on n^2_i, then x_i is assigned 1, and 0 otherwise. All the clause vertices whose groups can reach facilities at time 2 correspond to satisfied clauses. 
Suppose that k  groups from the clause vertices reach facilities at time 2. Then they contribute 2k to the minsum and the rest of the groups contribute 3m-3k, making the minsum a total of 10n + 3m -k. 

Since it is known that at least half of all clauses can be satisfied in a 3SAT formula, we have k ≥  m/2 for the optimum solution. Also, 3m ≥ n in any 3SAT formula. Substituting, we get 10n + 3m -k ≤ 65k. 

So, any solution that is at most (1+c) times the optimum minsum, is at most 65(1+c)k. This corresponds to satisfying at most 65ck less clauses in the 3SAT formula. From <cit.>, we know that Max-4OCC-3SAT cannot be approximated better than by a factor of 1/1900. Setting c = 1/65× 1900 we have the desired result.







 

MS-DWSF is APX-hard even when the underlying graph is bounded degree, bipartite, with all edges having the same length.


Due to our construction, G is bipartite, and all edges have the same length. Since the reduction preserves approximation, the claim follows.




§ PTAS


In this section, we explore a specific instance of the MS-DWSF, focusing on a path graph (V,E) with a fixed number of nodes, denoted as V = {1, …, k} and E = {{1,2}, …, {k-1,k}}. We assume uniform capacity across all edges, represented by C. Furthermore, this scenario includes a single facility located at node 1, i.e., F = {1}. Extending the algorithm designed for a facility at node 1 to any other node is relatively straightforward. Assuming the facility is positioned at node i, the task of transporting items from nodes {1, …, i - 1} to node i and from nodes {i + 1, …, r} to node i becomes two separate challenges that can be independently addressed using the same algorithm.

It is evident that the most critical edge in our instance is the edge {1,2}. If we have a way to transport items in this edge, i.e. we know the set D_2,1^(t) for all t, then, for i > 1, we can have D_i + 1,i^(t - ∑_i' = 2^i d(i' + 1, i')) = D_2,1^(t)∩ (⋃_i' > i S_i'^(0)). We then can reduce the MS-DWSF to the bin packing problem, where we need to pack all items into the bins of size C, which are D_2,1^(1), …, D_2,1^(T) where T indicates the maximum time bins are packed. From now, we will call the collection D_2,1^(t) as bin t. 

Our problem then looks similar to the minsum bin packing problem. However, certain items, such as item G, may not be eligible for inclusion in some bin D_2,1^(t). For instance, if G originates from S_3^(0), it cannot be assigned to D_2,1^(0), signifying it is not feasible to transport G across the edge {2,1} at time 0. This is due to the requisite time steps needed for G to move from node 3 to node 2. Consequently, item G cannot be allocated to the set D_2,1^(t) for any t < d(3,2), reflecting the inherent delay in moving items through the graph. 

In our approach, we adapt the minsum bin packing framework to include a `ready time' τ(G) for each item G, ensuring that the item cannot be placed into any bin numbered less than τ(G). Given that our model operates on a path graph with a fixed number of nodes, the set of possible τ(G) values is finite and of constant size, represented by {τ_1, …, τ_k}. We work under the assumption that these ready times are ordered such that τ_1 < ⋯ < τ_k. Therefore, the problem and objective function for the polynomial-time approximation scheme are defined as follows.

[breakable,bicolor,
  colback=cyan!5,colframe=cyan!5,boxrule=0pt,frame hidden]


Bin-Packing and Objective Function:


One end of the dynamic edge refers to the position of items, while the other end refers to the facility location as previously stated. Assume that we have sets of items G_1,⋯, G_k such that τ(G_i)=τ_i and τ_1 < ⋯ < τ_k. We also assume that we have a sufficient number of bins, and each bin may hold a maximum of 1 in unit weight. It is important to note that the weight of any item cannot exceed 1 unit; otherwise, it cannot be packed. The dynamic edge can only hold one bin per unit of time. That is, we can pack exactly one bin per unit of time. If the bin B_i is packed at time i, then the cost to transport B_i on the dynamic edge is i×| B_i|, where | B_i| is the cardinality of the bin B_i. When time t<τ_1, there are no items ready for packing because τ_1 < ⋯ < τ_k. Therefore, the bins B_1, B_2,…, B_τ_1-1 are empty. When t = τ_1, the items of S_1 (we assume S_1=G_1 initially) are only ready for packing until t = τ_2. We pack one bin per unit of time; hence, we need τ_2-τ_1 bins before t=τ_2. After packing the bins B_τ_1, B_τ_1+1,…, B_τ_2-1, when we arrive at time t=τ_2, we have some unpacked items of S_1 and the items of G_2 to be ready. Therefore, when t=τ_2, the items of S_2 (we assume S_2=G_2∪ S_1∖ (∪_i=τ_1^τ_2-1B_i)) are ready to be packed. We pack an additional τ_3-τ_2 bins before t=τ_3. We repeat the process until t =τ_k-1. When we reach t=τ_k, the items of S_k (we assume S_k=G_k∪ S_k-1∖ (∪_i=τ_k-1^τ_k-1B_i)) are ready to be packed. Finally, pack all of the items of S_k using a minimum number of bins to minimize ∑_j=1^t j×| B_j| where B_t is the last bin packed to evacuate all the items to the facility location (that is, the other end of the dynamic edge). Therefore, our target is to minimize the cost ∑_j=1^t j×| B_j|. A bin B_j is called a feasible bin if the total weight of the items packed in B_j is less than or equal to 1. The feasible bin is referred to as an optimal bin if it appears in an optimal solution. A packing is called feasible packing if all the bins of that packing are feasible. Let n be the total number of items in ∪_i=1^kG_i.




 §.§ Properties of Items, Their Weights and the Partition


We select a fixed constant ϵ with some properties and weights indicated below.



  * 0 < ϵ≤1/4 be a fixed constant such that 1/ϵ is an integer.

  * An item is said to be small if its weight does not exceed ϵ^2; otherwise, it is classified as large.

  * | G_i| =n_i i=1,…,k. Therefore n=∑_i=1^kn_i.

  * It is assumed that G_i contains a set of m_i large items, each of which is contained in the set L_i={x_i,n_i-m_i+1, x_i,n_i-m_i+2,…,x_i,n_i} with w_i,n_i-m_i+1≤ w_i,n_i-m_i+2≤…≤ w_n_i. Hence, m=m_1+m_2+ … +m_k, where m is the total number of large items in I.
    

As a result, we have a set of items S_i at time t=τ_i and τ_i+1-τ_i (i≠ k) bins in which to place some items of S_i in order to accommodate the greatest possible number of items. Additionally, when i=k, a minimum number of bins is required to store all the items of S_k. Consequently, in order to store items of each S_i, a polynomial-time approximation scheme is established below.


Without loss of generality, we can assume that at least one n_i≥1/ϵ^3 i=1,…,k.


If the claim is invalid, then n_i < 1/ϵ^3 for all i = 1, 2, …, n. For an arbitrary bin B_j, B_j must pack some items of one of the sets S_1, S_2, …, S_k. If each n_i<1/ϵ^3, then size of each S_i is bounded by k/ϵ^3 i=1,…,k. Consequently, the cardinality of the power set of each S_i must be bounded by 2^k/ϵ^3 and at least one set of that power set corresponds to the bin B_j. τ_k+n represents the utmost number of bins that can be accommodated in the optimal solution. Therefore, the optimal solution can be determined in the time 𝒪((n+τ_k)2^k/ϵ^3)≤𝒪((k/ϵ^3+τ_k)2^k/ϵ^3) where k and τ_k are constants.


[breakable,bicolor,
  colback=cyan!5,colframe=cyan!5,boxrule=0pt,frame hidden]


Partition:


We divide L_i into 1/ϵ^3 subsets denoted as L_i,1, L_i,2, …, L_i,1/ϵ^3, based on two properties listed below.  

    
  * | L_i,1|≥| L_i,2|≥…≥| L_i,1/ϵ^3|≥| L_i,1| -1 (this indicates that the cardinality of each subset is nearly identical to that of ϵ^3| L_i |).
    
    
  * If x_i,a∈ L_i,j and x_i,b∈ L_i,s such that j < s, then a > b and w_i,a≥ w_i,b (this means that the largest | L_i,1| items of L_i are assigned to L_i,1, followed by the largest | L_i,2| items of remaining items of L_i assigned to L_i,2 and so on).



The first property of the partition determines the exact cardinality of the L_i,j which is either ⌊ϵ^3| L_i |⌋ or ⌈ϵ^3| L_i |⌉ j=1,…, 1/ϵ^3 and the partition is well-defined by the second property.

 The following inequalities hold:

    
  * | G_i ∖ L_i,1|≥ n_i(1-2ϵ^3)
    
  * | L |≤ 2mϵ^3 and | I ∖ L |≥ n(1-2ϵ^3) where L=∪_i=1^kL_i,1.

   


| L_i,1| has a weight of either ⌊ϵ^3| L_i |⌋ or ⌈ϵ^3| L_i |⌉. Consequently, | L_i,1|≤ 2m_iϵ^3 since | L_i| =m_i. We obtain | L|≤ 2mϵ^3 by taking the summation on both sides. Now, | I∖ L|≥ n-2mϵ^3 ≥ n(1-2ϵ^3) since n≥ m. Again, | G_i∖ L_i,1|≥ n_i-2m_iϵ^3 ≥ n_i(1-2ϵ^3) since n_i≥ m_i.




[breakable,bicolor,
  colback=cyan!5,colframe=cyan!5,boxrule=0pt,frame hidden]


Rounded-up Instance:


For all j≥ 2, we assign the largest item in L_i,j as the rounded up weight of each item in L_i,j. This means that for all j≥ 2 and x_i,r∈ L_i,j, we allow σ_i,j=max_x_i,r∈ L_i,jw_i,r be the rounded-up weight of all the items of L_i,j. Despite this, the weights of the items in L_i,1 remain unchanged. There are no changes to the weight of the items in G_i∖ L_i (that is, the small items). We say that an item x_i∈ G_i∖ L_i has weight s_i. The two conditions of the partition <ref> must undoubtedly remain valid even after modifying the item weights in each L_i,j.


[breakable,bicolor,
  colback=cyan!5,colframe=cyan!5,boxrule=0pt,frame hidden]

Packing Instance of OPT:


Consider B_1^OPT, B_2^OPT, …, B_q_t^OPT to be the optimal bins packed at times t=0, t=1, …, t=q_t, respectively, and OPT to be the optimal solution. The packing instance B_i^INS corresponding to each OPT bin B_i^OPT i=1,…,q_t is as follows. 


  * The small items of each B_i^OPT are copied to B_i^INS. Therefore, B_i^OPT and B_i^INS have same small items.


  * If B_i^OPT has p_j items from the set L_r,s of the original instance s=1, 2, …, 1/ϵ^3-1 then B_i^INS receives p_j items from L_r,s+1 of the rounded up instance. We know that for each set L_r,s in L_r, the cardinality of L_r,s is either ⌊ϵ^3| L_r |⌋ or ⌈ϵ^3| L_r |⌉ s=1,…, 1/ϵ^3. Therefore, if we sometimes run out of items in some set L_r,s+1 and do not have an item to assign, it means that | L_r,s| = | L_r,s+1|+1. Such a value of s exists only once per L_i and is unique to that particular L_i. The space in the bin remains unused in this instance.



If OPT^' is the packing instance of OPT then OPT^'≤ OPT.


The small items of B_i^INS and B_i^OPT remain unchanged. However, in the case where B_i^OPT contains p_j items from the set L_r,s s=1, 2, …, 1/ϵ^3-1, then B_i^INS will acquire p_j items from L_r,s+1 of the rounded-up instance. Additionally, it is established that every item in L_r,s+1 has a lower weight than every item in L_r,s. Hence, the lemma is proved.



[breakable,bicolor,
  colback=cyan!5,colframe=cyan!5,boxrule=0pt,frame hidden]


Packing of Original Instance:


Although the packing instance associated with OPT has been established, it is evident that certain items have not yet been packed. When a bin B_i^OPT contains p_j items from the set L_r,s, then the contents of B_i^INS are updated to include p_j items from the rounded-up instance of L_r,s+1. This indicates that r=1,…,k, only the items in L_r,1 are not packed; therefore, L=∪_r=1^kL_r,1 should be packed in the next formulation. Additionally, it is assumed that B_q_t^OPT represents the final bin of OPT, then B_q_t^INS is not necessarily the final bin in packing instance, as B_q_t^INS can be empty. Therefore, it is assumed that the final bin of the packing instance is denoted by B_q_t^'^INS. Next, we define the cell, room, apartment, and house. Let C_i={B_τ_i^INS, B_τ_i+1^INS, …, B_τ_i+1-1^INS} i=1,…,k-1 and C_k={B_τ_k^INS, B_τ_k+1^INS, …, B_q_t^'^INS} be the cells. Each C_i is copied into a new set D_i, so D_i=C_i, and this is known as a room i=1,…,k (see Figure <ref>). Cells are created before packing the items of L, but we must pack the items of L in the rooms as follows. We first pack the items of L_1,1 left to right of the empty bins of D_1,…,D_k so that there is exactly one item from L_1,1 in each empty bin. Similarly, we pack the items of L_i,1 left to right of the empty bins of D_i,…,D_k, making sure that every empty bin has exactly one item i=2, …, k. In some cases, if we run out of empty bins for L_i,1, we must introduce new bins after B_q_t^'^INS and each new bin contains exactly one item of L_i,1 as before. We repeat this process k steps to pack all the items of L. The extra bins are assumed to be B_q_t^'+1^EXT, …, B_q_t^”^EXT, we then assign all of these additional bins to D_k, that is D_k={B_τ_k^INS, …, B_q_t^'^INS, B_q_t^'+1^EXT, …, B_q_t^”^EXT}. A house is defined as H_1^i=∪_x=1^iD_x if L_i,1 is the first set of L such that L_i,1 became empty while placing the items in the empty bins of the set D_i. Subsequently, H_i+1^j=∪_x=i+1^jD_x is likewise a home if L_j,1 (i<j) is a second set of L such that L_j,1 became empty when placing the items in the empty bins of the set D_j. We keep going through the same process until we get all the houses. It is clear that the number of houses is at most k. For a house H_i^j, A_i^r=∪_x=i^rD_x is called an apartmentr=i,…,j. It is evident that H_i^j and A_i^j, in addition to D_i and A_i^i, are identical. Assumed to be the set of all the houses is H, and the total cost of the bins in H is cost(H). Take note that every item in ∪_l=i^jG_l is packed in the house H_i^j, so any two houses can exist independently of one another.


 
Cost(H)≤ (1+cϵ)OPT^' where OPT^' is the solution of packing instance and c=∑_i=1^k1/4^i-1ki(4+9τ_k)^i.


The additional cost incurred for the original instance in comparison to the packaging instance is computed as follows. Suppose H_i^r is a house, and A_i^i, A_i^i+1, …, A_i^r are the blocks of H_i^r. We denote M_l=∑_l=i^jm_l and L_q^'=∪_j=i^qL_j,1 q=i,…,r.




Inequality for Cost(A_i^i):

    Δ_i^i    = cost(A_i^i)-cost(C_i)
       ≤∑_j=t_i+1^t_i+| L_i^'| (j)   (where B_t_i is the last bin in the cell C_i)
        = (t_i+1)+(t_i+2)+… (t_i+| L_i^'|)  
        = t_i| L_i^'|+| L_i^'|(| L_i^'|+1)/2 (use  M_i=∑_j=i^im_j=m_i  and | L_i^'| = | L_i,1|≤ 2M_iϵ^3 )  
       ≤ 2M_iϵ^3t_i+3M_i^2ϵ^6  (use lemma <ref> and (| L_i^'| +1) ≤ (2M_iϵ^3+M_iϵ^3)).

Now, we are looking at the least number of large items in C_i. The total number of large items in C_i is at least



    M_i-∑_j=i^i L_j,1   ≥ M_i-2(∑_j=i^im_jϵ^3)
       = M_i-2M_iϵ^3   (where M_i=∑_j=i^im_j=m_i)
       ≥31M_i/32  (since ϵ≤1/4).

Once more, C_i contains a sum of t_i non-empty bins containing a minimum of 31M_i/32 large items. Therefore, (t_i-τ_i+1) ≥31M_iϵ^2/32. Additionally, C_i utilizes t_i-τ_i+1 bins, and each of t_i-τ_i+1 bins contains at least one item. Consequently, Cost(C_i) ≥(t_i-τ_i+1)^2/4. Now,

    Δ_i^i    = cost(A_i^i)-cost(C_i) 
    
       ≤ 2M_iϵ^3t_i+3M_i^2ϵ^6 
    
        = 2M_iϵ^3(t_i-τ_i+1) + 2(τ_i-1)M_iϵ^3+3M_i^2ϵ^6  (since  (t_i-τ_i+1)+τ_i-1 = t_i)
    
       ≤ 2ϵ(t_i-τ_i+1) 32/31 (t_i-τ_i+1) + 2ϵ(τ_i-1) 32/31 (t_i-τ_i+1) +3ϵ^2 (32/31 (t_i-τ_i+1))^2
    
       (Using  (t_i-τ_i+1) ≥31M_iϵ^2/32 and assume that  (τ_i-1)≥ 0)
    
        =  64/31ϵ(t_i-τ_i+1)^2 + 64/31ϵ(τ_i-1) (t_i-τ_i+1) +3072/961ϵ^2 (t_i-τ_i+1)^2
    
       ≤64/31ϵ 4Cost(C_i) + 64/31ϵ(τ_i-1) 4Cost(C_i) +3072/961ϵ1/4 4Cost(C_i)
    
       (since  Cost(C_i) ≥(t_i-τ_1+1)^2/4≥(t_i-τ_1+1)/4 and ϵ≤1/4)
    
       ≤ (4+9τ_i)ϵ Cost(C_i).

Once more, the situation occurs when (τ_i-1)=-1, or when τ_i=0, the above inequality <ref> will be 

    Δ_i^i   ≤ 2M_iϵ^3(t_i+1)-2M_iϵ^3+3M_i^2ϵ^6
       ≤ 2M_iϵ^3(t_i+1)+M_i^2ϵ^6 (since  M_i^2ϵ^6≥ M_iϵ^3≥ 1)
    
       ≤ 2ϵ Cost(C_i).  (using the procedure used in the inequality <ref> )

Combining inequalities <ref> and <ref> we conclude that cost(A_i^i)< {1+(4+9τ_i)ϵ} cost(C_i).
Similarly, the inequality for Cost(A_i^i+1) is as follows.




Inequality for Cost(A_i^i+1):

    Δ_i^i+1    = cost(A_i^i+1)-(Cost(A_i^i)+ cost(C_i+1))
    
       ≤ 2M_i+1ϵ^3t_i+3M_i+1^2ϵ^6  (where M_i+1=| L_i+1^'| =∑_j=i^i+1m_j=m_i+m_i+1).

In the same manner as before, we are attempting to count the minimum number of large items in A_i^i∪ C_i+1. The sum of all large items in cup A_i^i∪ C_i+1 is equal to or greater than 

    M_i+1-∑_j=i^i+1 L_j,1   ≥31M_i+1/32.

Again, A_i^i∪ C_i+1 has a total of t_i+1 non-empty bins, with at least 31M_i+1/32 large items. Therefore, (t_i+1-τ_i+1) ≥31M_i+1ϵ^2/32. Also, A_i^i∪ C_i+1 uses t_i+1-τ_i+1 bins, and each of them has at least one item. Cosequently, Cost(A^i_i∪ C_i+1) ≥(t_i+1-τ_i+1)^2/4.
Consequently, by employing the analogous inequalities of A_i^i, we obtain
Therefore, if we use the similar inequalities of A_i^i, then we get

    Cost(A_i^i+1)    ≤{1+(4+9τ_i)ϵ}Cost(A_i^i∪ C_i+1)   (using similar inequalities of Δ_i^i)
    
        = {1+(4+9τ_i)ϵ}{(Cost(A_i^i)+ Cost(C_i+1)}
       ≤{1+(4+9τ_i)ϵ}[{1+(4+9τ_i)ϵ}Cost(C_i)+ Cost(C_i+1)] 
    
        (using inequality of Δ_i^i)
    
        = {1+(4+9τ_i)ϵ}^2Cost(C_i)+ {1+(4+9τ_i)ϵ} Cost(C_i+1)

Similarly, we must get 

    Cost(A_i^i+2)    ≤{1+(4+9τ_i)ϵ}^3Cost(C_i)+ {1+(4+9τ_i)ϵ}^2 Cost(C_i+1)
    
       + {1+(4+9τ_i)ϵ} Cost(C_i+2)


    ⋮
 
Hence,

    Cost(A_i^r)     = Cost(H_i^r) 
    
       ≤{1+(4+9τ_i)ϵ}^r-i+1 Cost(C_i)+ {1+(4+9τ_i)ϵ}^r-i Cost(C_i+1)
    
        + {1+(4+9τ_i)ϵ}^r-i-1 Cost(C_i+2)+…+{1+(4+9τ_i)ϵ} Cost(C_r)
    
       ≤{1+(4+9τ_k)ϵ}^r-i+1{Cost(C_i)+Cost(C_i+1)+ … + Cost(C_r)}
        (since τ_i≤τ_k  and {1+(4+9τ_i)ϵ}^r-i+1≥{1+(4+9τ_i)ϵ}^r-i-l for  l≥ 0)

Suppose, there are a total of h houses H_1^l_1, H_l_1+1^l_2, …, H_l_h-1^l_h, where l_1<l_2<…<l_h=k. Therefore, Cost(H_1^l_1)+ Cost(H_l_1+1^l_2)+ …+ Cost(H_l_h-1^l_h) = Cost(H), where H is the union of the sets H_1^l_1, H_l_1+1^l_2, …, H_l_h-1^l_h, then we obtain

    Cost(H)    ≤{1+(4+9τ_k)ϵ}^l_1-1+1{Cost(C_1)+Cost(C_2)+ … + Cost(C_l_1)}
        + {1+(4+9τ_k)ϵ}^l_2-l_1-1+1{Cost(C_l_1+1)+Cost(C_l_1+2)+ … + Cost(C_l_2)}
       …
       {1+(4+9τ_k)ϵ}^l_k-l_k-1-1+1{Cost(C_l_k-1+1)+Cost(C_l_k-1+2)+ … + Cost(C_l_k)}
       ≤{1+(4+9τ_k)ϵ}^k{Cost(C_1)+Cost(C_2)+ … + Cost(C_k)}
       ≤{1+(4+9τ_k)ϵ}^k OPT^'
       ≤{1+ ∑_i=1^k1/4^i-1ki(4+9τ_k)^iϵ} OPT^'( since ϵ≤1/4)
    
        = (1+ cϵ) OPT^'( where  c=∑_i=1^k1/4^i-1ki(4+9τ_k)^i  is a constant )



A packing that is possibly unfeasible but becomes feasible by eliminating the largest small item from each bin containing at least one small item is termed a quasi-feasible packing.


Assuming a bin B_j is packed at time j, its cost can be calculated as j×| B_j |. This indicates that the cost per item of B_j is denoted as j; we refer to this as the charging cost of an item of B_j. Therefore, the charging cost associated with each item in bin B_j is denoted by j.

A feasible packing is also a quasi-feasible packing, according to the definition. As a result, the cost of a quasi-feasible packing is either lower than or equal to the cost of a feasible packing. We now demonstrate that a cost factor of (1+c_1ϵ) must be applied in order to transform the quasi-feasible packing into a feasible packing, where c_1=k+2/4+1/2.

    A quasi-feasible packing Q can be converted into a feasible packing P such that Cost(P)≤ (1+c_1ϵ)Cost(Q) where c_1=k+2/4+1/2


Suppose that the bins in Q are B_1, B_2, …B_q_t^”, where first τ_1-1 bins are empty. We have the rooms D_i={B_τ_i, B_τ_i+1, …, B_τ_i+1-1}  i=1, …, k-1 and when i=k the room is D_k={B_τ_k, B_τ_k+1, …, B_q_t^”}. We divide the room D_i into multiple partitions of size 1/ϵ^2 bins from left to right, with the final partition possibly having fewer bins than 1/ϵ^2 bins. Let D_i={P_i^1, P_i^2, P_i^l_i} be the set of portions such that, with the exception of the final partition P_i^l_i, every P_i^j has exactly 1/ϵ^2 bins. If P_1^1 contains fewer than 1/ϵ-1 bins, we add an extra bin after the final bin in P_1^1; otherwise, we add an extra bin at the 1/ϵ-th position in P_1^1. We add an extra bin at the beginning of each partition for every other partition (i.e., except P_1^1) of D_i and i≥ 1. We find the largest small item in each bin for each partition and transfer it to the new bin for that partition. There are at most 1/ϵ^2 small items in each partition's corresponding new bin since each partition has at most 1/ϵ^2 bins, and each bin contains at most one largest small item. Each small item has a size of at most ϵ^2, as we know. Thus, the new bin's total item size is limited to 1/ϵ^2×ϵ^2=1. As a result, each partition's new bin is a feasible bin. We reduce a quasi-feasible packing Q to a feasible packing P in this way. Additionally, it is evident that there are k rooms in total, and each room has at least one partition. We now compute the additional cost resulting from the packing of each partition's largest small items into the new bin.



Initially, we compute the increment in charging cost for every item in P_1^1. Each bin's largest small item is moved to the new bin at 1/ϵ-th place. The charging cost of the largest item in the i-th bin is increased by 1/ϵ-i when i<1/ϵ. The charging cost of the largest item in the i-th bin does not increase when i>1/ϵ. So, for the largest small items in each bin of P_1^1, the overall cost increment is therefore at most 1/ϵ(1/ϵ-1)/2≤1/2ϵ^2. It is clear that the cost of Q is at least n for n items. Using the observation <ref>, we get Cost(Q)≥ n ≥1/ϵ^3. Therefore, ϵ/2Cost(Q) is the maximum total cost increment for the largest small items in each bin of P_1^1. Once more, when i<1/ϵ, the charging cost of all other items of the i-th bin in P_1^1 (i.e., excluding the largest small item of each bin) remains unchanged. However, when i>1/ϵ, a new bin is placed, and the charging cost of all other items of the i-th bin in P_1^1 increases by exactly 1. Moreover, the cost of every item in the P_1^1 in Q is greater than or equal to 1/ϵ for each i-th (where i>1/ϵ) bin. As a result, the charging cost is increased by a multiplicative factor of at most 1+ϵ. The charging cost increment needs to be calculated for a partition P_i^j, where i,j≥ 1 except for i=j=1. In Q, the charging cost of every item in P_i^j is at least l_1+l_2+… +l_i-1+j-(i-1)/ϵ^2=l-i+1/ϵ^2 because each item in the bins of P_i^j has a charging cost increment of l, where l=l_1+l_2+…+l_i-1+j. Consequently, the charging cost is increased by a multiplicative factor of at most 1+l/l-i+1ϵ^2≤ 1+(k+2)ϵ^2≤ 1+k+2/4ϵ. Hence, combining all the cases, it is determined that Cost(P)≤ (1+c_1ϵ)Cost(Q), with c_1=k+2/4+1/2.
    


Next Fit (NF) bin packing uses one active bin into which it packs the input; and once the free space in this bin becomes too small to accommodate the next item, a new active bin is opened and the previous active bin is never used again. Next Fit Increasing (NFI) bin packing is the same as NF, but the inputs are in increasing order with respect to their weights.


 NFI^+ packs items sorted by non-decreasing
order as NFI, but it moves to the next bin only after the total weight of the contents of the current bin strictly exceed 1.


For a feasible packing P, we define a quasi-feasible packing Q_P as follows. Remove all small items in P and re-pack them using NFI^+ into the empty spaces. Note that since NFI^+ is used here to pack only the small items, the resulting semi-feasible packing is indeed quasi-feasible packing as well.  



    Cost(Q_P)≤ Cost (P)


There is no repackaging involved in the large items. Therefore, the total cost of the large items in P and Q_P is the same. All we have to do is demonstrate that the entire cost of Q_P's small items does not exceed the total cost of small items of P. Suppose that the number of bins used in P is indicated by y. The number of small items in the i-th bin of Q_P is represented by q_i, while the number of small items in the i-th bin of P is represented by p_i. For 1≤ r≤ y, we assert that ∑_i=1^rq_i≥∑_i=1^rp_i. Specifically, this would demonstrate that, given the number of small items being ∑_i=1^yp_i, the number of bins in Q_P is at most y. Let X_i represent the area in the i-th bin of P that is not occupied by large items. In bins 1,…,r of P, the total size of small items is not greater than ∑_i=1^rX_i. Let ζ represent the final bin of Q_P containing small items. 



Since the claim is evidently true for r=ζ, …, y if ζ≤ y, we show it for bins 1,…, min{y,ζ-1}. Since the following bin received at least one small item for each such bin of index i, the total size of all the small items in that bin in Q_P exceeds X_i. Therefore, the total size of small items in bins 1,…,r of Q_P exceeds ∑_i=1^rX_i for every r∈{1,…, min{y,ζ-1}}. The claim follows since these bins in Q_P contain the smallest little objects, while these bins in P contain arbitrary items. Summing up all inequalities ∑_i=1^rq_i≥∑_i=1^rp_i 1≤ r≤ y, we get ∑_r=1^y∑_i=1^rq_i≥∑_r=1^y∑_i=1^rp_i implying that ∑_i=1^y(y-i+1)q_i≥∑_i=1^y(y-i+1)p_i (by calculating the multiplier of every q_i and every p_i in the preceding sum). 
Thus, in P, the packing cost of the small items is ∑_i=1^yi× p_i, whereas in Q_P, it is ∑_i=1^yi× q_i. For any non-negative sequence a_i (1≤ i ≤ y), ∑_i=1^yi× a_i=∑_i=1^y(t+1)× a_i-∑_i=1^y(t-i+1)× a_i and since ∑_i=1^y p_i= ∑_i=1^yq_i, we get ∑_i=1^yi× q_i ≤∑_i=1^yi× p_i as required.


For any input I, the cost for the output of NFI^+ is not larger than OPT(I).


The restrictions on weights of the small items are not used in Lemma <ref>'s proof. The output of NFI^+ is Q_P if all items are small (i.e., if ϵ=1 is used), and P is an optimal packing.


We conclude from the last four lemmas that finding a quasi-feasible packing for the rounded-up instance is sufficient. Once such a packing is achieved, it can be further converted into a feasible packing for the rounded-up instance using Lemma <ref>, and finally into a packing for the original instance using Lemma <ref>. Furthermore, according to Lemma <ref>, each feasible packing has an equivalent quasi-feasible packing in which NFI^+ is used to pack small items into the spaces left by large items. With a constant factor d, which is independent of the input size, all these conversions can be carried out while keeping a cost that varies from the prior cost by a factor of (1 + d ϵ). For any packing P, we determine the quasi-feasible packing of the type Q_P (this is achieved by dynamic programming in a directed graph, see below). This quasi-feasible packing is converted into a feasible packing, which is converted into a packing of the original items. 



 §.§ Dynamic Programming


Our dynamic programming algorithm is typically explained in terms of locating a path within a built-directed graph. In particular, we construct a directed graph G = (V, E) in the manner shown below. Consider the labels as follows.

    label(v_1)=(n_1,2(v_1), n_1,3(v_1), …, n_1,1/ϵ^3(v_1), l_1(v_1))


    label(v_2)=(n_1,2(v_2),…, n_1,1/ϵ^3(v_2),n_2,2(v_2),…, n_2,1/ϵ^3(v_2), l_2(v_2))


    ⋮


    label(v_k)=(n_1,2(v_k),…, n_1,1/ϵ^3(v_k),…, n_k,2(v_k),…, n_k,1/ϵ^3(v_k), l_k(v_k))

where l_i(v_i) indicates that the small items 1 through l_i(v_i) are already packed and the items l_i(v)+1 through ∑_l=1^in_l-∑_l=1^im_l remain to be packed. n_i,j(v_x) indicates the number of items of L_i,j that are not packed yet (for j≥ 2). The label(v_i) vector has a length of i(1/ϵ^3-1)+1. For every potential label, we give a level. We designate i as the level of label(v_i). Consequently, the total number of levels is k. A directed graph G(V, E) will have vertices in V for each possible value of the label, where the directed edges must be formed next (see Figure <ref>).

    | V| is polynomial.


There are at most m_i+1 ≤ n_i+1 different values that n_i,j(v_x) may have. This is because the value of n_i,j(v_x) is an integer in the interval [0,m_i] for each value of 2≤ j ≤1/ϵ^3. The maximum number of distinct values for l_i(v_i) is ∑_l=1^in_l-∑_l=1^im_l+1≤∑_l=1^in_l+1. As a result, the number of possible labels in label(v_i) is at most (∑_l=1^in_l+1)^i(1/ϵ^3-1)+1≤ (n+1)^i(1/ϵ^3-1)+1≤ (n+1)^k(1/ϵ^3-1)+1 and this is polynomial (as ϵ and k are fixed constants).

We next describe the edge set E. A vector for a generic packing pattern is defined as follows.

    pat_1=(pat_1,2, …, pat_1,1/ϵ^3,p_1,l_1)


    pat_2=(pat_1,2, …, pat_1,1/ϵ^3, pat_2,2, …, pat_2,1/ϵ^3, p_2,l_2)


    ⋮


    pat_k=(pat_1,2, …, pat_1,1/ϵ^3, pat_2,2, …, pat_2,1/ϵ^3,…, pat_k,2, …, pat_k,1/ϵ^3,  p_k,l_k)

where [p_i,l_i] represents the interval of the small items that are packed into this bin (that is, p_i, p_i+1, …, and l_i are packed into this bin) and pat_i,j indicates the number of items of L_i,j that are packed into this bin. We require that for each j, 0≤ pat_i,j≤| L_i,j|, 1≤ p_i≤ l_i ≤∑_l=1^in_l-∑_l=1^im_l+1, where l_i=∑_l=1^in_l-∑_l=1^im_l+1 only if p_i=∑_l=1^in_l-∑_l=1^im_l+1, in which case no small items are packed into the bin. Now, we introduce edges as follows. 





[breakable,bicolor,
  colback=cyan!5,colframe=cyan!5,boxrule=0pt,frame hidden]


Edges in level i vertices:


Under the convention that ∑_l=p_i^p_i-1s_l=0, we need ∑_l=1^i∑_j=2^1/ϵ^3(pat_l,j×σ_l,j)+∑_l=p_i^l_i-1s_l≤ 1 (keep in mind that σ_i,j is the rounded up weight of each item of L_i,j when j≥ 2 explained in <ref>, and s_l is the weight of the small item p_l), and if l_i<∑_l=1^in_l-∑_l=1^im_l, then ∑_l=1^i∑_j=2^1/ϵ^3 (pat_l,j ×σ_l,j)+ ∑_l=p_i^l_is_l> 1. The first sum in these inequalities applies to sets of the form L_i,j, while the second sum applies to small items. The second condition is that l_i<∑_l=1^in_l-∑_l=1^im_l (rather than l_i≤∑_l=1^in_l-∑_l=1^im_l, since the bin containing the largest packed small item need not have a total weight greater than 1). Consequently, the last bin containing small items will have the packing pattern with l_i=∑_l=1^in_l-∑_l=1^im_l, and other bins without any small items might exist, in which case p_i=l_i=∑_l=1^in_l-∑_l=1^im_l+1 would apply. Specifically, all packing patterns will have p_i=l_i=1 if no small items exist. A vector is not a generic packing pattern if it does not meet the above requirements. For every j≥ 2, if pat_r,j≤ n_r,j(v_i) r=1,…,i  j=2,…,1/ϵ^3 and p_i=l_i(v_i)+1, then a generic packing pattern pat_i is said to be consistent with a vertex v_i. Additionally, for any generic packing pattern consistent with v_i, we have a directed edge running from v_i to a vertex whose label is (n_1,2(v_i)-pat_1,2,… ,n_1,1/ϵ^3(v_i)-pat_1,1/ϵ^3,n_2,2(v_i)-pat_2,2,… ,n_2,1/ϵ^3(v_i)-pat_2,1/ϵ^3,…, n_i,2(v_i)-pat_i,2,… ,n_i,1/ϵ^3(v_i)-pat_i,1/ϵ^3, l_i ) with the cost of the edge ∑_l=1^in_l-∑_l=1^im_l-l_i(v_i)+∑_l=1^i∑_j=2^1/ϵ^3n_l,j(v_i) (that is, the number of items for which the ready time is less than or equal to τ_i, that remain unpacked in v_i). 



We initially take a path from the vertex s_1=(| L_1,2|, …, | L_1,1/ϵ^3|, 0) and end it at (0,…,0, n_1-m_1) if the path length is less than or equal to τ_2-τ_1. We then create some artificial vertices and directed edges (with the cost of the artificial edges are 0) at the end of (0,…,0, n_1-m_1) to get the length τ_2-τ_1. If the length of the path is greater than τ_2-τ_1, we start a path from the vertex (| L_1,2|, …, | L_1,1/ϵ^3|, 0) and end it at a vertex t_1 so that the length is τ_2-τ_1. Since | V| is polynomial, finding t_1 must take polynomial time. We assume that t_1=(| L_1,2|_1, …, | L_1,1/ϵ^3|_1,n_1^*-m_1^*) where | L_1,j|_1≤| L_1,j| and n_1^*-m_1^*≤ n_1-m_1. We present τ_2-τ_1 bins, which correspond to the path of length τ_2-τ_1 mentioned above. Using the items in the aforementioned τ_2-τ_1 bins, we also update all packing patterns pat_l 1=2, …, k. From t_1 to s_2=(| L_1,2|_1, …, | L_1,1/ϵ^3|_1,| L_2,2|, …, | L_2,1/ϵ^3|,n_1^*-m_1^*), we create a directed edge with cost 0. s_2 is a vertex of level 2.



For 2≤ i≤ k-1, we take a path from the vertex s_i and end it at (0,…,0, ∑_l=1^in_l-∑_l=1^im_l) (here, i(1/ϵ^3-1)+1 is the vector length) if the path length is less than or equal to τ_i+1-τ_i and then we create some artificial vertices and directed edges (with the cost of the artificial edges are 0) at the end of (0,…,0, ∑_l=1^in_l-∑_l=1^im_l) to get the length of the path to be τ_i+1-τ_i; otherwise, we start at the vertex s_i and follow a path to a vertex t_i, with the length τ_i+1-τ_i. We assume that t_i=(| L_1,2|_i, …, | L_1,1/ϵ^3|_i,| L_2,2|_i, …, | L_2,1/ϵ^3|_i,…,| L_i,2|_i, …, | L_i,1/ϵ^3|_i, n_i^*-m_i^*) where | L_r,j|_i≤| L_r,j| r=1,…,i  j=2,…, 1/ϵ^3. We present τ_i+1-τ_i bins, which correspond to the path of length τ_2-τ_1 mentioned above. Using the items in the aforementioned τ_i+1-τ_i bins, we also update all packing patterns pat_l 1=i+1, …, k. From t_i to s_i+1=(| L_1,2|_i, …, | L_1,1/ϵ^3|_i,| L_2,2|_i, …, | L_2,1/ϵ^3|_i,…,| L_i,2|_i, …, | L_i,1/ϵ^3|_i, | L_i+1,2|,…, | L_i+1,1/ϵ^3|, n_i^*-m_i^*), we create a directed edge with cost 0. s_i+1 is a vertex of level i+1.



For i=k, we take a path from the vertex s_k and end it at t_k=(0,…,0, ∑_l=1^kn_l-∑_l=1^km_l) (here, k(1/ϵ^3-1)+1 is the vector length). We add one bin to each edge of the path from s_1 to t_k, with the exception of the edges between t_i and s_i+1. This is our directed graph G(V, E) as a result.




[breakable,bicolor,
  colback=cyan!5,colframe=cyan!5,boxrule=0pt,frame hidden]


Explanation:


The path 𝒫 from s_1 to t_k provides us with a quasi-feasible packing on the original instance, which we will now explain. In the graph G(V, E), let 𝒫_i denote the path from s_i to t_i. A quasi-feasible packing of type Q_P_i can be created given a path 𝒫_i, and its cost is equal to that of the path 𝒫_i. If the l-th edge of the path 𝒫_i corresponds to a pattern pat_i, then the l-th bin of the solution SOL_i is created as follows. We pack the previously unpacked items from L_i,j to this bin pat_i,j for j≥ 2. If p_i≤∑_l=1^in_l-∑_l=1^im_l, the set of small items p_i, p_i+1, …, l_i are added to this bin. This solution SOL_i is quasi-feasible since, by contradiction, the removal of the last (and largest) small item of each bin will leave items of total weight at most 1. Note also that the cost of SOL_i is exactly the cost of the path 𝒫_i, since each item gets counted once for every bin up to the one that contains it. Conversely, in the graph with the same cost, a path from s_i to t_i in the quasi-feasible packing Q_P_i corresponds to a feasible packing P_i. All bins are packed according to the above-defined pattern since the small items are packed using NFI^+. To be more precise, let's say we have a bin and an item set S_i (remember that S_i is the union of G_i and the unpacked items of G_1,…, G_i-1, and initially S_1=G_1). pat_1,j=| L_1,j∩ S_i| defines the first 1/ϵ^3-1 components of the pattern pat_i. Similarly, pat_2,j=| L_2,j∩ S_i| defines the next 1/ϵ^3-1 components of the pattern pat_i. Also, pat_i,j=| L_i,j∩ S_i| represents the ((i-1)(1/ϵ^3-1)+1)-th component to i(1/ϵ^3-1)-th component of the same pattern pat_i. p_i is the smallest index of any small item packed into the bin and l_i is the largest index of any small item packed into the bin. If no small item is packed, then p_i=l_i=∑_l=1^in_l-∑_l=1^im_l+1. Once again, since each item gets counted once for every bin up to the one that contains it, the cost of the path is equal to the cost of the quasi-feasible packing Q_P_i. Since | V| is polynomial, all these must be counted in polynomial time.



Observe that s_1 and t_k are fixed vertices, as s_1 relates to every item in G_1, while t_k relates to packing every item in I. Since there is an edge from t_1 to s_2, the path length from s_1 to s_2 is τ_2-τ_1+1. Thus, τ_k-τ_1+(k-1) is the path length from s_1 to s_k. Since | V| is polynomial and τ_k-τ_1+(k-1)≤τ_k-k-2 (a constant), the number of paths of length τ_k-τ_1+(k-1) must be calculated in polynomial time. In order for the path from s_k to t_k to be the shortest path, we must find the optimal path from s_1 to s_k. After combining all k steps, the shortest path in terms of cost corresponds to a quasi-feasible packing Q_P of least cost, which we designate by SOL. This is because any quasi-feasible packing of the type Q_P corresponds to a path 𝒫. Recall that an output solution is constructed by converting SOL into a feasible solution SOL^' for the rounded-up instance, as shown in the lemma <ref>, and converting SOL^' into a solution SOL^” to the original instance, as shown in lemma <ref>.


If OPT is the optimal solution to our problem, the cost of SOL^” is at most (1+d·ϵ)OPT where c=∑_i=1^k1/4^i-1ki(4+9τ_k)^i, c_1=k+2/4+1/2, and d=c+c_1+c× c_1/4.


Let OPT^' be the quasi-feasible packing of the rounded-up instance. Also, as previously noted, SOL^' is the feasible packing of the rounded-up instance. Thus, SOL^' provides a feasible solution for quasi-feasible packing OPT^' for the rounded-up instance. Using Lemma <ref>, we get Cost(SOL^')≤ (1+c_1·ϵ) OPT^' where c_1=k+2/4+1/2. Again, using Lemma <ref>, we obtain Cost(SOL^')≤ (1+c_1·ϵ) OPT. Also, using Lemma <ref>, we obtain Cost(SOL^”)≤ (1+c·ϵ)Cost(SOL^'), where c=∑_i=1^k1/4^i-1ki(4+9τ_k)^i. Furthermore, Lemma <ref> states that each feasible packing has an equivalent quasi-feasible packing, where NFI^+ is utilized to pack small items into the spaces left by large items. Hence, Cost(SOL^”)≤ (1+c·ϵ)· (1+c_1·ϵ)OPT = (1+(c+c_1+c· c_1·ϵ)ϵ)OPT ≤ (1+d·ϵ) OPT where d = c+c_1+c× c_1/4 (recall that ϵ≤1/4).









§ CONCLUDING REMARKS


The evacuation problem is extended in this study with the help of the minsum bin packing problem, which takes items with different ready times and weights. We show APX-hardness for this new problem and apply it to develop an evacuation method for non-separable groups of individuals. Currently, our PTAS algorithm is restricted to a single destination dynamic edge. However, with minor modifications, this process works for a single destination path of any length. As an immediate direction for future work, the graph may be generalized to a tree while having a single destination. In this case, varying the edge capacities may drastically affect the evacuation process. It will be a much challenging task to obtain algorithmic results for graphs with multiple destinations.



unsrt 
  
