5. Proofs 5.a. Prove: Bin Packing is NP-complete. Use: Partition « Bin Packing. The [Bin Packing) problem: Given a finit
Posted: Tue Sep 07, 2021 7:53 am
- 5 Proofs 5 A Prove Bin Packing Is Np Complete Use Partition Bin Packing The Bin Packing Problem Given A Finit 1 (168.64 KiB) Viewed 85 times
5. Proofs 5.a. Prove: Bin Packing is NP-complete. Use: Partition « Bin Packing. The [Bin Packing) problem: Given a finite set U of items, a size s(u) e Z+ for each u EU, a positive integer bin capacity B, and a positive integer K. Is there a partition of U into dis- joint subsets U1, U2,...,UK such that the sum of the sizes of the items in each U; is B or less? The (Partition) problem: Given a list of n positive integers S1, S2, ..., Sn with o = 2-1 Si and a positive integer z = 0/2. Does there exist a subset I c {1,...,n} such that Lier si = Liçi si = z? Please use the proof structure as in lecture and homework: Step 1: Prove Bin Packing is in NP. Solution: Step 2: Select a known NP-Complete problem - Partition Step 3: Show how to compute a specific input for Bin Packing in polynomial time, given an arbitrary input for Partition. Solution: