Faster Exponential Time Algorithm for Bin Packing

(some slides are by Cline) A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins (via Additive Combinatorics) To appear at SODA 21 Started with this research at Parameterized Algorithms Retreat of the University of Warsaw in February 2020 Jesper Nederlof Jakub Pawlewicz C line Swennenhuis Karol W grzycki (a person wearing glasses) (a person wearing glasses) (a person posing for camera) (a close up of a person) UU Warsaw TU/e Warsaw/Saarbr cken

The Bin Packing Problem Given integers ?1, ,??, capacity ? number of bins ? 5 1 4 2 4 3 3 1 Asked partition ?1,?2, ,??of {1, ,?} s.t for each j: ? ?? ? ???? ? Algorithm A: ?(?? ?) Algorithm B: ?(2? ?) 4 5 time (direct DP) time (Bj rklund et al.) 8 Open Question Can do in ?(1.9999?) time? 8 WHY?? Try to run into the computational barrier Counter pessimism: Stronger hardness assumptions are gaining popularity 8 8

Before our work, only known for ? = 2,3 (Lente et al.) Our Contribution Can do in ?( 2 ?? ?) time for ??> 0 that depends on ? To explain our approach, we first assume All bins need to be tightly packed: ?1+ + ??= ? ? There is a balanced solution: ? ?/2?? = ?/2 ? 6: ? 40: ? 48: ? 1??: 25 March 24 April 29 April ?? May Key Idea: For every tight instance with balanced solution, either an extension of Algorithm A runs in ?( 2 ?? 11 may ? : ?) time ?(?) is small or an extension of Algorithm B runs in ?( 2 ?? ?) time ?(?) is small To relax the tightness and balancedness assumptions, additional ideas are needed

Algorithm A: Dynamic Programming Given item ?, remainder capacities ?1, ,??(1 ?? ?) define ? ?,?1, ,?? can items 1, ,? be divided over ? bins with capacities ?1 ,?? ? ?,?1, ,?? = ?[? 1, ,?? ??, ] ? ? ? ? :? {1, ,? } = {0,100, ,100?} and thus ? ? = ? + 1 We can compute ?[?,?, ,?] in ?(???2) time But what if, say, ? = 1000 and ?1= ?2= = ??= 100? Surely the algorithm doesn t need to compute all 1000?? table entries?! The above algorithm can actually be implemented in ? ?? ?2time, where ?(?) is the number of distinct subset sums | ? ? : ? {1, ,?} | Thm. If ? ? 1.99?/?, can solve instance in time ?(1.99??2) = ?(1.999?)

Algorithm B: The ?(2??) time algorithm {1, ,?} ? = {?1,?2} Due to Bj rklund, Husfeldt, Kaski and Koivisto Based on inclusion exclusion and fast algebraic transformations. ?1 ?2 For example, instance is yes iff ?/2 1? |?|{? ?:? ? ?}?> 0 ? {1, ,?} ? {1, ,?} In fact their algorithm computes a lot more. Def (closure): For a set family 2[?], define all subsets of a member of all supersets of a member of 0 Thm(BKKK). Given 2[?], we can compute for each ? whether ? can be distributed among ? bins in ?( ?) time.

Algorithm B: The ?(2??) time algorithm Thm(BKKK). Given 2[?], we can compute for each ? whether ? can be distributed among ? bins in ?( ?) time.

Algorithm B: The ?(2??) time algorithm {1, ,?} ? Thm(BKKK). Given 2[?], we can compute for each ? whether ? can be distributed among ? bins in ?( ?) time. Fix solution ?1, ,??, let ? ? ?/2?? Tightness implies ? ? = ??/2 Balancedness implies ? = ?/2 ? 2 ?1 ?2 ?3 ?4 ?5 Algorithm B: 1. Enumerate {? ? :? ? =?? (can be done in O((2n/2+ | |)n) time with Subset Sum algo) 2. Determine for each ? whether ? and ? ? fit in ?/2 bins (with BKKK, this takes ?( + ) ?) time ) If 1.99?, then + 1.99 ? Def (Max Binsize). ? ? max ? 2} 0 Thm. If ? ? 1.99?, then 1.99?and can solve instance in ?(1.99 ??) time |{ ? ? :? ? = ?}|

? ? ? ? max ? ? |{? ? :? ? = ? ? {1, ,?} }| ? Some Additive Combinatorics 0.99? ? , If ?(?) 2 Algorithm A fast If ? ? 21 ? ?, Algorithm B fast Histogram Histogram ??, ,?? ?(?) ? ? Want to show ?(?) and ?(?) not both large One direction: Upper bound ? ? ? ? Trivial upper bound 4?, will see 3? 0 0 0 0 0 1 32 Puzzle: maximize ? ? ? ? where ? has 3,4 or 5 integers: 1,2,3 gives 7x2 = 14 1,1,3,3 gives 9x4 = 36 1,1,3,3,9 gives 18x4 = 64 Which sequence of length 2? Repeated powers of 3 roughly maximize product?! 32 1 1 2 4 8 16 16 3 1 2 3 4 5

? ? ? ? max ? ? |{? ? :? ? = ? ? {1, ,?} }| ? Some Additive Combinatorics 0.99? ? , If ?(?) 2 Algorithm A fast If ? ? 21 ? ?, Algorithm B fast Thm. For all ? > 0, there exists ? > 0 such that: if ? ? 2??, then ? ? 21 ? ?. This implies our main result for tight instances with balanced solution: Pick ? 0.99/?: If ? ? 2??, Algorithm A runs in ?(20.99?) time If ? ? 2??, theorem implies ? ? 21 ???and Algorithm B runs in ?(2(1 ?? )?) time Proof of theorem is not easy (>10 pages) heavily builds on a previous connection with Uniquely Decodable Code Pairs

Uniquely Decodable Code Pairs (UDCPs) Def (UDCP): A UDCP is a pair ?, {0,1}?s.t. ? + = ? | |. ? = {10,01}, = {00,01,11} is UDCP: ? + = {10,11,21,01,02,12} ? + := {a + b:? ?,? }, a + b is addition over ?. ? 1011100 1101101 0000000 1010011 0101010 1111101 1100111 1100111 1011100 1101101 0000000 1010011 1010011 0101010 1111101 1 0 1 0 0 1 1 1 ?? 0 2 1 0 0011001 1010101 0011011 0110110 0110110 0110110 0011001 1010101 0011011 0 1 1 0 1 1 0 1 0

Uniquely Decodable Code Pairs (UDCPs) Def (UDCP): A UDCP is a pair ?, {0,1}?s.t. ? + = ? | |. ? = {10,01}, = {00,01,11} is UDCP: ? + = {10,11,21,01,02,12} ? + := {a + b:? ?,? }, a + b is addition over ?. Observation: If ?, {0,1}?form UDCP, then ? 3? Why? ? + {0,1,2}? Best known bounds: Exist ?, with ? 21.31781? ? 21.5 ?for any UDCP ?,

? ? ? ? max ? ? |{? ? :? ? = ? ? {1, ,?} }| ? Bounding ? ? ? ? 3?via UDCP s It will be convenient to view ? as a vector ? ? Instead of a subset ? [?] we use a vector ? 0,1nand ? ? = ?,? Construct ? {0,1}?by selecting for each ? one element from { ? 0,1? ?,? = ? } Construct {0,1}?by fixing a value ? and { ? 0,1?: ?,? = ? } We can assume |?| = ?(?) and = ? ? Sufficient to show ?, form a UDCP: Suppose ?1,?2 ? and ?1,?2 ? s.t. ?1+ ?1= ?2+ ?2 Then ?1,? = ?1+ ?1,? ? = ?2+ ?2,? ? = ?2,? Thus ?1= ?2and therefore also ?1= ?2

Some Additive Combinatorics 0.99? ? , If ?(?) 2 Algorithm A fast If ? ? 21 ? ?, Algorithm B fast Thm. For all ? > 0, there exists ? > 0 such that: if ? ? 2??, then ? ? 21 ? ?. There exist ? with ? ? 1.99999? and ? ? 20.2563? [Wiman 17]! Proof sketch: Use same ? as before. But for some ? ?(?) we construct roughly as follows: {?1+ ?2+ + ??: ?1, ,?? ?, ?1, ,?? "????? ?? ??????"} We still have the property ? + = ? | | Use the bound ? |? + |/| |; Quite some technical work to control |? + | and | |

Extra ideas for the general case If there exists a non-balanced solution: Algorithm B with obtained by random samples If instance is non-tight: Divide the weights by 2?and round to integers ? depends on weights non-trivially Combines Algorithm A (with finite precision) with Algorithm B.

Conclusion Main result: Bin packing in ? ( 2 ?? for some some ??> 0 that depends on ?. ?) time, Key idea: Tradeoff between parameters ?(?) and ?(?) and Algorithm A and Algorithm B complement each other nicely. Further Research: Can we solve Bin Packing instance with non-constant #bins in ?(1.99 ?) time? Ideas from this paper may be useful, but more cleverness is needed. Can we get ?(1.99 ?) time algorithms for other special cases of Set Cover? Several questions on ? ? ,?(?) and UDCP s