time-complexitybin-packing# If the BinPack problem were in P, how to get a packing that minimizes the number of bins in P?

I have the following definition of a BinPack problem:

The problem is to place a certain number of objects in a certain number of bins. The objects have different weights, each bin accepting a maximum load (all bins can accommodate the same load here). The associated BinPack property is formally defined as follows:

Input:

- n: number of objects
- x1, ..., xn: n integers, the weights of the objects
- c: bin capacity (integer)
- k: number of bins
Output:

- Yes, if there is a possible packing.
- No, otherwise.

The following definition of a decision problem associated with the BinPack problem is also provided: Let this problem be called BinPackOpt

Input:

- n: number of objects
- x1, ..., xn: n integers, the weights of the objects
- c: bin capacity (integer)
- k: number of bins
Output: A correct packing that minimizes number of bins.

I need to show that if the BinPack property was P, then BinPackOpt would also be P.

Therefore, I must construct a packing in polynomial time using the polynomial time algorithm of the BinPack problem. I already figured out how to get the minimum number of bins in polynomial time by using a binary search algorithm with bounds 1 and n initially and fixing the bounds according to outcome of the BinPack problem. That is, if we can accommodate the objects in "median" number of bins, then I fix the upper boundary to median, and if not, I fix the lower boundary to median + 1 which gives me an algorithm in O(P(n).log(n)) where P(n) is the complexity of the BinPack problem. However, I am not able to figure out how to get the actual packing of the objects in this optimal number of bins in polynomial time.

How can I solve this issue? Any help is appreciated.

Solution

You can find the fewest number of bins necessary for `BinPackOpt`

to find any packing, as you say, via a binary search in which `BinPack`

will be called `O(log n)`

times.

Let's say the minimum number of bins necessary for a packing to be possible is found to be *k*. Then the following pseudocode will give you the optimal packing:

```
let current_set = {obj_1, ..., obj_n}
loop1: let test_obj be the first object in current_set
loop2: for each obj_i in current_set not equal to test_obj
let test_set = current_set - {test_obj, obj_i}
add a new object to test_set that has the combined weight of test_obj and obj_i
call BinPack on test_set with k bins of the given capacity
if BinPack succeeds
record that test_obj and obj_i are binned together
let current_set = test_set
goto loop1
record that test_obj is binned alone
let test_obj = test_obj+1
goto loop2
```

The inner loop of the above places one object into a bin of the optimal packing using `O(n)`

calls to `BinPack`

so you can find the whole optimal packing with `O(n^2)`

calls to `BinPack`

.

- What is the formal definition of Θ(f(n)) without expressing Θ(f(n)) in terms of O(f(n)) or Ω(f(n))?
- What is the Big-O of this function that reverses words in a string
- Why is the time complexity of Python's list.append() method O(1)?
- How can I apply meet-in-the-middle algorithm for searching whole 2D matrix
- lru_cache vs dynamic programming, stackoverflow with one but not with the other?
- c++ bitset logical operations in O(log n)?
- Time complexity of while loop inside for loop
- Time complexity of simultaneous iteration
- Time complexity for recursive binary search that also prints current subarray
- What's the Time Complexity of two separate inner loops nested in an outer loop?
- how to calculate binary search complexity
- Time complexity of StringBuilder reverse method
- How should I calculate the Time complexity for the below code?
- Big O notation of string permutation in Python
- Count number of digits - which method is most efficient?
- most efficient way to compute f(n)^f(n) where f(n)=n^n and n has 15-20 digits
- Big O of algorithm that steps over array recursively
- Why is O(n) better than O( nlog(n) )?
- How can the time complexity for this algo be O(N)?
- Find max product using divide and conqure in O(n) time
- Rough estimate of running time from Big O
- Calculation of time complexity of a function that finds all possible sum combinations of a given number from the list
- Find occurrences of subsequence in a binary string (non-necessarily-contiguous)
- Is complexity O(log(n)) equivalent to O(sqrt(n))?
- Leetcode 2161: Partition array according to given pivot
- Time Complexity of my program in competitive programming question City Plan
- How to calculate the time complexity of this recursive function
- Why log(n!) is O(nlog(n)) and not O(log(n!))
- Given an array of houses find how many segments exists after n queries
- How to simplify my double loops by matlab vectorization?