<p>Bin-packing (BP) and maximum-makespan (MM) are dual problems. In both problems, the input can be defined as a set <span class="math-container">$S$</span> of positive integers, and the output is a partition of <span class="math-container">$S$</span>.</p>
<ul>
<li>In BP, there is a second input <span class="math-container">$c$</span> (capacity), the sum of integers in each part should be at most <span class="math-container">$c$</span>, and subject to this, the number of parts should be as small as possible;</li>
<li>In MM, the second input is <span class="math-container">$n$</span> (number), there must be at most <span class="math-container">$n$</span> parts, and subject to this, the maximum sum of integers in each part should be as small as possible.</li>
</ul>
<p>An optimal algorithm for BP can be used to solve MM as follows. Given <span class="math-container">$S$</span> and <span class="math-container">$n$</span>, find the smallest integer <span class="math-container">$c$</span> such that BP<span class="math-container">$(S,c)$</span> packs at most <span class="math-container">$n$</span> bins. This smallest <span class="math-container">$c$</span> is the optimal solution for MM<span class="math-container">$(S,n)$</span>. It can be found using binary search.</p>
<p>Since BP is NP-hard, we do not have a polytime algorithm for solving it exactly, but we have approximation algorithms. This raises the following question: suppose that we apply the above binary-search algorithm using some approximation algorithm for BP. What approximation factor do we get for MM?</p>
<p>Coffman, Garey and Johnson (1978) studied this question for a specific approximation algorithm for BP, known as the <a href="https://en.wikipedia.org/wiki/First-fit-decreasing_bin_packing" rel="nofollow noreferrer">first-fit-decreasing algorithm</a>. Its approximation ratio for BP is about 11/9. When it is used in the binary-search scheme for MM, it is called the <a href="https://en.wikipedia.org/wiki/Multifit_algorithm" rel="nofollow noreferrer">Multifit algorithm</a>. Its approximation ratio for MM is about 13/11.</p>
<p>MY QUESTION IS: Is there any analysis of the performance of the binary-search MM algorithm with different BP approximation algorithms? In particular, what is its performance when used with the <a href="https://en.wikipedia.org/wiki/Next-fit-decreasing_bin_packing" rel="nofollow noreferrer">Next-fit-decreasing algorithm</a>?</p>
<p>EDIT: the motivation for the question comes from a different problem: fair allocation of items using the <a href="https://en.wikipedia.org/wiki/Maximin-share" rel="nofollow noreferrer">maximin-share</a> criterion. In this problem, instead of a set of integers there is a set of items, and there are several people each of whom assigns a different value to each item. It can be shown that the MM algorithm based on next-fit-decreasing and binary-search can be adapted to solve this problem; this is why I am interested in its approximation ratio.</p>

CC BY-SA 4.0
2021-08-17T21:24:06.453Z
Why not attack MM directly instead of doing this round about reduction via BM? There is a simple PTAS, and even an EPTAS, for MM. From an approximation point of view it is settled essentially. On the other hand BP is quite open because one cannot rule out packing in OPT+1 bins. As is well known, even closely related problems that are polynomial-time equivalent behave differently when considering approximation. What is a good motivation for your question?
Chandra Chekuri
CC BY-SA 4.0
2021-08-18T11:33:14.897Z
@ChandraChekuri good question; I added an explanation.
Erel Segal-Halevi
<approximation-algorithms><optimization><partition-problem><scheduling><packing>
Using bin-packing algorithms to approximate maximum-makespan
Erel Segal-Halevi
# Using bin-packing algorithms to approximate maximum-makespan

(Asked by: username_0 on 2021-08-17)

Bin-packing (BP) and maximum-makespan (MM) are dual problems. In both problems, the input can be defined as a set $S$ of positive integers, and the output is a partition of $S$.

* In BP, there is a second input $c$ (capacity), the sum of integers in each part should be at most $c$, and subject to this, the number of parts should be as small as possible;
* In MM, the second input is $n$ (number), there must be at most $n$ parts, and subject to this, the maximum sum of integers in each part should be as small as possible.

An optimal algorithm for BP can be used to solve MM as follows. Given $S$ and $n$, find the smallest integer $c$ such that BP$(S,c)$ packs at most $n$ bins. This smallest $c$ is the optimal solution for MM$(S,n)$. It can be found using binary search.

Since BP is NP-hard, we do not have a polytime algorithm for solving it exactly, but we have approximation algorithms. This raises the following question: suppose that we apply the above binary-search algorithm using some approximation algorithm for BP. What approximation factor do we get for MM?

Coffman, Garey and Johnson (1978) studied this question for a specific approximation algorithm for BP, known as the [first-fit-decreasing algorithm](https://en.wikipedia.org/wiki/First-fit-decreasing_bin_packing). Its approximation ratio for BP is about 11/9. When it is used in the binary-search scheme for MM, it is called the [Multifit algorithm](https://en.wikipedia.org/wiki/Multifit_algorithm). Its approximation ratio for MM is about 13/11.

MY QUESTION IS: Is there any analysis of the performance of the binary-search MM algorithm with different BP approximation algorithms? In particular, what is its performance when used with the [Next-fit-decreasing algorithm](https://en.wikipedia.org/wiki/Next-fit-decreasing_bin_packing)?

EDIT: the motivation for the question comes from a different problem: fair allocation of items using the [maximin-share](https://en.wikipedia.org/wiki/Maximin-share) criterion. In this problem, instead of a set of integers there is a set of items, and there are several people each of whom assigns a different value to each item. It can be shown that the MM algorithm based on next-fit-decreasing and binary-search can be adapted to solve this problem; this is why I am interested in its approximation ratio.

**Tags:** approximation-algorithms, optimization, partition-problem, scheduling, packing

> **Comments:**
> **username_1**: Why not attack MM directly instead of doing this round about reduction via BM? There is a simple PTAS, and even an EPTAS, for MM. From an approximation point of view it is settled essentially. On the other hand BP is quite open because one cannot rule out packing in OPT+1 bins. As is well known, even closely related problems that are polynomial-time equivalent behave differently when considering approximation. What is a good motivation for your question?  
> **username_0**: @ChandraChekuri good question; I added an explanation.  

---

## 0 answers

