0
$\begingroup$

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. 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. 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?

EDIT: the motivation for the question comes from a different problem: fair allocation of items using the 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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Chandra Chekuri
    Aug 17, 2021 at 21:24
  • $\begingroup$ @ChandraChekuri good question; I added an explanation. $\endgroup$
    – Erel Segal-Halevi
    Aug 18, 2021 at 11:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.