11institutetext: School of Computer Science, Ariel University, Israel
11email<EMAIL_ADDRESS>
#  $k$-times bin packing and its application to fair electricity distribution

Dinesh Kumar Baghel 11 Erel Segal-Halevi 11

###### Abstract

Given items of different sizes and a fixed bin capacity, the bin-packing
problem is to pack these items into a minimum number of bins such that the sum
of item sizes in a bin does not exceed the capacity. We define a new variant
called _$k$ -times bin packing ($k$BP)_, where the goal is to pack the items
such that each item appears exactly $k$ times, in $k$ different bins. We
generalize some existing approximation algorithms for bin-packing to solve
$k$BP, and analyze their performance ratio.

The study of $k$BP is motivated by the problem of _fair electricity
distribution_. In many developing countries, the total electricity demand is
higher than the supply capacity. We show that $k$-times bin packing can be
used to distribute the electricity in a fair and efficient way. Particularly,
we implement generalizations of the First-Fit and First-Fit-Decreasing bin-
packing algorithms to solve $k$BP, and apply the generalizations to real
electricity demand data. We show that our generalizations outperform existing
heuristic solutions to the same problem.

###### Keywords:

Approximation algorithms bin packing first-fit first-fit decreasing fair
division Karmarkar-Karp algorithms Fernandez de la Vega-Lueker algorithm
electricity distribution utilitarian metric egalitarian metric utility
difference.

##  1 Introduction

This work is motivated by the problem of _fair electricity distribution_. In
developing countries, the demand for electricity often surpasses the available
supply [15]. Such countries have to come up with a fair and efficient method
of allocating of the available electricity among the households.

Formally, we consider a power-station that produces a fixed supply $S$ of
electricity. The station should provide electricity to $n$ households. The
demands of the households in a given period are given by a (multi)set $D$.
Typically, $\sum_{i}D[i]>S$ (where $D[i]$ is the electricity demand of a
household $i$), so it is not possible to connect all households
simultaneously. Our goal is to ensure that each household is connected the
same amount of time, and that this amount is as large as possible. We assume
that an agent gains utility only if the requested demand is fulfilled;
otherwise it is zero. Practically it can be understood as follows: Suppose at
some time, a household $i$ is running some activity that requires $D[i]$
kilowatt of electricity to operate; in the absence of that amount, the
activity will not function. Therefore, an allocation where demands are
fractionally fulfilled is not relevant.

A simple approach to this problem is to partition the households into some $q$
subsets, such that the sum of demands in each subset is at most $S$, and then
connect the agents in each subset for a fraction $1/q$ of the time. To
maximize the amount of time each agent is connected, we have to minimize $q$.
This problem is equivalent to the classic problem of _bin-packing_. In this
problem, we are given some $n$ items, with sizes given by a multiset of
positive real numbers $D$, and a positive real number $S$ representing the
capacity of a bin. The goal is to pack items in $D$ into the smallest possible
number of bins, such that the sum of item sizes in each bin is at most $S$.
The problem is NP-complete [8], but has many efficient approximation
algorithms.

However, even an optimal solution to the bin-packing problem may provide a
sub-optimal solution to the electricity division problem. As an example,
suppose we have three households $x,y,z$ with demands $2,1,1$ respectively,
and the electricity supply $S=3$. Then, the optimal bin-packing results in $2$
bins, e.g. $\\{x,y\\}$ and $\\{z\\}$. This means that each agent would be
connected $1/2$ of the time. However, it is possible to connect each agents
$2/3$ of the time, by connecting each of the pairs
$\\{x,y\\},\\{x,z\\},\\{y,z\\}$ for $1/3$ of the time, as each agent appears
in $2$ different subsets. More generally, suppose we construct $q$ subsets of
agents, such that each agent appears in exactly $k$ different subsets. Then we
can connect each subset for $1/q$ of the time, and each agent will be
connected $k/q$ of the time.

To study this problem more abstractly, we define the _$k$ -times bin-packing
problem (or $k\text{BP}$ in short)_. The input to $k$BP is a set of $n$ items
with sizes given by a multiset $D$, a positive real number $S$ representing
the capacity of a bin, and an integer $k\geq 1$. The goal is to pack items in
$D$ into the smallest possible number of bins, such that the sum of item sizes
in each bin is at most $S$, and each item appears in $k$ different bins, where
each item occurs at most once in a bin. In the above example, $k=2$.

###  1.1 Using existing bin-packing algorithms for $k$BP

Several existing algorithms for bin-packing can be naturally extended to
$k$BP. However, it is not clear whether the extension will have a good
approximation ratio.

As an example, consider the simple algorithm called _first-fit (FF)_ : process
the items in an arbitrary order; pack each item into the first bin it fits
into; if it does not fit into any existing bin, open a new bin for it. In the
example $D=[10,20,11],S=31$, the FF would pack two bins: $\\{10,20\\}$ and
$\\{11\\}$. This is clearly optimal, so the approximation ratio here is $1$.

One way to extend it to $k$BP is by processing each item $k$ times in
sequence. In the above example, with $k=2$, FF will process the items in order
$[10^{1},10^{2},20^{1},20^{2},11^{1},11^{2}]$, where the superscript specifies
the instance to which an item belongs. This results in four bins:
$\\{10^{1},20^{1}\\},\\{10^{2},20^{2}\\},\\{11^{1}\\},\\{11^{2}\\}$, which
simply repeats $k$ times the solution obtained from $FF$ on $D$. However, the
optimal solution here is 3 bins:
$\\{10^{1},20^{1}\\},\\{11^{1},10^{2}\\},\\{20^{2},11^{2}\\}$, so the
approximation ratio here is $4/3$.

Another way to extend FF to $k$BP, which we call $FFk$, is to process the
whole sequence $D$, $k$ times. In the above example, FF will process the
sequence $D_{2}=DD=[10^{1},20^{1},11^{1},10^{2},20^{2},11^{2}]$ . Applying the
$FFk$ algorithm to this input instance will result in three bins
$\\{10^{1},20^{1}\\},\\{11^{1},10^{2}\\},\\{20^{2},11^{2}\\}$, which is
optimal. Thus, while the extension of FF to $k$BP is simple, it is not
trivial, and it is vital to study the approximation ratio of such algorithms
in this case.

As another example, consider the approximation schemes by de la Vega and
Lueker [23] and Karmarkar and Karp [14]. These algorithms use a linear program
that counts the number of different _configurations_ of each type in the
packing (see subsection 5.1 for the definitions). One way in which these
algorithms can be extended, without modifying the linear program, is to give
$D_{2}$ as the input. But then, a configuration might have more than one copy
of an item in $D$, which violates the $k$BP constraint. Another approach is to
modify the constraint in the configuration linear program, to check that there
are $k$ copies of each item in the solution, while keeping the same
configurations as for the input $D$. Doing so will respect the $k$BP
constraint. Again, while the extension of the algorithm is straightforward, it
is not clear what the approximation ratio would be; this is the main task of
the present paper.

###  1.2 Our contribution

Our main contribution is to extend some well-known approximation algorithms
for bin-packing to the setting of $k$BP. The most trivial way to do this is
just to run an existing bin-packing algorithm, and duplicate the output $k$
times. However, this will not let us enjoy the benefits of $k$BP for
electricity division (in the above example, this method will yield $4$ bins,
so that each agent will be connected for $2/4=1/2$ of the time). Therefore, we
present more elaborate extensions, that attain better performance. The
algorithms we extend can be classified into two classes:

  1. 1.

Fast constant-factor approximation algorithms first-fit ($FF$) and first-fit-
decreasing ($FFD$). For bin-packing, these algorithms find a packing with at
most $1.7\cdot OPT(D)$ and $\frac{11}{9}\cdot{OPT}(D)+\frac{6}{9}$ bins
respectively [6, 5] We adapt these algorithms by running them on an instance
made of $k$ copies, $DDD\ldots\\{k\text{th copy of }D\\}$, which we denote by
$D_{k}$. We show that, for $k>1$, the extension of $FF$ to $k$BP (which we
call $FFk$) finds a packing with at most $(\frac{1}{k}\cdot
1.7+\left(1-\frac{1}{k}\right)\cdot 1.5)\cdot OPT(D_{k})+3\cdot k$ bins. The
asymptotic approximation ratio of $FFk$ (a generalization of $FFk$ when $k$ is
large approaches 1.5, which is better than the asymptotic ratio of $FF$. We
also prove that the lower bound for $FFDk$ (the extension of $FFD$ to $k$BP)
is $\frac{7}{6}\cdot{OPT}(D_{k})+1$, and conjecture by showing on simulated
data that $FFDk$ solves $k$BP with at most $\frac{11}{9}\cdot
OPT(D_{k})+\frac{6}{9}$ bins which gives us an asymptotic approximation ratio
of at most $11/9$.

  2. 2.

Polynomial-time approximation schemes, such as the algorithms by Fernandez de
la Vega and Lueker [23] and Karmarkar and Karp [14]. We show that the
algorithm by Fernandez de la Vega and Lueker can be extended to solve $k$BP
using at most $\leq(1+2\cdot\epsilon)OPT(D_{k})+k$ bins for any fixed
$\epsilon\in(0,1/2)$. For every $\epsilon>0$, Algorithm 1 in [14] solves $k$BP
using bins at most $(1+2\cdot
k\cdot\epsilon)OPT(D_{k})+\frac{1}{2\cdot\epsilon^{2}}+(2\cdot k+1)$ bins, and
runs in time
$O(n(D_{k})\cdot\log{n(D_{k})}+T(\frac{1}{\epsilon^{2}},n(D_{k}))$, where
$n(D_{k})$ is the number of items in $D_{k}$, and $T$ is a polynomially-
bounded function. Algorithm 2 in [14] generalized to solve $k$BP using at most
$OPT(D_{k})+O(k\cdot\log^{2}{OPT(D)})$ bins, and runs in time
$O(T(\frac{n(D)}{2},n(D_{k}))+n(D_{k})\cdot\log{n(D_{k})})$.

The fair electricity division problem was introduced by [19, 20] under the
name of “fair load-shedding”. They presented several heuristic as well as ILP-
based algorithms, and tested them on a dataset of $367$ households from
Nigeria. We implement the $FFk$ and $FFDk$ algorithms for finding approximate
solutions to $k$BP, and use the solutions to determine a fair electricity
allocation. We test the performance of our allocations on the same dataset of
[19]. We compare our results on the same metrics used by [19]. These metrics
are utilitarian and egalitarian social welfare and the maximum utility
difference between agents. We compare our results in terms of hours of
connection to supply on average, utility delivered to an agent on average, and
electricity supplied on average, along with their standard deviation. We find
that our results surmount their results in all the above parameters. $FFk$ and
$FFDk$ run in time that is nearly linear in the number of agents. We conclude
that using $k$BP can provide a practical, fair and efficient solution to the
electricity division problem.

###  1.3 Organization of the paper

In section 2, we discuss the work related to our research problem. In section
3, we give some definitions and notations. In section 4.1, we prove the upper
bound for the $FFk$ algorithm and the main theorems and lemmas used in its
proof. In section 4.2, we state the lemma, which proves the lower bound for
the $FFDk$ algorithm. Section 5, discusses the Fernandez de la Vega-Lueker and
Karmarkar-Karp algorithms and highlights the difference between our extensions
to these algorithms and the original.

In Section 6, we discuss the experiments related to the $k$BP adaptation of
$FFk$ and $FFDk$ algorithms to solve the electricity packing problem, and the
$FFk$ and $FFDk$ bin packing algorithms. The experimental findings of the
$FFk$ and $FFDk$ bin packing algorithms, which validate our conjecture in
subsection 4.1 and 4.2, are presented in section 7.2, along with the results
of applying approximation algorithms to the electricity distribution problem
using data from 367 households [20]. Finally, in section 8, we conclude with a
summary and directions for future work. We defer most of the technical proofs
and algorithms to the Appendix.

##  2 Related Literature

##### First-fit:

We have already defined the working of $FF$ in subsection 1.1. Denote by $FF$
the number of bins used by the First-Fit algorithm, and by $OPT$ the number of
bins in an optimal solution for a multiset $D$. An upper bound of $FF\leq
1.7OPT+3$ was first proved by Ullman in 1971 [16]. The additive term was first
improved to 2 by [7] in 1972. In 1976, [9] improved the bound further to
$FF\leq\lceil 1.7OPT\rceil$, equivalent to $FF\leq 1.7OPT+0.9$ due to the
integrality of $FF$ and $OPT$. This additive term was further lowered to
$FF\leq 1.7OPT+0.7$ by [26]. Finally, in 2013 [6] settled this open problem
and proved that $FF\leq\lfloor 1.7OPT\rfloor$, which is tight.

##### First-fit decreasing:

Algorithm _first-fit decreasing_ ($FFD$) first sorts the item in non-
increasing order, and then implements $FF$ on it. In 1973, in his doctoral
thesis [13], D. S. Johnson proved that $FFD\ \leq\frac{11}{9}OPT+4$.
Unfortunately, their proof spanned more than 100 pages. Later, in 1985 [1]
simplified their proof and improved the additive term to 3. In 1992 [18]
further simplified the proof and showed that the additive term is 1. Then, in
1997, [17] narrowed the additive constant to 7/9 without formal proof.
Finally, in 2007 [5] proved that the additive constant is 6/9. They also gave
an example which achieves this bound.

##### Efficient approximation schemes:

In 1981, Fernandez de la Vega and Lueker [23] presented a polynomial time
approximation scheme to solve bin packing. Their algorithm accepts as input an
$\epsilon>0$ and produces a packing of the items in $D$ of size at most
$\left(1+\epsilon\right)OPT+1$. Their running time is polynomial in the size
of $D$ and depends on $1/\epsilon$. They invented the _adaptive rounding_
method to reduce the problem size. In adaptive rounding, they initially
organize the items into groups and then round them up to the maximum value in
the group. This results in a problem with a small number of different item
sizes, which can be solved optimally using the linear configuration program.
Later, [14] devised several PTAS for the bin-packing problem. One of the
Karmarkar-Karp algorithms solves bin-packing using at most
$OPT+O({log^{2}OPT})$ bins. Other Karmarkar–Karp algorithms have different
additive approximation guarantees, and they all run in polynomial time. This
additive approximation was further improved to $O(log{OPT}+log{log{OPT}})$ by
[21]. They used a “glueing” technique wherein they glued small items to get a
single big item. In 2017, [11] further improved the additive approximation to
a logarithmic term $O(log{OPT})$.

Recently, [3] has solved in polynomial time a more general variant of bin
packing, with partition matroid constraints. Their algorithm packs the items
in $OPT+O(\frac{OPT}{(\ln{\ln OPT})^{\frac{1}{17}}})$ bins. Their algorithm
can be used to solve the $k$BP: for each item in $D$, define a category that
contains $k$ items with the same size. Then, solve bin-packing with the
constraint that each bin can contain at most one item from each category (it
is a special case of a partition-matroid constraint). However, in the present
paper we focus on the special case of $k$BP. This allows us to attain a better
running-time (with $FFk$ and $FFDk$), and a better approximation ratio (with
the de la Vega–Lueker and Karmarkar–Karp algorithms).

##### Cake cutting and electricity division:

The electricity division problem can also be modeled as a classic resource
allocation problem known as ‘cake cutting’. The problem was first proposed by
Steinhaus [22]. A number of cake-cutting protocols have been discussed in [2,
24]. In cake cutting, a cake is a metaphor for the resource. Like previous
approaches, a time interval can be treated as a resource. A cake-cutting
protocol then allocates this divisible resource among agents who have
different valuation functions (or preferences) according to some fairness
criteria. The solution to this problem differs from the classic cake-cutting
problem in the sense that at any point in time, $t$, the sum of the demands of
all the agents, should respect the supply constraint, and several agents may
share the same piece.

##  3 Notation

We denote by $S\in{\mathbb{R}}_{>0}$, the bin capacity (also the total
available supply of electricity for distribution). We denote the multiset of
$n$ items by $D$. Each item in $D$ models an agent (or a household) in the
real world. In the context of electricity distribution, $D[i]$ denotes the
demand for electricity of an agent $i$.

Let $n(D)$ and $m(D)$ denote the number of items and the number of different
item sizes in $D$, respectively. Let $c[i]$ denote the $i$th size. We denote
by $n[i]$ the number of items with size $c[i]$. The _size_ of a bin is defined
as the sum of all the item sizes in that bin. Given a set $B$ of items, we
denote its size by $V(B)$.

We denote $D_{k}:=DD\ldots k\text{th copy of }D$. By $bins(D_{k})$ we denote
the number of bins used for packing the items in $D_{k}$ by the specific
algorithm under consideration, and by $OPT(D_{k})$ we denote the minimum
number of bins required.

Note that each item should appear at most once in each bin, and at the same
time, each item should appear in $k$ different bins. Consider the example in
section 1. There are three items $x,y,z$ with demand $2,1,1$ respectively. Let
$k=2$ and $S=3$. Then, one valid solution could be the bins
$\\{x,y\\},\\{y,z\\},\\{z,x\\}$. Note that each item appears two times
overall, but appears at most once in each bin. In contrast,
$\\{x,y\\},\\{y,z,z\\},\\{x\\}$ is not a valid solution, as there are two
copies of $z$ in the same bin.

##  4 Fast Approximation Algorithms

###  4.1 $FFk$ — First-Fit for $k$BP

The $k$-times version of the first-fit bin packing algorithm packs each item
of $D_{k}$ in order into the first bin where it fits and does not violate the
constraint that each item should appear in a bin at most once. If the item
does not fit into any currently open bins, $FFk$ creates a new bin and packs
the item into this newly opened bin. For example: consider
$D=\\{10,20,11\\},k=2,S=31$. $FFk$ will result in bins
$\\{10,20\\},\\{11,10\\},\\{20,11\\}$. It is known that the asymptotic
approximation ratio of FF is $1.7$ [6]; below, we prove that the asymptotic
approximation ratio of $FFk$ is better, and it improves when $k$ increases.

###### Theorem 4.1

For every input $D$, and $k\geq 1$, $FFk(D_{k})\leq(\frac{1}{k}\cdot
1.7+\left(1-\frac{1}{k}\right)\cdot 1.5)\cdot OPT(D_{k})+3\cdot k$.

###### Proof

At a very high level, the proof works as follows:

  * •

We define a _weight_ for each item, which depends on the item size, and may
also depend on the instance to which the item belongs.

  * •

We prove that the average weight of each bin in an optimal packing is at most
some real number $Z$, so that the total weight of all items is at most $Z\cdot
OPT(D_{k})$.

  * •

We prove that the average weight of a bin in the $FFk$ packing (except some
$3k$ bins that we will exclude from the analysis) is at least some real number
$Y$, so the total weight of all items is at least $Y\cdot(FFk(D_{k})-3\cdot
k)$.

  * •

Since the total weight of all items is fixed, we get $FFk(D_{k})-3\cdot
k\leq(Z/Y)\cdot OPT(D_{k})$, which gives an asymptotic approximation ratio of
$Z/Y$.

##### Basic weighting scheme.

The basic weighting scheme we use follows [4]. The weight of any item with
size $V$ is defined as

$\displaystyle w(V):=V/S+r(V),$

where $r$ is a _reward function_ , computed as follows:

$r(V):=\begin{cases}0\quad&\text{if }V/S\leq\frac{1}{6},\\\
\frac{1}{2}(V/S-\frac{1}{6})\quad&\text{if
}V/S\in(\frac{1}{6},\frac{1}{3}),\\\ 1/12\quad&\text{if
}V/S\in[\frac{1}{3},\frac{1}{2}],\\\ 4/12\quad&\text{if
}V/S>\frac{1}{2}.\end{cases}$

For $k>1$, we use a modified weighting scheme, which gives different weights
to items that belong to different instances. This allows us to get a better
asymptotic ratio. We describe the modified weighting scheme below.

##### Associating bins with instances.

Recall that $FFk$ processes one instance of $D$ completely, and then starts to
process the next instance. We associate each bin in the $FFk$ packing with the
instance in which it was opened. So for every $j\in\\{1,\ldots,k\\}$, the
_bins of instance $j$_ are all the bins, whose first allocated item comes from
the $j$-th instance of $D$. Note that bins of instance $j$ do not contain
items of instances $1,\ldots,j-1$, but may contain items of any instance
$j,\ldots,k$.

For the analysis, we also need to associate some bins in the optimal packing
with specific instances. We consider some fixed optimal packing. For each bin
$B$ in that packing:

  * •

If $B$ contains an item $x$ with $V(x)>S/2$, and $x$ belongs to instance $j$,
then we associate bin $B$ with instance $j$. Clearly, there can be at most one
item with size larger than $S/2$ in any feasible bin, so there is no
ambiguity. Moreover, we ensure that all other items in $B$ belong to instance
$j$ too: if some other item $x^{\prime}\in B\setminus\\{x\\}$ belongs to a
different instance $j^{\prime}$, then we replace $x^{\prime}$ with its copy
from instance $j$. Note that the other copy of $x^{\prime}$ must be located in
a bin different than $B$, due to the restrictions of $k$BP. Since both copies
of $x^{\prime}$ have the same size, the size of all bins remains the same.

  * •

If $B$ contains no item with size larger than $S/2$, then we do not associate
$B$ with any instance.

##### Partitioning $FFk$ bins into groups.

For the analysis, we partition the bins of each instance $j\in[k]$ in the
$FFk$ packing into five groups.

Group 1. Bins with a single item of instance $j$, whose size is at most $S/2$.
There is at most one such bin. This is because, if there is one such bin $B$
of instance $j$, it means that all later items of instance $j$ do not fit into
$B$, so their size must be greater than $S/2$. Therefore, any later bin
$B^{\prime}$ of instance $j$ must have size larger than $S/2$.

Group 2. Bins with two or more items of instance $j$, whose total size is at
most $2S/3$. There is at most one such bin. This is because, if there is one
such bin $B$ of instance $j$, it means that all later items of instance $j$ do
not fit into $B$, so their size must be greater than $S/3$. Therefore, in any
later bin $B^{\prime}$ with two or more items of instance $j$, their total
size is larger than $2S/3$.

Group 3. Bins with a single item of instance $j$, whose size is larger than
$S/2$.

Group 4. Bins with two or more items of instance $j$, whose total size is at
least $10S/12$.

Group 5. Bins with two or more items of instance $j$, whose total size is in
$(2S/3,10S/12)$.

In the upcoming analysis, we will exclude from each instance, the at most one
bin of group 1, at most one bin of group 2, and at most one bin of group 5.
All in all, we will exclude at most $3k$ bins of the $FFk$ packing from the
analysis.

##### Analysis using the basic weighting scheme.

First we prove that, with the basic weighting scheme, the total weight of each
optimal bin $B$ is at most $17/12$. Since the total size of $B$ is at most
$S$, we have $w(B)\leq 1+r(B)$, so it is sufficient to prove that the reward
$r(B)\leq 5/12$. Indeed:

  * •

If $B$ contains an item larger than $S/2$, then this item gives $B$ a reward
of $4/12$; the remaining room in $B$ is smaller than $S/2$, and the maximum
reward of items that can fit into this space is $1/12$ (for example, one item
of size between $S/3$ and $S/2$).

  * •

If $B$ does not contain an item larger than $S/2$, then the maximum possible
reward is $3/12$ (for example, three items of size $S/3$).

We now prove that, with the basic weighting scheme, the average weight of each
$FFk$ bin is at least $10/12$. In fact, we prove a stronger claim: we prove
that, for each instance $j$, the average weight of the items _of instance $j$
only_ in bins of instance $j$ (ignoring items of instances $j+1,\ldots k$ if
any) is at least $10/12$.

We use the above partition of the bins into 5 groups, excluding at most one
bin of group 1 and at most one bin of group 2.

The bins of group 3 (bins with a single item of instance $j$, which is larger
than $S/2$) have a reward of $4/12$, so their weight is at least
$1/2+4/12=10/12$.

The bins of group 4 (bins with two or more items of instance $j$, which have a
total size larger than $10S/12$) already have weight at least $10/12$,
regardless of their reward.

We now consider the bins of group 5 (bins with two or more items of instance
$j$, which have a total size in $(2S/3,10S/12)$). Denote the bins in group 5
of instance $j$, in the order they are opened, by $B_{1},\ldots,B_{Q}$.
Consider a pair of consecutive bins, e.g. $B_{t},B_{t+1}$. Let $x:=$ the free
space in bin $B_{t}$ during instance $j$. Note that $x\in(S/6,S/3)$. Let
$c_{1},c_{2}$ be some two items of instance $j$ which are packed into
$B_{t+1}$.

For each $c_{i}\in\\{c_{1},c_{2}\\}$, as $FF$ did not pack $c_{i}$ into
$B_{t}$ during the processing of instance $j$, there are two options: either
$c_{i}$ is too large (its size is larger than $x$), or $B_{t}$ already
contains other copies of $c_{i}$ from other instances. But the second option
cannot happen, because $B_{t}$ belongs to instance $j$, so it contains no
items of instances $1,\ldots,j-1$; and while $c_{i}$ of instance $j$ was
processed by $FFk$, items of instance $j+1,\ldots,k$ were not processed yet.
Therefore, necessarily $v(c_{i})>x$.

Since $S/6<x<S/3$, the reward of each of $c_{1},c_{2}$ is at least
$(x/S-1/6)/2$, and the reward of both of them is at least $x/S-1/6$.
Therefore, during instance $j$,

$\displaystyle V(B_{t})/S+r(B_{t+1})\geq(S-x)/S+(x/S-1/6)=1-1/6=10/12.$

In the sequence $B_{1},\ldots,B_{Q}$, there are $Q-1$ consecutive pairs. Using
the above inequality, we get that the total weight of these bins is at least
$10/12\cdot(Q-1)$, which is equivalent to excluding one bin (in addition to
the two bins excluded in groups 1 and 2).

Summing up the weight of all non-excluded bins gives at least
$(10/12)\cdot(FFk(D_{k})-3k)$. Meanwhile, the total weight of optimal bins is
at most $(17/12)\cdot OPT(D_{k})$. This yields $FFk(D_{k})\leq(17/10)\cdot
OPT(D_{k})+3k$, which corresponds to the known asymptotic approximation ratio
of $1.7$ for $k=1$.

We now present an improved approximation ratio for $k>1$. To do this, we give
different weights to items of different instances. We do it in a way that the
average weight of the $FFk$ bins (except the $3k$ excluded bins) will remain
at least $10/12$. Meanwhile, the average weight of the optimal bins in some
$k-1$ instances (as well as the unassociated bins) will decrease to $15/12$,
whereas the average weight of the optimal bins in a single instance will
remain $17/12$. This would lead to an asymptotic ratio of at most
$\frac{1.7+(k-1)\cdot 1.5}{k}=1.5\cdot(1-1/k)+1.7\cdot(1/k)$.

##### Warm-up: $k=2$.

As a warm-up, we analyze the case $k=2$, and prove an asymptotic approximation
ratio of $(1.5/2+1.7/2)=1.6$. We give a detailed proof of the general case of
any $k\geq 1$ in Appendix 0.A.1.

We call a bin in the $FFk$ packing _underfull_ if it has only one item, and
this item is larger than $S/2$ and smaller than $2S/3$. Note that all
underfull bins belong to group 3. We consider two cases.

##### Case 1

: No $FFk$ bin of instance 1 is underfull (in instance 2 there may or may not
be underfull bins). In this case, we modify the weight of items in instance
$1$ only: we reduce the reward of each item with size $V>S/2$ in instance $1$
from $4/12$ to $2/12$.

  * •

In the optimal packing, if $B$ does not contain an item larger than $S/2$,
then its maximum possible reward is still $3/12$ as with the basic weights. If
$B$ contains an item larger than $S/2$, then this item gives $B$ a reward of
$2/12$ if it belongs to instance 1, or $4/12$ if it belongs to instance 2. The
remaining room in $B$ is smaller than $S/2$, and the maximum reward of items
that can fit into this space is $1/12$ (for example, one item of size between
$S/3$ and $S/2$). Overall, the reward of $B$ is at most $5/12$ if it contains
an item item larger than $S/2$ from instance $2$, and at most $3/12$
otherwise. As at most half the bins in the optimal packing contain an item
larger than $S/2$ from instance $2$, at most half these bins have reward
$5/12$, while the remaining bins have reward at most $3/12$, so the average
reward is at most $4/12$. Adding the size of at most $1$ per bin leads to an
average weight of at most $16/12$.

  * •

In the $FFk$ packing, we note that the change in the reward affects only the
bins of group 3 (bins with a single item and $V(B)>S/2$). These bins now have
a reward of at least $2/12$. Since none of them is underfull by assumption,
their weight is at least $2/3+2/12=10/12$. The bins of groups 4 and 5 are not
affected by the reduced reward: the same analysis as above can be used to
deduce that their average weight (except one bin per instance excluded in
group 5) is at least $10/12$.

##### Case 2

: At least one $FFk$ bin of instance 1 is underfull. In this case, we modify
the weight of items in instance $2$ only, as follows (note that we reduce the
_weights_ of these items, and not only their rewards):

$w(V)=\begin{cases}0\quad&\text{if }V/S\leq\frac{1}{3},\\\ 5/12\quad&\text{if
}V/S\in[\frac{1}{3},\frac{1}{2}],\\\ 10/12\quad&\text{if
}V/S>\frac{1}{2}.\end{cases}$

Note that all these weights are not higher than the basic weights of the same
items.

  * •

In the optimal packing, every bin that contains an item larger than $S/2$ from
instance 2 is associated with instance 2, and therefore contains only items of
instance 2 by construction. Therefore, the weight of any such bin is at most
$15/12$ (with one item larger than $S/2$ and one item larger than $S/3$). The
weight of every bin that contains no item larger than $S/2$ is still at most
$15/12$, since its reward is at most $3/12$ as with the basic weights. The
only bins that may have a larger weight (up to $17/12$) are those that contain
an item larger than $S/2$ from instance 1; at most half the bins in the
optimal packing contain such an item. Therefore, the average weight of a bin
in the optimal packing is at most $16/12$.

  * •

In the $FFk$ packing, some bin $B^{1}$ in instance 1 is underfull, that is,
$B^{1}$ contains a single item with size $V\in(S/2,2S/3)$, and the free space
in $B^{1}$ is $S-V\in(S/3,S/2)$. This means that, in the bins of instance 2,
there is no item with size at most $S/3$, since every such item would fit into
$B^{1}$ (it is smaller than the available space in $B^{1}$, and it is not a
copy of the single item in $B^{1}$). So for every bin $B^{2}$ in instance 2
(except the excluded ones), there are only two options:

    * –

$B^{2}$ contains one item larger than $S/2$ — so its weight is $10/12$;

    * –

$B^{2}$ contains two items, each of which is larger than $S/3$ — so its weight
is at least $2\cdot 5/12=10/12$.

The weight of items in instance 1 does not change. So the average weight of
bins in the $FFk$ packing (except the $3k$ excluded bins) remains at least
$10/12$.

In all cases, for $k=2$, we get that the average weight of bins in the optimal
packing is at most $16/12$, and the average weight of non-excluded bins in the
$FFK$ packing is at least $10/12$. Therefore, $FFk-3k\leq(16/10)\cdot
OPT=1.6OPT$. ∎

##### Approximation ratio lower bound.

For $k=1$, the approximation ratio of $1.7$ is tight; an example is given on
page 306 in [12]. In Appendix 0.A.2, we analyze the example for $k>1$, and
show that $FFk$ achieves a ratio of $1.35$. This raises the question of
whether the bound of Theorem 4.1 is tight.

Although we do not have a complete answer for this question, we show below an
example in which $FFk$ attains an approximation ratio of $1.375$, which is
higher than the example of [12].

Consider the example $D=\\{371,659,113,47,485,3,228,419,468,581,626\\}$ and
bin capacity ${S}=1000$. Then, $FFk$ for $k=2$ will result in 11 bins
$[373,113,47,3,228],$ $[659,113,47,3],$ $[485,419],$ $[468,371],$ $[581,228],$
$[626],[659],$ $[485,419],$ $[468],[581],[626]$. The optimal packing for the
items in $D_{2}$ is $[626,371,3],$ $[626,371,3]$, $[659,228,113],$
$[659,228,113],$ $[419,581],$ $[419,581],$ $[468,485,47],$ $[468,485,47]$.
Clearly, $\frac{FFk(D_{2})}{OPT(D_{2})}=\frac{11}{8}=1.375$. Experimental
results in support of this ratio are given in section 7.2. Based on the
example for which we have achieved a ratio of $1.375$ and the simulation of
the algorithm on different datasets, we conjecture that for $k>1$ the
_absolute_ approximation ratio for $FFk$ is $1.375$.

###  4.2 $FFDk$

The $k$-time version of the first-fit decreasing bin packing algorithm first
sorts $D$ in non-increasing order. Then it constructs $D_{k}$ using $k$
consecutive copies of the sorted $D$, and then implements $FFk$ on $D_{k}$. In
contrast to $FFk$, we could not prove an upper bound for $FFDk$ that is better
than the upper bound for $FFD$; we only have a lower bound.

###### Lemma 1

A lower bound for first-fit decreasing is $FFDk(D_{k})\geq\frac{7}{6}\cdot
OPT(D_{k})+1$.

###### Proof

To prove this we use the same example as given in [5] on page 2. The example
is as follows:
$D=\\{\frac{1}{2}+\delta,\frac{1}{2}+\delta,\frac{1}{2}+\delta,\frac{1}{2}+\delta,\frac{1}{4}+2\delta,\frac{1}{4}+2\delta,\frac{1}{4}+2\delta,\frac{1}{4}+2\delta,\frac{1}{4}+\delta,\frac{1}{4}+\delta,\frac{1}{4}+\delta,\frac{1}{4}+\delta,\frac{1}{4}-2\delta,\frac{1}{4}-2\delta,\frac{1}{4}-2\delta,\frac{1}{4}-2\delta,\frac{1}{4}-2\delta,\frac{1}{4}-2\delta,\frac{1}{4}-2\delta,\frac{1}{4}-2\delta\\}$.
Optimal packing for this example contains 4 bins of type
$\\{\frac{1}{2}+\delta,\frac{1}{4}+\delta,\frac{1}{4}-2\delta\\}$ and 2 bins
of type
$\\{\frac{1}{4}+2\delta,\frac{1}{4}+2\delta,\frac{1}{4}-2\delta,\frac{1}{4}-2\delta\\}$.
Clearly, for $D_{k}$ the optimal number of bins are $6k$.

On applying $FFDk$ on $D_{k}$ the resulting number of bins are $8+7(k-1)$.
This gives us a lower bound of $\frac{7}{6}\cdot OPT(D_{k})+1$. . ∎

##### Challenges in extending existing proof:

Existing proofs for the $FFD$ are based on the assumption that the last bin
contains a single item, and no other item(s) are packed after that, i.e. the
smallest item is the only item in the last bin of $FFD$ packing. We can not
say the same in the case of $k$BP when $k>1$. For example let
$D=\\{103,102,101\\}$ and $\mathcal{S}=205$. Then $FFDk$ packing when $k=1$ is
$\\{103,102\\},\\{101\\}$ whereas for $k=2$ the packing is
$\\{103,102\\},\\{101,103\\},\\{102,101\\}$. Hence, the existing proofs for
$FFD$ can not be extended to $FFDk$.

Based on the simulation of $FFDk$ on different datasets, we conjecture that
the upper bound for $FFDk$ is $\frac{11}{9}\cdot OPT(D_{k})+\frac{6}{9}$.
Experimental results in support of this conjecture are provided in section
7.2.

##  5 Polynomial-time Approximation Schemes

###  5.1 Some general concepts and techniques

The basic idea behind generalizing Fernandez de la Vega-Lueker and all the
Karmarkar-Karp algorithms to solve $k$BP is similar. It consists of three
steps: 1\. Keeping aside the small items, 2. Packing the remaining large
items, and 3. Packing the small items in the bins that we get from step 2
(opening a new bin if necessary) to get a solution to the original problem.

In step 3, the main difference from previous work is that, in $k$BP, we cannot
pack two copies of the same small item into the same bin, so we may have to
open a new bin even though there is still remaining room in some bins. The
following lemma analyzes the approximation ratio of this step.

###### Lemma 2

Let $D_{k}$ be an instance of the $k$BP problem, and $\epsilon$ a real number
satisfying $0<\epsilon<1$. Large items are those whose size is $>\epsilon\cdot
S$; otherwise, they are small. Let us assume that the large items can be
packed into $L$ bins. Consider an algorithm which starts adding the small
items into the $L$ bins respecting the constraint of $k$BP; whenever required,
the algorithm opens a new bin. Then, the number of bins required to pack the
items in $D_{k}$ is at most $\max\\{L,(1+2\cdot\epsilon)\cdot
OPT(D_{k})+k\\}$.

###### Proof

Let $I$ be the set of all items $\leq\epsilon\cdot S$, and
$I_{k}=II\ldots\text{ $k$ copies of $I$ }$. Let $bin(D_{k})$ be the number of
bins in the packing of $D_{k}$. If adding small items do not require a new
bin, then $bin(D_{k})=L$. Otherwise, let’s assume that at least $k$ new bins
are opened while packing the items in $I_{k}$. Let $d$ be the first item in
the $k$th new bin. There are at most $k$ bins (including the $k$th new bin)
that contain item $d$; these bins may have a size less than $(1-\epsilon)\cdot
S$. All other bins that do not contain $d$ will have a size of at least
$(1-\epsilon)\cdot S$. The same analysis is true whenever a new bin is opened
while packing the items in $I_{k}$, and it remains true when the algorithm
ends. Therefore,

$\displaystyle\sum{D_{k}[i]}$ $\displaystyle\geq(S-\epsilon\cdot
S)(bins(D_{k})-k)$ $\displaystyle\sum{D_{k}[i]}$ $\displaystyle\leq
OPT(D_{k})\cdot S$ $\displaystyle bins(D_{k})$
$\displaystyle\leq\frac{1}{1-\epsilon}\cdot OPT(D_{k})+k$ $\displaystyle
bins(D_{k})$ $\displaystyle\leq(1+2\cdot\epsilon)\cdot OPT(D_{k})+k$ (1)

Therefore,

$bin(D_{k})\leq\max\\{L,(1+2\cdot\epsilon)\cdot OPT(D_{k})+k\\}$ (2)

∎

Step 2 is done using a linear program based on _configurations_.

###### Definition 1

A _configuration_ (or a _bin type_) is a collection of item sizes which sums
to, at most, the bin capacity $S$.

For example [25]: suppose there are $7$ items of size $3$, $6$ items of size
$4$, and $S=12$. Then, the possible configurations are
$[3,3,3,3],[3,3,3],[3,3],[3],$ $[4,4,4],[4,4],[4],$ $[3,3,4],[3,4,4],[3,4]$.

Let $t$ be the number of different configurations. $A$ is a $m(D)\times t$
matrix, where row $i$ denotes the number of items of type $c[i]$ in
configuration $j$. $\mathbf{n}$ is a vector whose each element, $n[i]$,
denotes the count of items of size $c[i]$. Let $\mathbf{x}$ is a vector of
size $t$ whose each element, $x[i]$ denotes the number of bins of bin type
$i$, and 1 is a vector of 1. The fractional bin-packing problem $F$ is the
following linear program : $\min\quad\mathbf{1\cdot x}$ $\text{such that}\quad
A\mathbf{x}\geq\mathbf{n}$ $\mathbf{x}\geq 0$.

Let $LIN(D)$ denote the value of the fractional bin-packing problem $F$
associated with instance $D$.

Recall that in $k$BP, each item $D[i]\in D$ has to appear in $k$ distinct
bins. _One can observe that $k$BP uses the same configurations as in bin-
packing when $k=1$ to ensure that each bin should contain at most one copy of
an item._ Therefore, the configuration linear program $C_{k}$ for $k$BP is as
follows (for $k=1$ it is the same as in [23]):

$\displaystyle\min\quad\mathbf{1\cdot x}$ (3) $\displaystyle\text{such
that}\quad A\mathbf{x}$ $\displaystyle\geq k\mathbf{n}$ (4)
$\displaystyle\mathbf{x}$ $\displaystyle\geq 0$ (5)

$A$, $\mathbf{n}$, and $\mathbf{x}$ are same as in fractional bin packing $F$
above.

Let $F_{k}$ be the fractional bin packing problem corresponding to $C_{k}$.
Step $2$ involves grouping. Grouping reduces the number of different item
sizes, and thus reduces the number of constraints and configurations in the
fractional linear program $F_{k}$.

To solve the configuration LP efficiently, both Fernandez de la Vega-Lueker
algorithm and Algorithm 1 of Karmarkar Karp use a _linear grouping_ technique.
In linear grouping, items are divided into groups (of fixed cardinality,
except possibly the last group), and each item size (in each group) increases
to the maximum item size in that group.

##### Linear Grouping:

Let $K$ be some instance and $g>1$ be some integer parameter. Order the items
in $K$ in non-increasing order. Let $U$ be the instance obtained by making
groups of the items in $K$ of cardinality $g$ and then rounding up the items
in each group by the maximum item size in that group. Let $U^{\prime}$ be the
group of the $g$ largest items and $U^{\prime\prime}$ be the instance
consisting of groups from the second to last group in $U$. Then,
$OPT(U^{\prime\prime})\leq OPT(K)$ [14]
$OPT(U^{\prime})\leq g$, because each item in $U^{\prime}$ can pack into a
single bin.
$OPT(K)\leq OPT(U^{\prime\prime}\cup U^{\prime})\leq
OPT(U^{\prime\prime})+OPT(U^{\prime})\leq OPT(U^{\prime\prime})+g$
It implies the below Lemma 3 due to [14]

###### Lemma 3

$\displaystyle OPT(U^{\prime\prime})\leq OPT(K)\leq OPT(U^{\prime\prime})+g$
$\displaystyle LIN(U^{\prime\prime})\leq LIN(K)\leq LIN(U^{\prime\prime})+g$
$\displaystyle V(U^{\prime\prime})\leq V(K)\leq V(U^{\prime\prime})+g$

If the items in $K$ are arranged in non-decreasing order, then
$U^{\prime\prime}$ will be the instance consisting of groups from first to the
second from the last group, and $U^{\prime}$ be the last group consisting of
the $\leq g$ large items. The above same results hold in this case as well.

Our extension of Fernandez de la Vega-Lueker and Karmarkar-Karp algorithms to
$k$BP differs from their original counterpart in mainly two directions: First,
in configuration linear program (see the constraint 4 in $C_{k}$), and hence
the obtained solution to this configuration LP is not necessarily the $k$
times copy of the original solution (to BP); Second, in greedily adding the
small items (see lemma 2 ). In extension of Karmarkar-Karp algorithm 1 to
$k$BP we have also shown that getting an integer solution from $\mathbf{x}$ by
rounding method may require at most $(k-1)/2$ additional bins. We discuss
extensions to the Fernandez de la Vega-Lueker and Karmarkar-Karp algorithms
and their analysis in 5.2 and 5.3, respectively.

The inputs to the extension of the algorithms by Fernandez de la Vega-Lueker
and Algorithm 1 and Algorithm 2 of Karmarkar-Karp are $D$: the input set of
items, $k$: an integer, and $\epsilon>0$: a real parameter. Algorithm 2 of
Karmarkar-Karp, in addition, accepts an integer parameter $g>0$.

###  5.2 Fernandez de la Vega-Lueker algorithm to $k$BP

Fernandez de la Vega and Lueker [23] published a PTAS which, given an input
instance $D$ and $\epsilon>0$, solves bin packing with, at most,
$(1+\epsilon)\cdot OPT(D)+1$ bins. They devised a method called “adaptive
rounding” for this algorithm. In this method, the given items are put into
groups and rounded to the largest item size in that group. This resulting
instance will have fewer different item-sizes. This resulting instance can be
solved efficiently using a configuration linear program $C_{k}$.

This integer program can be solved as follows:

Using exhaustive search: Since there are $n(D)$ items, a configuration can
repeat at most $n(D)$ times. Therefore, $(x_{t})_{t\in
T}\in\\{0,1,\ldots,n(D)\\}^{\lvert T\rvert}$. Each configuration can contain,
at most, $1/\epsilon$ items, and there are $m(D)$ different item sizes.
Therefore, the number of possible configurations can, at most, be
$m(D)^{1/\epsilon}$. Now, we can check if enough slots are available for each
size $c[i]$. Finally, output the solution with the minimum number of bins.
Running time then is $m(D)\times n(D)^{m(D)^{1/\epsilon}}$, which is
polynomial in $n(D)$ when $m(D),\epsilon$ are fixed.

##### A high-level description of the extension of Fernandez de la Vega-Lueker
algorithm to $k$BP:

Let $I$ and $J$ be multisets of small and large items in $D$, respectively.
After applying linear grouping in $J$, let $U$ be the resulting instance and
$C_{k}$ be the corresponding configuration linear program. An optimal solution
to $C_{k}$ will give us an optimal solution to the corresponding $k$BP
instance $U_{k}$. Ungrouping the items in $U_{k}$ will give us a solution to
$k$BP instance $J_{k}$. Finally, adding the items in $I_{k}$, by respecting
the constraints of $k$BP , to the solution of $J_{k}$ will give us a packing
of $D_{k}$.

The extension of the algorithm by Fernandez de la Vega-Lueker to $k$BP is
given in appendix 0.B.

###### Lemma 4

Let $OPT(U_{k})$ denote the optimal number of bins in solving $C_{k}$. Then,
$OPT(U_{k})<(1+\epsilon)\cdot OPT(J_{k})$.

###### Corollary 1

$bins(J_{k})\leq(1+\epsilon)\cdot OPT(J_{k})$.

###### Theorem 5.1

Generalizing the Fernandez de la Vega-Lueker algorithm to $k$BP will require
bins: $bins(D_{k})\leq(1+2\cdot\epsilon)\cdot OPT(D_{k})+k$.

We give a detailed proof of the above lemma 4, corollary 1, and theorem 5.1,
along with the run time analysis of the Fernandez de la Vega-Lueker algorithm
to $k$BP in appendix 0.B.

###  5.3 Karmarkar-Karp Algorithms to $k$BP

Karmarkar and Karp [14] improved the work done by Fernandez de la Vega and
Lueker [23] mainly in two directions: 1. Solving the linear programming
relaxation of $C$ (note that $C=C_{k}$ when $k=1$) using a variant of the GLS
method [10], and 2. using a different grouping technique. These improvements
led to the development of three algorithms. Their algorithm 3 is a particular
case of algorithm 2; we will discuss the generalization of algorithms 1 and 2
of Karmarkar-Karp algorithms to solve $k$BP. Let $LIN(F_{k})$ denote the
optimal solution to the fractional linear program $F_{k}$ for $k$BP. We will
discuss helpful results relevant to analyzing the generalized version of their
algorithms. These results are an extension of the results in [14]. Lemma 5
bounds from above the bins needed to pack the items in an optimal packing of
some instance $D_{k}$. Lemma 6 talks about obtaining an integer solution from
a basic feasible solution of the fractional linear program.

###### Lemma 5

$OPT(D_{k})\leq 2\cdot V(D_{k})/S+k$

###### Lemma 6

$V(D_{k})\leq S\cdot LIN(D_{k})\leq S\cdot OPT(D_{k})\leq S\cdot
LIN(D_{k})+\frac{S\cdot(m(D_{k})+k)}{2}$

We give the complete proof of the lemma 5 and 6 at the start of Appendix 0.C.

###### Corollary 2

There is an algorithm A that solves the $k$BP by solving the corresponding
fractional bin-packing problem $F_{k}$. It produces bins no more than
$\mathbf{1\cdot x}+\frac{m(D_{k})+k}{2}$, where $\mathbf{x}$ is the optimal
solution of $F_{k}$.

Note that $m(D_{k})=m(D)=$ the number of different item sizes in the instance.

Before moving further, we would like to mention that if we use some instance
(or group) without subscript $k$, we are talking about the instance when
$k=1$.

All Karmarkar-Karp algorithms use a variant of the ellipsoid method to solve
the fractional linear program. So, we will talk about adapting this method to
$k$BP.

##### Solving the fractional linear program:

Solving the fractional linear program $F_{k}$ involves a variable for each
configuration.This results in a large number of variables. The dual, $D_{F}$,
of the fractional linear program, is:

$\displaystyle\max\quad k\cdot\mathbf{n\cdot y}$ (6) $\displaystyle\text{such
that}\quad A^{T}\mathbf{y}$ $\displaystyle\leq\mathbf{1}$ (7)
$\displaystyle\mathbf{y}$ $\displaystyle\geq 0$ (8)

The above dual LP can be solved to any given tolerance $h$ by using a variant
of the ellipsoid method that uses an approximate separation oracle [14]. The
running time of the algorithm is
$T(m(D_{k}),n(D_{k}))=O(m(D)^{8}\cdot{\ln{m(D)}}\cdot{\ln^{2}(\frac{m(D)\cdot
n(D)}{\epsilon\cdot S\cdot h})}+\frac{m(D)^{4}\cdot k\cdot
n(D)\cdot\ln{m(D)}}{h}\ln{\frac{m(D)\cdot n(D)}{\epsilon\cdot S\cdot h}})$. We
give a description of this variant of the ellipsoid method and its running
time in Appendix 0.C.1

##### A high-level description of the extensions of the Karmarkar-Karp
algorithms:

We will give a high-level description behind the extension of Karmarkar-Karp
algorithms to solve $k$BP: Let $I$ and $J$ be multisets of small and large
items in $D$, respectively. Let $U^{\prime\prime}$ be the instance constructed
from $J$ by applying the grouping technique. Construct the configuration
linear program $C_{k}$ for $U^{\prime\prime}_{k}$ and solve the corresponding
fractional linear program $F_{k}$. Let $\mathbf{x}$ be the resulting solution.
From $\mathbf{x}$, obtain an integral solution for $U^{\prime\prime}_{k}$.
From this solution, get a solution for $J_{k}$ by ungrouping the items. Add
the items in $I_{k}$ by respecting the constraints of $k$BP to get a solution
for $D_{k}$.

####  5.3.1 Karmarkar-Karp Algorithm 1 extension to $k$BP:

Algorithm 1 of the Karmarkar-Karp algorithms uses the linear grouping
technique as illustrated in subsection 5.1. We give the extension of the
Karmarkar-Karp Algorithm 1 to $k$BP in Appendix 0.C.2

###### Theorem 5.2

Let $bin(D_{k})$ denote the cost of the bin-packing produced by Karmarkar-Karp
Algorithm 1 extension to $k$BP. Then, $bin(D_{k})\leq(1+2\cdot
k\cdot\epsilon)OPT(D_{k})+\frac{1}{2\cdot\epsilon^{2}}+(2\cdot k+1)$.

We give the complete proof of the above theorem and the running time of the
Karmarkar-Karp Algorithm 1 extension to $k$BP in Appendix 0.C.2.

####  5.3.2 Karmarkar-Karp Algorithm 2 extension to $k$BP:

Algorithm 2 of the Karmarkar-Karp algorithms uses the alternative geometric
grouping technique: Let $J$ be some instance and $g>1$ be some integer
parameter, then, alternative geometric grouping partitions the items in $J$
into groups such that each group contains the necessary number of items so
that the size of each group (i.e. the sum of item sizes in that group) is at
least $g\cdot S$. See appendix 0.C.3 for more details.

###### Theorem 5.3

Let $bin(D_{k})$ denote the cost of the bin-packing produced by Karmarkar-Karp
Algorithm 2 extension to $k$BP. Then, $bin(D_{k})\leq
OPT(D_{k})+O(k\cdot\log^{2}{OPT(D)})$

We give the complete proof of the above theorem and the running time of the
Karmarkar-Karp Algorithm 2 extension to $k$BP in Appendix 0.C.3.

##  6 Experiment 1: $FFk$ and $FFDk$ for fair electricity distribution

In this section, we describe an experiment checking the performance of the
$k$BP adaptations of $FFk$ and $FFDk$ to our motivating application of fair
electricity distribution.

###  6.1 Dataset

We use the same dataset of $367$ Nigerian households described in [20].111 We
are grateful to Olabambo Oluwasuji for sharing the dataset with us.  This
dataset contains the hourly electricity demand for each household for 13 weeks
(2184 hours). In addition, they estimate for each agent and hour, the
_comfort_ of that agent, which is an estimation of the utility the agent gets
from being connected to electricity at that hour. For more details about the
dataset, readers are encouraged to refer to the papers [19, 20]. The
electricity demand of agents can vary from hour to hour. We execute our
algorithms for each hour separately, which gives us essentially 2184 different
instances.

As in [20], we use the demand figures in the dataset as mean values; we
determine the actual demand of each agent at random from a normal distribution
with a standard deviation of $0.05$ (results with a higher standard deviation
are presented in Appendix 0.D).

As in [20], we compute the supply capacity $S$ for each day by averaging the
hourly estimates of the agents’ demand for that day. We run nine independent
simulations (with different randomization of the agents’ demands). Thus, the
supply changes in accordance with the average daily demand, but cannot satisfy
the maximum hourly demand.

###  6.2 Experiment

For each hour, we execute the $FFk$ and $FFDk$ algorithms on the households’
demands for that hour. We then use the resulting packing to allocate
electricity: if the packing returns $q$ bins, then each bin is connected for
$1/q$ of an hour, which means that each agent is connected for $k/q$ of an
hour.

The authors of [20] measure the efficiency and fairness of the resulting
allocation, not only by the total time each agent is connected, but also by
more complex measures. In particular, they assume that each agent $i$ has a
utility function, denoted $u_{i}$, that determines the utility that the agent
receives from being connected to electricity at a given hour. They consider
three different utility models:

  1. 1.

The simplest model is that $u_{i}$ equals the amount of time agent $i$ is
connected to electricity (this is the model we mentioned in the introduction).

  2. 2.

$u_{i}$ can also equal the total amount of electricity that agent $i$
receives. For each hour, the amount of electricity given to $i$ is the amount
of time $i$ is connected, times $i$’s demand at that hour.

  3. 3.

They also measure the “comfort” of agent $i$ in time $t$ by averaging their
demand over the same hour in the past four weeks, and normalizing it by
dividing by the maximum value.

For each utility model, they consider three metrics of efficiency and
fairness:

  * •

Utilitarian: the sum (or the average) of all agents’ utilities:
$\sum_{i}u_{i}(x).$

  * •

Egalitarian: the minimum utility of a single agent: $\min_{i}u_{i}(x).$

  * •

The maximum difference of utilities between each pair of agents:
$\max_{i,j}\\{\lvert u_{i}(x)-u_{j}(x)\rvert\\}.$

###  6.3 Results

For comparison with their results, we show our results for $FFk$ and $FFDk$
for $k=9$ along with the results in [20] in table 1,2, and 3 . We highlight
the best results in bold. As can be seen in Tables 1, 2 and 3, $FFk$ and
$FFDk$ outperform the previous results for all 9 combinations of utility
models and social welfare metrics, even though they were only designed for the
egalitarian welfare of the time-based utility function. In Appendix 0.D, we
have graphs that show how various values of $k$ and varying levels of
uncertainty affect the number of connection hours, amount of electricity
delivered, and comfort.

Table 1: Comparing results of $FFk$ and $FFDk$ for $k=9$ with the results in [20] in terms of hours of connection to supply on the average, along with their standard deviation (SD) within parenthesis. In the third column, we have shown the average number of hours an agent is connected to the supply.  Algorithm |  Utilitarian:sum(SD) | Utilitarian:average | Egalitarian(SD) | Maximum Utility Difference
---|---|---|---|---
$FFk$ |  723982.0121(401.4496) | 1972.7030 | 1972.7030(1.0939) | 0.0(0.0)
$FFDk$ |  723804.0727(654.8798) | 1972.2182 | 1972.2182(1.7844) | 0.0(0.0)
CM |  717031(3950) | 1953.7629 | 1920(3.24) | 123(2.09)
SM |  709676(3878) | 1933.7221 | 1922(3.41) | 71(2.04)
GA |  629534(4178) | 1715.3515 | 1609(4.69) | 695(3.28)
CSA1 |  647439(3063) | 1764.1389 | 1764(2.27) | 1(0.00)
RSA |  643504(4094) | 1753.4169 | 1753(4.33) | 1(0.00)
CSA2 |  641002(3154) | 1746.5995 | 1746(2.38) | 1(0.00)
Table 2: Comparing results of $FFk$ and $FFDk$ for $k=9$ with the results in [20] in terms of electricity supplied on the average, along with their standard deviation (SD) within parenthesis Algorithm |  Utilitarian(SD) | Egalitarian(SD) | Maximum Utility Difference
---|---|---|---
$FFk$ |  1444617.5746(793.4190) | 0.8957(0.0005) | 0.0179(0.0008)
$FFDk$ |  1444242.4530(1333.086) | 0.8954(0.0009) | 0.01771(0.0010)
CM |  1340015(8299) | 0.78(0.01) | 0.17(0.02)
SM |  1347801(8304) | 0.83(0.01) | 0.11(0.02)
GA |  1297020(11264) | 0.35(0.04) | 0.58(0.03)
CSA1 |  1296939(7564) | 0.66(0.02) | 0.28(0.02)
RSA |  1344945(11284) | 0.68(0.03) | 0.25(0.03)
CSA2 |  1345537(7388) | 0.63(0.03) | 0.30(0.02)
Table 3: Comparing results of $FFk$ and $FFDk$ for $k=9$ with the results in [20] in terms of comfort delivered on the average, along with their standard deviation (SD) within parenthesis Algorithm |  Utilitarian(SD) | Egalitarian(SD) | Maximum Utility Difference
---|---|---|---
$FFk$ |  314035.2667(171.7323) | 0.8975(0.0005) | 0.0109(0.0004)
$FFDk$ |  313967.0364(268.3526) | 0.8974(0.0007) | 0.0108(0.0004)
CM |  303217(3447) | 0.81(0.01) | 0.13(0.02)
SM |  292135(3802) | 0.83(0.01) | 0.09(0.02)
GA |  291021(5198) | 0.38(0.04) | 0.56(0.03)
CSA1 |  291909(3201) | 0.67(0.02) | 0.25(0.02)
RSA |  268564(5106) | 0.65(0.04) | 0.28(0.03)
CSA2 |  270262(3112) | 0.64(0.02) | 0.28(0.02)

In Appendix 0.D, we discuss the variation in utilitarian, egalitarian, and
maximum-utility difference with different values of $k$ and varying levels of
uncertainty (standard deviation). The graphs show that the changes appear to
saturate as $k$ increases.

##  7 Experiment 2: approximation ratio of $FFk$ and $FFDk$ algorithms

In this section we describe a second experiment, for checking the
approximation ratio of FFk and FFDk with respect to the optimal bin packing.

###  7.1 Data generation

Since computing the optimal bin packing of a given instance is NP-hard, we
constructed instances whose optimal bin packing is known. Given the bin
capacity $S$, we use Algorithm 1 is used to generate a list of items which sum
to the bin capacity $S$. Algorithm 2 uses Algorithm 1 to generate an instance
whose items sum to $OPT$ times $S$, and by the construction, we know that the
optimal bin packing for the instance $D$ has exactly $OPT$ bins, and moreover,
the optimal bin packing for $D_{k}$ has exactly $k\cdot OPT$ bins (all of them
full).

Input: ${S}$: bin capacity

Output: Returns a list, $L$, of items that sum to $S$.

1

2Let $L$ be the list of the randomly generated items. Initially empty.

3 Let $s_{L}$ the sum of all the items in the list. Initially 0.

4

5while  _True_ do

6 generate a random number in range $(1,S)$. Let $r$ be this random number.

7 if  _$s_{L}+r >S$_ then

8 Append $S-s_{L}$ to $L$.

9 break

10 else

11 Append $r$ to $L$, and update $s_{L}$.

12 end if

13

14 end while

15return $L$

Algorithm 1 generate_items

Our generated dataset contains multiple files. Each file in the dataset
contains a fixed number ${IC}$ of instances. Each instance has several items.
These items have an optimal packing of ${OPT}$ bins. Each bin has capacity
$S$. For example let $[1,2,3,7,6,1^{\prime}]$ be an instance in some file
where for each instance in the file ${OPT}=2$. Bin capacity is $S=10$. As we
can see, there are two groups $\\{7,2,1\\},\\{6,3,1^{\prime}\\}$ which sum to
10 and hence an optimal packing requires two bins to pack the items in this
instance.

Input: ${S}$: bin capacity; ${OPT}$: the optimal number of bins to pack items
in this instance.

Output: A list, $D$, of items which sum to ${OPT}\cdot{S}$, such that the
optimal number of bins is indeed $OPT(D)=OPT$.

1

2Let $D$ be the instance. Initially empty.

3 Let $s_{D}$ be the sum of all the items in $D$. Initially 0.

4 while  _True_ do

5 $L=$ generate_items($S$)

6 $s_{D}=s_{D}+s_{L}$.

7 if  _$s_{D}/S=={OPT}$_ then

8 Append items in $L$ to $D$.

9 Shuffle items in $D$.

10 break

11 else

12 Append items in $L$ to $D$.

13 end if

14

15 end while

16return $D$

17

Algorithm 2 generate_instance_items

###  7.2 Results

We ran our experiment for different values of $k>1$, and for different values
of $OPT\in\\{2,3,4,5,6,7,8,9\\}$. We compute the conjectured upper bound on
the number of bins required to pack items using $FFk$(for $k>1$) and $FFDk$ as
$1.375\cdot OPT(D_{k})$ and $\frac{11\cdot OPT(D_{k})+6}{9}$, respectively.
For each file we report the maximum number of bins required to pack items. We
can see in Figures 1, and 2 that the bins used by $FFk$(for $k>1$) and $FFDk$
are $\leq 1.375\cdot OPT(D_{k})$ and $\leq\frac{11\cdot OPT(D_{k})+6}{9}$,
respectively, which supports our conjecture in subsection 4.1 and 4.2.

Figure 1:  The x axis is $OPT(D_{k})$, which in our generated instances is
equal to $k\cdot OPT(D)$. The y axis shows the number of bins in the packing
generated by $FFk$ and $FFDk$ algorithms. The data points in the legend show
the upper bound that can be hypothesized for $OPT(D_{k})=k\cdot OPT(D)$;
different points on the same column correspond to random instances (some
points correspond to several different instances).

Figure 2: The output bins from $FFk$ and $FFDk$ algorithms are shown on the
$y$-axis. The $OPT(D_{k})$ bins are shown in the $x$-axis. The data points in
the legend show the upper bound that can be hypothesized for
$OPT(D_{k})=k\cdot OPT(D)$. Each subplot’s data points display the number of
different output bins corresponding to each conjectured upper bound. Note that
the output bins convey the conjectured upper bound at most.

##  8 Conclusion and Future Directions

We have shown that the existing approximation algorithms, like first-fit and
first-fit decreasing, can be extended to solve $k$BP. We have proved that, for
any $k\geq 1$, the asymptotic approximation ratio for the $FFk$ algorithm is
$(\frac{1}{k}\cdot 1.7+\left(1-\frac{1}{k}\right)\cdot 1.5)\cdot
OPT(D_{k})+3\cdot k$. We have also demonstrated that the generalization of
efficient approximation algorithms like Fernandez de la Vega-Lueker and
Karmarkar Karp algorithms solves $k$BP in $(1+2\cdot\epsilon)\cdot
OPT(D_{k})+k$ and $OPT(D_{k})+O(k\cdot\log^{2}{OPT(D)})$ bins respectively in
polynomial time. We have also shown the practical efficacy of $FFk$ and $FFDk$
in solving the fair electricity distribution problem.

Given the usefulness of $k$-times bin-packing to electricity division, an
interesting open question is how to determine the optimal value of $k$ — the
$k$ that maximizes the fraction of time each agent is connected — the fraction
$\frac{k}{bins(D_{k})}$. Note that this ratio is not necessarily increasing
with $k$. For example, consider the demand vector $D=\\{11,12,13\\}$:

  * •

For $k=1$, any agent is connected $\frac{1}{2}$ of the time.

  * •

For $k=2$, any agent connects $\frac{2}{3}$ of the time.

  * •

For $k=3$, any agent connects only $\frac{3}{5}$ of the time, which is worse
than $\frac{2}{3}$.

Therefore, a natural question arises: what is the smallest value of $k$ that
results in the optimal $\frac{k}{bins(D_{k})}$ ratio?

Some other questions left open are

  1. 1.

To bridge the gap in the approximation ratio of $FFk$, between the lower bound
$1.375$ and the upper bound $(\frac{1}{k}\cdot
1.7+\left(1-\frac{1}{k}\right)\cdot 1.5)\cdot OPT(D_{k})+3\cdot k$, which
converges to 1.5.

  2. 2.

To prove or disprove that the conjectured bound $\frac{11}{9}OPT+\frac{6}{9}$
is tight for $FFDk$.

## References

  * [1] Baker, B.S.: A new proof for the first-fit decreasing bin-packing algorithm. Journal of Algorithms 6(1), 49–70 (Mar 1985). https://doi.org/10.1016/0196-6774(85)90018-5, https://linkinghub.elsevier.com/retrieve/pii/0196677485900185
  * [2] Brams, S.J., Taylor, A.D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press (1996). https://doi.org/10.1017/CBO9780511598975
  * [3] Doron-Arad, I., Kulik, A., Shachnai, H.: Bin packing with partition matroid can be approximated within $o(opt)$ bins (arXiv:2212.01025) (Dec 2022), http://arxiv.org/abs/2212.01025, arXiv:2212.01025 [cs]
  * [4] Dsa, G., Sgall, J.: First Fit bin packing: A tight analysis. Leibniz International Proceedings in Informatics, LIPIcs 20, 538–549 (2013). https://doi.org/10.4230/LIPIcs.STACS.2013.538, iSBN: 9783939897507
  * [5] Dósa, G.: The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is F F D ( I ) $\leq$ 11 / 9 OP T ( I ) + 6 / 9 2007(2), 1–11 (2007)
  * [6] Dósa, G., Li, R., Han, X., Tuza, Z.: Tight absolute bound for First Fit Decreasing bin-packing: FFD (L) $\leq$ 11/9 OPT (L) + 6/9. Theoretical Computer Science 510(11101065), 13–61 (2013). https://doi.org/10.1016/j.tcs.2013.09.007
  * [7] Garey, M.R., Graham, R.L., Ullman, J.D.: the ratios AFF / A *, ABF / A *, AFFD / A *, and ABFD / A *. pp. 143–150 (1972)
  * [8] Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. A series of books in the mathematical sciences, Freeman, New York [u.a], 27. print edn. (2009)
  * [9] Garey, M., Graham, R., Johnson, D., Yao, A.C.C.: Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A 21(3), 257–298 (1976). https://doi.org/https://doi.org/10.1016/0097-3165(76)90001-7, https://www.sciencedirect.com/science/article/pii/0097316576900017
  * [10] Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197 (Jun 1981). https://doi.org/10.1007/BF02579273, http://link.springer.com/10.1007/BF02579273
  * [11] Hoberg, R., Rothvoss, T.: A logarithmic additive integrality gap for bin packing. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 2616–2625. Society for Industrial and Applied Mathematics (Jan 2017). https://doi.org/10.1137/1.9781611974782.172, http://epubs.siam.org/doi/10.1137/1.9781611974782.172
  * [12] Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SIAM Journal on Computing 3(4), 299–325 (1974). https://doi.org/10.1137/0203025
  * [13] Johnson, D.S.: Near-Optimal Bin Packing Algorithms. Thesis p. 400 (1973)
  * [14] Karmarkar, N., Karp, R.M.: Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem. Annual Symposium on Foundations of Computer Science - Proceedings pp. 312–320 (1982). https://doi.org/10.1109/sfcs.1982.61
  * [15] Kaygusuz, K.: Energy for sustainable development: A case of developing countries. Renewable and Sustainable Energy Reviews 16(2), 1116–1126 (2012). https://doi.org/10.1016/j.rser.2011.11.013, http://dx.doi.org/10.1016/j.rser.2011.11.013, publisher: Elsevier Ltd
  * [16] Laboratory, P.U.D.o.E.E.C.S., Ullman, J.: The Performance of a Memory Allocation Algorithm. Technical report (Princeton University. Dept. of Electrical Engineering. Computer Sciences Laboratory), Princeton University (1971), https://books.google.co.il/books?id=gnwNPwAACAAJ
  * [17] Li, R., Yue, M.: The proof of ffd(l) ¡ -opt(l) + 7/9. Chinese Science Bulletin 42(15), 1262–1265 (Aug 1997). https://doi.org/10.1007/BF02882754
  * [18] Minyi, Y.: For the ffd bin-packing algorithm*. ACTA MATHEMATICAE APPLICATAE SINICA (1992)
  * [19] Oluwasuji, O.I., Malik, O., Zhang, J., Ramchurn, S.D.: Algorithms for Fair Load Shedding in Developing Countries. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. pp. 1590–1596. International Joint Conferences on Artificial Intelligence Organization, Stockholm, Sweden (Jul 2018). https://doi.org/10.24963/ijcai.2018/220, https://www.ijcai.org/proceedings/2018/220
  * [20] Oluwasuji, O.I., Malik, O., Zhang, J., Ramchurn, S.D.: Solving the fair electric load shedding problem in developing countries. Auton Agent Multi-Agent Syst 34(1), 12 (Apr 2020). https://doi.org/10.1007/s10458-019-09428-8, http://link.springer.com/10.1007/s10458-019-09428-8
  * [21] Rothvoss, T.: Approximating bin packing within o(log opt · log log opt) bins. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. p. 20–29. IEEE, Berkeley, CA, USA (Oct 2013). https://doi.org/10.1109/FOCS.2013.11, https://ieeexplore.ieee.org/document/6686137/
  * [22] Society, T.E.: Sur la division pragmatique Author ( s ): H . Steinhaus Source : Econometrica , Vol . 17 , Supplement : Report of the Washington Meeting ( Jul ., 1949 ), Published by : The Econometric Society Stable URL : http://www.jstor.org/stable/1907319 Accessed : 26 17, 315–319 (2016)
  * [23] Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1 + $\epsilon$ in linear time. Combinatorica 1(4), 349–355 (1981). https://doi.org/10.1007/BF02579456
  * [24] Webb, Jack Robertson, W.: Cake-Cutting Algorithms: Be Fair if You Can. A K Peters/CRC Press, New York (Jul 1998). https://doi.org/10.1201/9781439863855
  * [25] Wikipedia contributors: Configuration linear program — Wikipedia, the free encyclopedia (2023), https://en.wikipedia.org/w/index.php?title=Configuration˙linear˙program&oldid=1139054649, [Online; accessed 16-March-2023]
  * [26] Xia, B., Tan, Z.: Tighter bounds of the First Fit algorithm for the bin-packing problem. Discrete Applied Mathematics 158(15), 1668–1675 (2010). https://doi.org/10.1016/j.dam.2010.05.026, http://dx.doi.org/10.1016/j.dam.2010.05.026, publisher: Elsevier B.V.

##  Appendix 0.A $FFk$ Algorithm

###  0.A.1 Asymptotic approximation ratio

In this section we will give the proof of theorem 4.1 for the general case.
Recall that we have already given the proof for $k=2$ as a warm up case in
section 4.1.

######  Proof (of theorem 4.1 )

Recall that we have a basic weighting scheme, in which each item is given a
weight according to the following formula: The weight of any item with size
$V$ is defined as

$\displaystyle w(V):=V/S+r(V),$

where $r$ is a _reward function_ , computed as follows:

$r(V):=\begin{cases}0\quad&\text{if }V/S\leq\frac{1}{6},\\\
\frac{1}{2}(V/S-\frac{1}{6})\quad&\text{if
}V/S\in(\frac{1}{6},\frac{1}{3}),\\\ 1/12\quad&\text{if
}V/S\in[\frac{1}{3},\frac{1}{2}],\\\ 4/12\quad&\text{if
}V/S>\frac{1}{2}.\end{cases}$

We modify this scheme later for some items, based on the instances to which
they belong.

Denote by $u$, the first instance in the $FFk$ packing in which there are
underfull bins (if there are no underfull bins at all, we set $u=k$). We
modify the item weights as follows:

  * •

For instances $1,\ldots,u-1$, we reduce the reward of each item with size
$V>S/2$ from $4/12$ to $2/12$.

  * •

For instance $u$, we keep the weights unchanged.

  * •

For instances $u+1,\ldots,k$, we reduce the weights of items as follows (Note
that it is the same reduction in weight as in case 2 of warm-up case for $k=2$
in the proof of theorem 4.1):

$w(V)=\begin{cases}0\quad&\text{if }V/S\leq\frac{1}{3},\\\ 5/12\quad&\text{if
}V/S\in[\frac{1}{3},\frac{1}{2}],\\\ 10/12\quad&\text{if
}V/S>\frac{1}{2}.\end{cases}$

We now analyze the effects of these changes.

  * •

In the optimal packing, the maximum reward of every bin that contains an item
larger than $S/2$ from instances $1,\ldots,u-1$ drops from at most $5/12$ to
at most $3/12$, so their weight is at most $15/12$. Additionally, every bin
that contains an item larger than $S/2$ from some instance
$j\in\\{u+1,\ldots,k\\}$, contains only items from instance $j$. Therefore,
its weight can be at most $15/12$ (e.g. one item larger than $S/2$ and one
item larger than $S/3$). Additionally, the weight of every bin that contains
no items larger than $S/2$ remains at most $15/12$. The only bins that can
have a larger weight (up to $17/12$) are bins with items larger than $S/2$
from instance $u$. At most $1/k$ bins in the optimal packing can contain such
an item. Therefore, the average weight of a bin in the optimal packing is at
most $\frac{(17/12)+(15/12)\cdot(k-1)}{k}$.

  * •

In the $FFk$ packing, instances $1,\ldots,u-1$ have no underfull bins. The
change in the reward affects only the bins of group 3 (bins with a single item
larger than $S/2$): the weight of each bin in group 3 (which must have one
item larger than $2S/3$ since it is not underfull) is at least
$2/3+2/12=10/12$. Since we only reduce the reward of the item larger than
$S/2$ for the instances $1,\ldots,u-1$; the analysis of bins in groups 4 and 5
is not affected at all by this reduction in reward and therefore leads to
their average weight (except excluding one bin per instance in groups 1, 2,
and 5) of at least $10/12$.

In instance $u$, the weights are unchanged, so the average bin weight (except
excluding one bin per instance in groups 1, 2, and 5) is still at least
$10/12$.

Finally, the bins of instances $u+1,\ldots,k$ contain no item of size at most
$S/3$ — since any such item would fit into the underfull bin in instance $u$.
Therefore, for each such bin, there are only two options:

    * –

the bin contains one item larger than $S/2$ — so its weight is $10/12$;

    * –

the bin contains two items, each of which is larger than $S/3$ — so its weight
is at least $2\cdot 5/12=10/12$.

Again, the average bin weight (except excluding one bin per instance in groups
1, 2, and 5) of instances $u+1,\ldots,k$ is at least 10/12.

We conclude that the average weight of all bins in the $FFk$ packing (except
the $3k$ excluded bins) is at least $10/12$. Therefore:

$\displaystyle FFk$
$\displaystyle\leq(\frac{\frac{(17/12)+(15/12)\cdot(k-1)}{k}}{10/12}\cdot
OPT)+3k=$ $\displaystyle=(\frac{1.7+1.5\cdot(k-1)}{k})\cdot OPT+3k$
$\displaystyle=(\frac{1}{k}\cdot 1.7+\left(1-\frac{1}{k}\right)\cdot 1.5)\cdot
OPT+3k$

∎

###  0.A.2 Worst-case example

For $k>1$, the example given on page 306 in [12] for which $FF(D)/OPT(D)=1.7$
achieves a ratio of $1.35$ as follows:

All the items in this example $D$ are in non-decreasing order and are as
follows:
$D=\\{6/101(7),10/101(7),16/101(3),34/101(10),51/101(10)\\}$ and bin size $S$
is $101$. The number in the parenthesis denotes the occurrence of that item in
$D$. In the above example $6/10(7)$ expands to
$\\{6/10,6/10,6/10,6/10,6/10,6/10,6/10\\}$. Before proceeding further, we
describe some notation that we will use. For 2 bins $B_{i},B_{j}$, $i<j$
implies bin $B_{i}$ has been created before bin $B_{j}$. $R_{i}$ will denote
the remaining space in bin $B_{i}$.

For $k=1$, $FFk$ will result in the following number of bins:

$B_{1}=[6/101(\times 7),10/101(\times 5)]$ i.e. $B_{1}$ contains 7 items of
size $6/101$ and 5 items of size $10/101$.

$B_{2}=[10/101(\times 2),16/101(\times 3)]$,

$B_{3}=B_{4}=B_{5}=B_{6}=B_{7}=[34/101(\times 2)]$,

$B_{8}=B_{9}=B_{10}=B_{11}=B_{12}=B_{13}=B_{14}=B_{15}=B_{16}=B_{17}=[51/101]$

whereas $OPT$ for $k=1$ will result in below bins,

$O_{1}=O_{2}=O_{3}=[51/101,34/101,16/101]$,

$O_{4}=O_{5}=O_{6}=O_{7}=O_{8}=O_{9}=O_{10}=[51/101,34/101,10/101,6/101]$

Now consider the case for $k=2$, and the input to $FFk$ is $D_{2}$. The
packing for the first instance of $D$ will be the same as that for $k=1$.
Items in the second instance of $D$ can be packed in bins as below::

Note that the first item with size $6/101$ can’t be accommodated in bin
$B_{1}$ as it will result in the packing of the two copies of the same item in
the same bin. No other item can be accommodated in $B_{1}$ as $R_{1}=9$.
Therefore, the first five items of size $6/101$ can be accommodated in bin
$B_{2}$, and the remaining two items can be accommodated in bin $B_{3}$. Next,
$FFk$ will pack seven items of size $10/101$. Two of these items can be packed
in bin $B_{3}$. The next three items can be packed in bin $B_{4}$, and the
remaining two items can be packed in bin $B_{5}$. At this point
$R_{3},R_{4},R_{5},R_{6},R_{7}=\frac{1}{101},\frac{3}{101},\frac{13}{101},\frac{33}{101},\frac{33}{101}$
respectively. Now $FFk$ will pack three items of size $16/101$. Two of these
items can be packed in bin $B_{6}$, and the remaining one item can be packed
in bin $B_{7}$. Next in line are ten items of size $34/101$ to pack. $FFk$
will pack each one of them in bins from $B_{8}$ to $B_{17}$. In the end, ten
items of size $51/101$ are left to pack. $FFk$ will create ten new bins from
$B_{18}$ to $B_{27}$ and pack each one of them in these new bins. No items are
left, and ten new bins have been created. Thus for $k=2$, $FFk$ uses a total
of 27 bins. $OPT$ in this case is nothing but two copies each of $O_{1}$ to
$O_{10}$. Therefore, for $k=2$, $OPT$ will be 20. Hence,
$\frac{FFk}{OPT}=\frac{27}{20}=1.35$. Continuing in this way we get that
$\frac{FFk(D_{k})}{OPT(D_{k})}=\frac{17+10(k-1)}{10k}\leq 1.35$ for $k>1$.

##  Appendix 0.B Fernandez de la Vega-Lueker algorithm to $k$BP

We extend the algorithm by de la Vega and Lueker to solve $k$BP as follows:

Input: $D:$ input set of items, $k:$ an integer, $\epsilon>0$

Output: Packing of $D_{k}$.

1 Let $I$ and $J$ be multisets of small ($\leq\epsilon\cdot S$) and large
($>\epsilon\cdot S$) items in $D$, respectively.

2 Sort the items in $J$ in non-decreasing order.

3 Construct an instance from $J$ by linear grouping with
$g=n(J)\cdot{\epsilon}^{2}$ and round up the sizes in each group to the
maximum size in that group; call the resulting instance $U$.

4 Solve the configuration linear program $C_{k}$ corresponding to the rounded
problem $U$, optimally. This will give us an optimal solution to the $k$BP
instance $U_{k}$.

5 “Ungroup” the items to get a solution for $J_{k}$. Ungrouping refers to the
process of replacing the items in a group with the original items in that
group, as in step 3, prior to rounding up.

6 Greedily add small items in $I_{k}$ by respecting constraint of $k$BP to get
a solution for $D_{k}$.

Algorithm 3 Fernandez de la Vega-Lueker Algorithm to $k$BP

$J_{k}$ is the $k$-times analogue of $J$. Instance $I_{k}$ is defined in the
same way as $D_{k}$.

######  Proof (of Lemma 4)

Let $L$ be the problem resulting from rounding down the items in each group by
the maximum of the previous group. The first group will round down to 0. Since
bin-packing is monotone, therefore

$\displaystyle OPT(L_{k})\leq OPT(J_{k})\leq OPT(U_{k})$ (9)

Note that $L$ and $U$ differ by a group of $n(J)\cdot{\epsilon}^{2}$ items.
Therefore, the difference between $L_{k}$ and $U_{k}$ is, at most, $k\cdot
n(J)\cdot{\epsilon}^{2}$. Hence,

$\displaystyle OPT(U_{k})-OPT(L_{k})\leq k\cdot n(J)\cdot\epsilon^{2}$
$\displaystyle OPT(U_{k})\leq OPT(J_{k})+k\cdot n(J)\cdot\epsilon^{2}$ (10)

Since all items in $U_{k}$ have a size larger than $\epsilon\cdot S$.
Therefore, the maximum number of items in a bin can be $1/\epsilon$. Hence,
the minimum number of bins required would be $k\cdot n(J)\cdot\epsilon$.
Hence,

$k\cdot n(J)\cdot\epsilon^{2}\leq\epsilon\cdot(k\cdot
n(J)\cdot\epsilon)\leq\epsilon\cdot OPT(J_{k})$ (11)

by 0.B and 11

$OPT(U_{k})\leq(1+\epsilon)OPT(J_{k})$ (12)

∎

######  Proof (of Corollary 1)

From steps 3,and 5 of the algorithm, it is clear that from a packing of
$U_{k}$ ,we can get a packing of $J_{k}$ using the same number of bins.
Therefore, $bins(J_{k})\leq(1+\epsilon)\cdot OPT(J_{k})$. ∎

######  Proof (of Theorem 5.1)

Let $I$ be the set of all items $\leq\epsilon\cdot S$ in $D$, and
$I_{k}=II\ldots\text{k copies of }I$. In step 6, while packing the items in
$I_{k}$ if fewer than $k$ new bins are opened, then from corollary 1 it is
clear that $bins(D_{k})\leq bins(J_{k})+k\leq(1+\epsilon)\cdot OPT(J_{k})+k$.
Since bin packing is monotone hence, $OPT(J_{k})\leq OPT(D_{k})$. Therefore,
$bins(D_{k})\leq(1+\epsilon)\cdot OPT(D_{k})+k$.

Let’s assume that at least $k$ new bins are opened at step 6 of the algorithm.
Then, from equation 5.1

$bins(D_{k})\leq(1+2\cdot\epsilon)\cdot OPT(D_{k})+k$

From, Lemma 2,

$\displaystyle bins(D_{k})$ $\displaystyle\leq\max\\{(1+\epsilon)\cdot
OPT(D_{k})+k,(1+2\cdot\epsilon)\cdot OPT(D_{k})+k\\}$
$\displaystyle\leq(1+2\cdot\epsilon)\cdot OPT(D_{k})+k$ (13)

∎

##### Running time of algorithm 3:

Time $O(n(D)\log{n(D)})$ is sufficient for all the steps except the step 4 in
algorithm 3. Step 4 takes time $O(m(D)\cdot{n(D)}^{{m(D)}^{1/\epsilon}})$.
Therefore, the time taken by the algorithm is
$O(m(D)\cdot{n(D)}^{{m(D)}^{1/\epsilon}})$, which is polynomial in $n(D)$
given $m(D),\epsilon$.

##  Appendix 0.C Karmarkar-Karp algorithms to $k$BP

######  Proof (of Lemma 5)

The proof is easy in this case. When $k=1$ then, from [14] we know that
$OPT(D)\leq\frac{2}{S}\cdot V(D)+1$. Therefore, $OPT(D_{k})\leq
k.OPT(D)\leq\frac{2}{S}\cdot k\cdot V(D)+k=\frac{2}{S}\cdot V(D_{k})+k$. ∎

######  Proof (of Lemma 6)

Let $\mathbf{c}$ be the vector of length $m(D)$ whose $i$th element is $c[i]$:
the size of an item of type $i$. Let $\mathbf{n}$ be the vector of length
$m(D)$ whose $i$th element is $n[i]$, which denotes the number of items of
size $c[i]$. Define the size of a configuration as the sum of all the item
sizes in that configuration. Then, the size of configurations is represented
by the vector $\mathbf{c^{T}}A$. For example, suppose
$m(D)=2,n[1]=2,n[2]=2,c[1]=3,c[2]=4,S=10$. Then, the possible number of
configurations is 6, and matrix $A$ is $\begin{bmatrix}0&0&1&2&1&2\\\
1&2&0&0&1&1\end{bmatrix}$. $\mathbf{c^{T}}A$ will be defined by vector
$\begin{bmatrix}4&8&3&6&7&10\end{bmatrix}$. Note that the size of each
configuration can, at most, be $S$ (the bin size). Let $\mathbf{S}$ be a
vector of size $t$, each element of which is $S$(the bin size). Then,

$\mathbf{S}\geq\mathbf{c^{T}}A$ (14)

Let $\mathbf{x}$ be an optimal basic feasible solution to the fractional
linear program $F_{k}$, which represents the $k$BP problem, for instance,
$D_{k}$. Then, $\mathbf{S}\cdot\mathbf{x}$ will denote the maximum possible
sum of all the items corresponding to all the configurations in the solution
vector $\mathbf{x}$. Then,

$\displaystyle S\cdot LIN(D_{k})=S\cdot LIN(F_{k})$
$\displaystyle=\mathbf{S}\cdot\mathbf{x}$ (15)
$\displaystyle\geq(\mathbf{c}^{T}A)\cdot\mathbf{x}$ from 14 (16)
$\displaystyle\geq\mathbf{c}^{T}(k\mathbf{n})$ from 4 (17)

Since each element in $\mathbf{c^{T}}$ specifies an item of type $i$ and each
element in $\mathbf{n}$ denotes the number of items of type $i$. Therefore,
$\mathbf{c^{T}n}$ denotes the sum of the sizes of all items in $D$. Therefore,

$\displaystyle S\cdot LIN(D_{k})$ $\displaystyle=k\cdot V(D)=V(D_{k})$ from 17
(18)

In $LIN(D_{k})$, $x_{j}$ denotes the fractional value of the occurrence of
configuration $j$. If these fractional values are integer then,

$LIN(D_{k})=OPT(D_{k})$

Otherwise, the optimal value of $LIN(D_{k})$ is a lower bound on $OPT(D_{k})$.
Therefore,

$LIN(D_{k})\leq OPT(D_{k})$

A basic feasible solution to any LP has non-zero variables equal to, at most,
the number of constraints. Therefore, solution $\mathbf{x}$ has at most $m(D)$
non-zero variables. For each non-zero variable $x_{j}$,

$x_{j}=\lfloor x_{j}\rfloor+r_{j}$

where $\lfloor x_{j}\rfloor$ is the principal part of $x_{j}$, and $r_{j}$ is
the residual part of $x_{j}$. Note that if we consider all the configurations
corresponding to the residual part, then they only have a single copy of the
items in $D$. Let the instance corresponding to the residual part be
$D^{\prime}$. Then,

$V(D^{\prime})\leq S\cdot LIN(D^{\prime})=S\cdot\sum_{j}r_{j}$ (19)

For the residual part, we can construct two packings: First, for each non-zero
$r_{j}$, let’s take a bin of configuration $j$. We can then remove extra items
from it. Therefore,

$OPT(D^{\prime})\leq m(D_{k})\text{\\{Note that configurations remain same in
both }D_{k}\text{ and }D\text{\\}}$ (20)

Second, from Lemma 5:

$OPT(D^{\prime})\leq 2V(D^{\prime})/S+k$ (21)

From 20 and 21,

$\displaystyle OPT(D^{\prime})$
$\displaystyle\leq\min\\{m(D_{k}),2V(D^{\prime})/S+k\\}$ $\displaystyle
OPT(D^{\prime})$ $\displaystyle\leq averge(m(D_{k}),2V(D^{\prime})/S+k)$
$\displaystyle OPT(D^{\prime})$ $\displaystyle\leq
V(D^{\prime})/S+\frac{m(D_{k})+k}{2}$ (22)

Therefore,

$\displaystyle OPT(D_{k})$ $\displaystyle\leq\text{principal
part}+OPT(D^{\prime})$ $\displaystyle OPT(D_{k})$
$\displaystyle\leq\text{principal part}+V(D^{\prime})/S+\frac{m(D_{k})+k}{2}$
$\displaystyle OPT(D_{k})$ $\displaystyle\leq LIN(D_{k})+\frac{m(D_{k})+k}{2}$
from 19 (23)

∎

###  0.C.1 Solving the fractional linear program:

Solving the fractional linear program $F_{k}$ involves a variable for each
configuration.This results in a large number of variables. The dual, $D_{F}$,
of the fractional linear program, is:

$\displaystyle\max\quad k\cdot\mathbf{n\cdot y}$ (24) $\displaystyle\text{such
that}\quad A^{T}\mathbf{y}$ $\displaystyle\leq\mathbf{1}$ (25)
$\displaystyle\mathbf{y}$ $\displaystyle\geq 0$ (26)

The above dual LP can be solved to any given tolerance $h$ by using a variant
of the ellipsoid method that uses an approximate separation oracle [14]. This
separation oracle accepts as input a vector $\mathbf{y}$ and determines:

  * •

whether $\mathbf{y}$ is feasible, or

  * •

If not, then return a constraint that is violated, i.e. a vector $\mathbf{a}$
such that $\mathbf{a}\cdot\mathbf{y}>1$.

Let $\mathbf{c}$ be the $m(D)$-vector of item sizes. The separation oracle
solves the above problem by solving the following knapsack problem:

$\displaystyle\max\quad\mathbf{a}\cdot\mathbf{y}$ (27)
$\displaystyle\text{such that}\quad\mathbf{a}\cdot\mathbf{c}$
$\displaystyle\leq S$ (28) $\displaystyle\mathbf{a}$ $\displaystyle\geq 0$
(29)

Each element $a[i]\in\mathbf{a}$ represents $a[i]$ pieces of type $i$, and
hence $\mathbf{a}$ is an integer vector. If $\mathbf{y}$ is feasible, then the
optimal value of the above knapsack problem is, at most, $1$. Otherwise,
$\mathbf{a}$ correspond to a configuration that violates the constraint
$\mathbf{a}\cdot\mathbf{y}\leq 1$.

Suppose we want a solution within a specified tolerance $\delta$. Then, the
above knapsack problem can be solved in polynomial time by rounding down each
component of $\mathbf{y}$ to the closest multiple of $\frac{\delta}{n(D)}$.
The run time of the above algorithm is $O(\frac{m(D)\cdot n(D)}{\delta})$
[14]. Alternatively, we can round down each component of $\mathbf{y}$ to the
nearest multiple of $\frac{\delta}{k\cdot n(D)}$, and then the run time of the
above algorithm is $O(\frac{k\cdot m(D)\cdot n(D)}{\delta})$.

The modified ellipsoid method uses the above approximate separation oracle as
follows. Given the current ellipsoid center $\mathbf{y_{c}}$, let
$\widetilde{\mathbf{y_{c}}}$ be the rounded down solution corresponding to
$\mathbf{y_{c}}$. The modified ellipsoid method performs either an feasibility
cut (if $\widetilde{\mathbf{y_{c}}}$ is infeasible) or an optimality cut (if
$\widetilde{\mathbf{y_{c}}}$ is feasible). Since $\mathbf{\widetilde{y_{c}}}$
is the rounded down solution corresponding to $\mathbf{y_{c}}$, if
$\mathbf{\widetilde{y_{c}}}$ is infeasible then $\mathbf{y_{c}}$ is definitely
not feasible. In a feasibility cut, the modified ellipsoid method cuts from
the ellipsoid all points such that $\mathbf{a}\cdot\mathbf{y}>1$. If
$\mathbf{\widetilde{y_{c}}}$ is feasible, then $\mathbf{y_{c}}$ may or may not
be feasible. If rounding down is done to a multiple of $\frac{\delta}{k\cdot
n(D)}$, then, by definition of the rounding, we can say that

$\displaystyle k\cdot\mathbf{n}\cdot\widetilde{\mathbf{y_{c}}}$
$\displaystyle\geq
k\cdot\mathbf{n}\cdot\mathbf{y_{c}}-k\cdot\mathbf{n}\cdot\mathbf{1}\cdot\frac{\delta}{k\cdot
n}$ $\displaystyle=k\cdot\mathbf{n}\cdot\mathbf{y_{c}}-\delta$ (30)

In an optimality cut, the method preserves all the vectors whose value exceeds
$\widetilde{\mathbf{y_{c}}}$ by more than $\delta$ [14] i.e. it removes all
points that satisfy
$k\cdot\mathbf{n}\cdot\mathbf{y}<k\cdot\mathbf{n}\cdot\widetilde{\mathbf{y_{c}}}+\delta$
.

The number of iterations in the modified ellipsoid algorithm is the same as
that of the modified ellipsoid method in [14] that is, at most,
$Q=4\cdot{m(D)}^{2}\cdot\ln{(\frac{m(D)\cdot n(D)}{\epsilon\cdot
S\cdot\delta})}$ iterations. The total execution time of the modified
algorithm is $O(Q\cdot m(D)\cdot(Q\cdot m(D)+\frac{k\cdot n(D)}{\delta}))$.

Let $t$ be the number of configurations in $k$BP, which is the same as the
number of configurations in BP. There are at most $t$ constraints of the form
$\mathbf{a}\cdot\mathbf{y}\leq 1$ during the ellipsoid method. It is well-
known that in any bounded linear program with $m(D)$ variables, at most $m(D)$
constraints are sufficient to determine the optimal solution. We can use the
same constraint elimination procedure as in [14] to come up with this critical
set of $m(D)$ constraints. It results in having a reduced dual linear program
with $m(D)$ variables and $m(D)$ constraints. Let us call this reduced dual
linear program $R_{D_{F}}$. By taking the dual of $R_{D_{F}}$, we get a
reduced primal linear program, say $R_{F}$. This reduced primal linear program
will have only $m(D)$ variables corresponding to $m(D)$ constraints. Let us
denote the optimal solution of the dual linear program $D_{F}$ and the reduced
dual linear program $R_{D_{F}}$ as $LIN(D_{F})$ and $LIN(R_{D_{F}})$
respectively. Since $R_{D_{F}}$ is a relaxation of $D_{F}$ therefore,
$LIN(D_{F})\leq LIN(R_{D_{F}})$. From the modified GLS algorithm, we know that
$LIN(R_{D_{F}})\leq LIN(D_{F})+\delta$ if rounding down is done in a multiple
of $\frac{\delta}{k\cdot n(D)}$. From the duality theorem of the linear
program, both primal and dual have the same optimal solution. Therefore, the
optimal solution of the reduced primal linear program, $R_{F}$, is at most
$LIN(D_{F})+\delta$ using the rounding down scheme in the modified GLS method.

The constraint elimination procedure will require executing the modified GLS
algorithm to run at most
$(m(D)+1)(\lceil\frac{R}{m(D)+1}\rceil+(m(D)+1)\ln(\lceil\frac{R}{m(D)+1}\rceil)+1)$
times, where $R\leq Q+2\cdot m(D)$ [14]. In the constraint elimination
procedure, in the worst case, one out of every $m(D)+1$ executions succeeds
[14]. Therefore, the total accumulated error is
$\delta(\lceil\frac{R}{m(D)+1}\rceil+(m(D)+1)\ln(\lceil\frac{R}{m(D)+1}\rceil)+1)$.
If the tolerance $\delta$ is set to
$\frac{h}{\lceil\frac{R}{m(D)+1}\rceil+(m(D)+1)\ln(\lceil\frac{R}{m(D)+1}\rceil)+2}$
then the optimal solution of the reduced primal linear program is at most
$LOPT(D_{F})+h$ using the rounding down mechanism in the modified GLS method.

The total running time of the algorithm is $O((Q\cdot m(D)\cdot(Q\cdot
m(D)+\frac{k\cdot
n(D)}{\delta}))(m(D)+1)(\lceil\frac{R}{m(D)+1}\rceil+(m(D)+1)\ln(\lceil\frac{R}{m(D)+1}\rceil)+1))\approx
O(m(D)^{8}\cdot{\ln{m(D)}}\cdot{\ln^{2}(\frac{m(D)\cdot n(D)}{\epsilon\cdot
S\cdot h})}+\frac{m(D)^{4}\cdot k\cdot
n(D)\cdot\ln{m(D)}}{h}\ln{\frac{m(D)\cdot n(D)}{\epsilon\cdot S\cdot h}})$.
Since $m(D)=m(D_{k})$ and $k\cdot n(D)=n(D_{k})$, in our analysis, we denote
this running time as $T(m(D_{k}),n(D_{k}))$. ∎

###  0.C.2 Karmarkar-Karp Algorithm 1 extension to $k$BP

Recall that the algorithm 1 of Karmarkar-Karp algorithms uses the linear-
grouping technique 5.1.

Input: $D:$ set of items, $\epsilon>0$ be a positive real number, $k$: an
integer.

Output: Packing of $D_{k}$.

1 Let $J$ be the instance after keeping aside all items with sizes
$\leq\max\\{1/n,\epsilon/2\\}\cdot S$ in $D$. Let $I$ be the multiset of all
small items which are kept aside in $D$. $I_{k}$, similar to $D_{k}$, is the
$k$ times instance of $I$.

2 Perform the linear grouping on instance $J$ by making groups of cardinality,
$g=\lceil n(J)\cdot{\epsilon}^{2}\rceil$. Let’s call the resulting instances
as ${U^{\prime}}$ and $U^{\prime\prime}$ ($U^{\prime}$ and $U^{\prime\prime}$
are as defined in the linear grouping technique in subsection 5.1)

3 Pack each item in ${U^{\prime}_{k}}$ into a bin. There can be at most
$g\cdot k$ bins. ($k$ copies of each item)

4 Solve ${U^{\prime\prime}}_{k}$ using fractional linear program with
tolerance $h=1$. Denote the resulting solution as $\mathbf{x}$.

5 Construct the integer solution from $\mathbf{x}$ by the rounding method
using no more than $1.\mathbf{x}+\frac{m(U^{\prime\prime})+k}{2}$ bins (see
Lemma 2).

6 Reduce the item sizes as necessary and obtain a packing for $J_{k}$ along
with the addition of bins as in step 3.

7 Obtain a packing for $D_{k}$ by adding the items in $I_{k}$ which are kept
aside in step 1 by respecting constraint of $k$BP, creating new bin(s) when
necessary.

Algorithm 4 Karmarkar-Karp Algorithm 1 extension to $k$BP

######  Proof (of Theorem 5.2)

Since bin-packing is monotone.

$OPT({U^{\prime\prime}}_{k})\leq OPT(J_{k})\leq OPT(D_{k})$ (31)

The size of each item in $J_{k}$ is, at least, $\frac{\epsilon}{2}\cdot S$.
Therefore, from Lemma 6,

$\displaystyle S.OPT(J_{k})$ $\displaystyle\geq
V(J_{k})\geq\frac{\epsilon}{2}\cdot S\cdot n(J_{k})$ $\displaystyle
OPT(J_{k})$ $\displaystyle\geq\frac{\epsilon}{2}\cdot n(J_{k})$ (32)

From algorithm step 2 and from equations 31 and 0.C.2,

$g=\lceil n(J_{k})\epsilon^{2}\rceil\leq 2\cdot\epsilon\cdot OPT(J_{k})+1\leq
2\cdot\epsilon\cdot OPT(D_{k})+1$ $m({U^{\prime\prime}}_{k})\leq
n({U^{\prime\prime}}_{k})/g\leq n({U^{\prime\prime}}_{k})/{\lceil
n(J_{k})\epsilon^{2}\rceil}\leq n(J_{k})/{\lceil
n(J_{k})\epsilon^{2}\rceil}\leq 1/\epsilon^{2}$

We have tolerance $h=1$.

$\mathbf{1\cdot x}\leq LIN({U^{\prime\prime}}_{k})+1\leq
OPT({U^{\prime\prime}}_{k})+1\leq OPT(D_{k})+1$

Step 6 will result in number of bins:

$\leq\mathbf{1\cdot x}+\frac{m({U^{\prime\prime}}_{k})+k}{2}+g\cdot k$ $\leq
OPT(D_{k})+1+\frac{k+\frac{1}{\epsilon^{2}}}{2}+k\cdot(2\cdot\epsilon\cdot
OPT(D_{k})+1)$ $\leq(1+2\cdot
k\cdot\epsilon)OPT(D_{k})+\frac{1}{2\cdot\epsilon^{2}}+(2k+1)$

By Lemma 2, number of bins required at step 7 of the algorithm is:

$\displaystyle bin(D_{k})$ $\displaystyle\leq\max\\{(1+2\cdot
k\cdot\epsilon)OPT(D_{k})+\frac{1}{2\cdot\epsilon^{2}}+(2k+1),(1+2\
\cdot\epsilon)OPT(D_{k})+k\\}$ $\displaystyle bin(D_{k})$
$\displaystyle\leq(1+2\cdot
k\cdot\epsilon)OPT(D_{k})+\frac{1}{2\cdot\epsilon^{2}}+(2k+1)$ (33)

∎

##### Running time of algorithm 4:

The time taken by fractional linear program is $\leq
T(m(U^{\prime\prime}_{k}),n(U^{\prime\prime}_{k}))\leq
T(\frac{1}{\epsilon^{2}},n(D_{k}))$. The rest of the steps in Algorithm 1 will
take at most $O(n(D_{k})\log{n(D_{k})})$ time. Therefore, the execution time
of above Algorithm 1 is at most
$O(n(D_{k})\log{n(D_{k})}+T(\frac{1}{\epsilon^{2}},n(D_{k}))$.

###  0.C.3 Karmarkar-Karp Algorithm 2 extension to $k$BP

##### Alternative Geometric Grouping:

Let $J$ be some instance and $g>1$ be some integer parameter. Sort the items
in $J$ in non-increasing order of their size. Now, we partition $J$ into
groups each containing necessary number of items so that the size of each
group (the sum of item sizes in that group) is at least $g\cdot S$.

Let $l_{j}$ denote the cardinality of group $j$ (the number of items in that
group). Let $l_{r}$ be the cardinality of the last group in $J$. Note that
this last group, let us denote it with $G_{r}$, may have size $<g\cdot S$.

Since each item size is less than $S$, the number of items in each group is at
least $g+1$. Let us assume that the smallest item in $J$ is $\epsilon\cdot S$.
Then, the number of items in each group is at most $\frac{g}{\epsilon}$. Let
$r$ denote the number of groups formed in $J$. Therefore, $g+1\leq
l_{1}\leq\ldots\leq l_{r}\leq\frac{g}{\epsilon}$. Let ${G^{\prime}}_{i+1}$ be
the group obtained by increasing the size of each item in ${G}_{i+1}$ to the
maximum item size in that group except for the smallest $l_{i+1}-l_{i}$ items
in that group. Let $U^{\prime}=\cup_{i=2}^{r}\Delta{G_{i}}\cup G_{1}$, and
$U^{\prime\prime}=\cup_{i=2}^{r}G_{i}^{{}^{\prime}}$ where $\Delta G_{i}$ is
the multiset of smallest $l_{i}-l_{i-1}$ pieces in $G_{i}$. Since bin packing
is monotone, $OPT(J)\leq OPT(U^{\prime})+OPT(U^{\prime\prime})$.
From Lemma 5 $OPT(U^{\prime})\leq 2\cdot V(U^{\prime})/S+1$ (Note that $k=1$).
It holds that $V(U^{\prime})\leq S\cdot g\cdot(1+\ln{\frac{1}{\epsilon\cdot
S}})+S$ [14](page 315). Therefore,

$OPT(J)\leq OPT(U^{\prime\prime})+2\cdot
g\cdot\left(2+\ln{\frac{1}{\epsilon\cdot S}}\right)$ (34)

Also, $V(U^{\prime\prime})\geq\sum_{\forall i\in[r],i>1}g\cdot
S\cdot\frac{l_{i-1}}{l_{i}}\geq g\cdot
S\cdot\left((r-1)-\ln\frac{1}{\epsilon\cdot S}\right)$. Therefore [14],

$m(U^{\prime\prime})=r-1\leq V(U^{\prime\prime})/(g\cdot
S)+\ln{\frac{1}{\epsilon\cdot S}}$ (35)

∎

Input: $D:$ input set of items; $\epsilon>0$: a real parameter; $g>1$ an
integer parameter; $k$: an integer.

Output: Packing of $D_{k}$.

1 Let $J$ be the instance obtained after eliminating all items of size
$\leq\epsilon\cdot S$ from $D$.

2 while  _$V(J) >S\cdot(1+\frac{g}{g-1}\cdot\ln{\frac{1}{\epsilon}})$_ do

3 Do the alternative geometric grouping with parameter $g$. Let the resulting
instances be $U^{\prime}$ and $U^{\prime\prime}$.

4 Solve ${U^{\prime\prime}}_{k}$ using fractional bin-packing with tolerance
$h=1$. Denote the resuting basic feasible solution as x.

5 Construct an integer solution from x. Create $\lfloor x_{i}\rfloor$ bins for
each $x_{i}$ in x. Remove the packed items from $J$.

6 Pack ${U^{\prime}}_{k}$ in at most $2\cdot k\cdot
g\cdot\left[2+\ln\frac{1}{\epsilon}\right]$ bins.

7

8 end while

9When $V(J)\leq S\cdot(1+\frac{g}{g-1}\cdot\ln{\frac{1}{\epsilon}})$, pack the
remaining items greedily in at most $(2+\frac{2\cdot
g}{g-1}\cdot\ln{\frac{1}{\epsilon}})$ bins and create $k$ copies of it.

10 Greedily pack the $k-$copies of the items $\leq\epsilon\cdot S$ respecting
$k$BP constraint to get a solution for $D_{k}$.

11

Algorithm 5 Karmarkar-Karp Algorithm 2 extension to $k$BP

######  Proof (of Theorem 5.3)

Let ${U^{\prime\prime}}_{ki}$ be the instance at the beginning of the $i$th
iteration of the loop in step2, then the fractional part of $\mathbf{x}$
contains at most $m({U^{\prime\prime}}_{ki})$ non-zero variables $x_{j}$.
Therefore, from equation 35 we have

$m({U^{\prime\prime}}_{ki})=m({U^{\prime\prime}}_{i})\leq\frac{V({U^{\prime\prime}}_{i})}{gS}+\ln{\frac{1}{\epsilon}}$
(36)

_Number of Iterations in step 6 of algorithm:_ As shown in [14] the number of
iterations are at most $\leq\frac{\ln{V({D})}}{\ln{g}}+1$.

_Number of bins produced using Fractional Bin-Packing solution in step 3-5:_
Let $J_{i}$ denote the item set at the beginning of $i$th iteration. On
applying alternative geometric grouping with parameter $g$, we get instances
${U^{\prime}}_{i},{U^{\prime\prime}}_{i}$. Let
${U^{\prime}}_{ki},{U^{\prime\prime}}_{ki}$ are the corresponding $k$BP
instances. Let $B_{i}$ be the number of bins obtained in solving
${U^{\prime\prime}}_{ki}$ by applying fractional bin-packing at iteration $i$
with tolerance $h=1$. Then,

$B_{i}\leq LIN({U^{\prime\prime}}_{ki})+1$

Summing across all iterations

$\displaystyle\sum B_{i}$ $\displaystyle\leq
LIN({U^{\prime\prime}}_{k})+\frac{\ln{V(D)}}{\ln{g}}+1$ $\displaystyle\leq
OPT({U^{\prime\prime}}_{k})+\frac{\ln{V({D})}}{\ln{g}}+1$ (37)

_Total number of bins produced:_ Let $bin(D_{k})$ denote the total number of
bins produced. Then,

$\begin{split}bin(D_{k})=\text{bins produced in steps 3-5}+\text{bins produced
in steps 6}+\\\ \text{bins produced in step 8}\end{split}$
$\begin{split}bin(D_{k})\leq OPT(D_{k})+(\frac{\ln{V(D)}}{\ln{g}}+1)(1+4\cdot
k\cdot g+2\cdot k\cdot g\ln{\frac{1}{\epsilon}})+\\\ k(2+\frac{2\cdot
g}{g-1}\ln{\frac{1}{\epsilon}})\end{split}$ (38)

From Lemma 2

$\begin{split}bin(D_{k})\leq\max\\{OPT(D_{k})+(\frac{\ln{V(D)}}{\ln{g}}+1)(1+4\cdot
k\cdot g+2\cdot k\cdot g\ln{\frac{1}{\epsilon}})+\\\ k(2+\frac{2\cdot
g}{g-1}\ln{\frac{1}{\epsilon}}),(1+2\cdot\epsilon)OPT(D_{k})+k\\}\end{split}$
(39)

Choosing $g=2$ and $\epsilon=\frac{1}{V(D)}$ will result in

$\displaystyle bin(D_{k})$ $\displaystyle\leq
OPT(D_{k})+O(k\cdot\log^{2}{OPT(D)})$ (40)

number of bins. ∎

##### Running time of algorithm 5:

From equation 35, in each iteration of the while loop
$m(U^{\prime\prime}_{i})$ decreases by a factor of $g\cdot S$. During $i$th
iteration of while loop time taken by fractional bin-packing is $\leq
T(m({U^{\prime\prime}}_{ki}),n({U^{\prime\prime}}_{ki}))$. The rest of the
steps will take time at most $O(n(D_{k})\cdot\log{n(D_{k})})$. Therefore, the
total time taken by the algorithm is $O(T(\frac{n(D)\cdot S}{g\cdot
S}+\ln{\frac{1}{\epsilon}},n(D_{k}))+n(D_{k})\cdot\log{n(D_{k})})$. For choice
$g=2$ and $\epsilon=\frac{1}{V(D)}$ the running time will be
$O(T(\frac{n(D)}{2}+\ln{V(D)},n(D_{k}))+n(D_{k})\cdot\log{n(D_{k})})\in
O(T(\frac{n(D)}{2},n(D_{k}))+n(D_{k})\cdot\log{n(D_{k})})$.

##  Appendix 0.D More Electricity Distribution Results

In this section, we discuss the variation in hours of connection, comfort, and
electricity supplied with different values of $k$ and with varying levels of
uncertainty (standard deviation) in the agent’s demand.

In Figure 4, we can observe that the sum of comfort the algorithm delivers to
agents increase with an increasing value of $k$. However, that increase
appears to saturate as $k$ increases. Similar phenomena occur for other
metrics.

Figure 4 shows that the minimum comfort the algorithm delivers to agents
individually increases with an increasing value of $k$. However, that increase
appears to saturate as $k$ increases. Similar phenomena occur for other
metrics.

Figure 3: Mean utilitarian value of comfort is shown on the $y$-axis. $k$
values are shown on the $x$-axis. Figure shows the increase in sum of comfort
delivered by the algorithm to agents with increasing value of $k$ for varying
levels of uncertainty $\sigma$.

Figure 4: Minimum egalitarian value of comfort is shown on the $y$-axis. $k$
values are shown on the $x$-axis.Figure shows the increase in minimum comfort
delivered to agents individually with increasing value of $k$ for varying
levels of uncertainty $\sigma$.

In Figure 5, the maximum utility difference decreases with an increasing value
of $k$, and then again, it appears to start increasing. But still, the maximum
utility difference is meager. Similar phenomena occur for electricity-supplied
social welfare metrics. However, in the case of hours of connection, the
maximum utility difference is 0 because the algorithm is executed for each
hour.

Figure 5: Maximum utility difference of comfort is shown on the $y$-axis. $k$
values are shown on the $x$-axis. Figure shows the decrease in maximum utility
difference with increasing value of $k$ for varying levels of uncertainty
$\sigma$.