SWAT 2010: Algorithm Theory - SWAT 2010 pp 260-272

# Bin Packing with Fixed Number of Bins Revisited

• Klaus Jansen
• Stefan Kratsch
• Dániel Marx
• Ildikó Schlotter
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 6139)

## Abstract

As Bin Packing is NP-hard already for k = 2 bins, it is unlikely to be solvable in polynomial time even if the number of bins is a fixed constant. However, if the sizes of the items are polynomially bounded integers, then the problem can be solved in time n O(k) for an input of length n by dynamic programming. We show, by proving the W-hardness of Unary Bin Packing (where the sizes are given in unary encoding), that this running time cannot be improved to f(kn O(1) for any function f(k) (under standard complexity assumptions). On the other hand, we provide an algorithm for Bin Packing that obtains in time $$2^{O(k\log^2 k)}+O(n)$$ a solution with additive error at most 1, i.e., either finds a packing into k + 1 bins or decides that k bins do not suffice.

## Keywords

Large Item Small Item Medium Item Item Size Feasible Mapping
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

## References

1. 1.
Alon, N., Ruzsa, I.Z.: Non-averaging subsets and non-vanishing transversals. J. Comb. Theory, Ser. A 86(1), 1–13 (1999)
2. 2.
Bose, R.C., Chowla, S.: Theorems in the additive theory of numbers. Comment. Math. Helv. 37(1), 141–147 (1962-1963)Google Scholar
3. 3.
Bosznay, A.P.: On the lower estimation of non-averaging sets. Acta Math. Hung. 53, 155–157 (1989)
4. 4.
de la Vega, W.F., Lueker, G.: Bin packing can be solved in within 1 + ε in linear time. Combinatorica 1, 349–355 (1981)
5. 5.
Coffman, J.E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: A survey. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 46–93. PWS Publishing, Boston (1997)Google Scholar
6. 6.
Eisenbrand, F., Shmonin, G.: Caratheodory bounds for integer cones. OR Letters 34, 564–568 (2006)
7. 7.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
8. 8.
Graham, S.W.: $$B\sb h$$ sequences. In: Analytic number theory. Progr. Math., vol. 1 (1995), vol. 138, pp. 431–449. Birkhäuser, Boston (1996)Google Scholar
9. 9.
Halberstam, H., Roth, K.F.: Sequences. Springer, New York (1983)
10. 10.
Jansen, K.: An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. In: ICALP ’09: 36th International Colloquium on Automata, Languages and Programming, pp. 562–573 (2009)Google Scholar
11. 11.
Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. of OR 12, 415–440 (1987)
12. 12.
Karmarkar, N., Karp, R.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: FOCS 1982: 23rd IEEE Symposium on Foundations of Computer Science, pp. 312–320 (1982)Google Scholar
13. 13.
Lenstra, H.: Integer programming with a fixed number of variables. Math. of OR 8, 538–548 (1983)
14. 14.
Plotkin, S., Tardos, D., Tardos, E.: Fast approximation algorithms for fractional packing and covering problems. Math. of OR 20, 257–301 (1995)
15. 15.
Ruzsa, I.Z.: Solving a linear equation in a set of integers. I. Acta Arith. 65(3), 259–282 (1993)
16. 16.
Simchi-Levi, D.: New worst-case results for the bin-packing problem. Naval Res. Logist. 41(4), 579–585 (1994)

## Authors and Affiliations

• Klaus Jansen
• 1
• Stefan Kratsch
• 2
• Dániel Marx
• 3
• Ildikó Schlotter
• 4
1. 1.Institut für InformatikChristian-Albrechts-Universität KielKielGermany
2. 2.Max-Planck-Institut für InformatikSaarbrückenGermany
3. 3.Tel Aviv UniversityIsrael
4. 4.Budapest University of Technology and EconomicsBudapestHungary

## Personalised recommendations

### Citepaper
{"ft_lang_label":"__label__en","ft_lang_prob":0.62737584,"math_prob":0.8120842,"size":3550,"snap":"2019-26-2019-30","text_gpt3_token_len":1073,"char_repetition_ratio":0.14551607,"word_repetition_ratio":0.0,"special_character_ratio":0.2974648,"punctuation_ratio":0.25987262,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9646021,"pos_list":[0,1,2],"im_url_duplicate_count":[null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-07-18T13:07:11Z\",\"WARC-Record-ID\":\"<urn:uuid:87dda6d9-5d9d-4bf2-ae89-4a2539d7f173>\",\"Content-Length\":\"83820\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:0b4e7acb-acf6-4720-8c18-e3d638122110>\",\"WARC-Concurrent-To\":\"<urn:uuid:7aae9676-8da7-4298-a457-6ea44c452835>\",\"WARC-IP-Address\":\"151.101.200.95\",\"WARC-Target-URI\":\"https://link.springer.com/chapter/10.1007/978-3-642-13731-0_25\",\"WARC-Payload-Digest\":\"sha1:SKXOCEICNHGXXZ67UNBPXFXB5VCE4DVP\",\"WARC-Block-Digest\":\"sha1:XXF5XHEB3ISSIJ6ORPYR4T723QFP4FCC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-30/CC-MAIN-2019-30_segments_1563195525634.13_warc_CC-MAIN-20190718125048-20190718151048-00348.warc.gz\"}"}