A robust APTAS for the classical bin packing problem. Epstein, L. & Levin, A. *Mathematical Programming*, 119(1):33--49, June, 2009. Paper doi abstract bibtex Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property cannot be maintained with respect to optimal solutions.

@article{epstein_robust_2009-1,
title = {A robust {APTAS} for the classical bin packing problem},
volume = {119},
issn = {0025-5610, 1436-4646},
url = {http://link.springer.com/article/10.1007/s10107-007-0200-y},
doi = {10.1007/s10107-007-0200-y},
abstract = {Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property cannot be maintained with respect to optimal solutions.},
language = {en},
number = {1},
urldate = {2014-04-14TZ},
journal = {Mathematical Programming},
author = {Epstein, Leah and Levin, Asaf},
month = jun,
year = {2009},
keywords = {Calculus of Variations and Optimal Control; Optimization, Mathematical Methods in Physics, Mathematical and Computational Physics, Mathematics of Computing, Numerical Analysis, combinatorics},
pages = {33--49}
}

Downloads: 0

{"_id":"KCsuwmyJh2mgZSWoJ","bibbaseid":"epstein-levin-arobustaptasfortheclassicalbinpackingproblem-2009","downloads":0,"creationDate":"2016-12-19T20:50:58.405Z","title":"A robust APTAS for the classical bin packing problem","author_short":["Epstein, L.","Levin, A."],"year":2009,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"A robust APTAS for the classical bin packing problem","volume":"119","issn":"0025-5610, 1436-4646","url":"http://link.springer.com/article/10.1007/s10107-007-0200-y","doi":"10.1007/s10107-007-0200-y","abstract":"Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property cannot be maintained with respect to optimal solutions.","language":"en","number":"1","urldate":"2014-04-14TZ","journal":"Mathematical Programming","author":[{"propositions":[],"lastnames":["Epstein"],"firstnames":["Leah"],"suffixes":[]},{"propositions":[],"lastnames":["Levin"],"firstnames":["Asaf"],"suffixes":[]}],"month":"June","year":"2009","keywords":"Calculus of Variations and Optimal Control; Optimization, Mathematical Methods in Physics, Mathematical and Computational Physics, Mathematics of Computing, Numerical Analysis, combinatorics","pages":"33--49","bibtex":"@article{epstein_robust_2009-1,\n\ttitle = {A robust {APTAS} for the classical bin packing problem},\n\tvolume = {119},\n\tissn = {0025-5610, 1436-4646},\n\turl = {http://link.springer.com/article/10.1007/s10107-007-0200-y},\n\tdoi = {10.1007/s10107-007-0200-y},\n\tabstract = {Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property cannot be maintained with respect to optimal solutions.},\n\tlanguage = {en},\n\tnumber = {1},\n\turldate = {2014-04-14TZ},\n\tjournal = {Mathematical Programming},\n\tauthor = {Epstein, Leah and Levin, Asaf},\n\tmonth = jun,\n\tyear = {2009},\n\tkeywords = {Calculus of Variations and Optimal Control; Optimization, Mathematical Methods in Physics, Mathematical and Computational Physics, Mathematics of Computing, Numerical Analysis, combinatorics},\n\tpages = {33--49}\n}\n\n","author_short":["Epstein, L.","Levin, A."],"key":"epstein_robust_2009-1","id":"epstein_robust_2009-1","bibbaseid":"epstein-levin-arobustaptasfortheclassicalbinpackingproblem-2009","role":"author","urls":{"Paper":"http://link.springer.com/article/10.1007/s10107-007-0200-y"},"keyword":["Calculus of Variations and Optimal Control; Optimization","Mathematical Methods in Physics","Mathematical and Computational Physics","Mathematics of Computing","Numerical Analysis","combinatorics"],"downloads":0,"html":""},"search_terms":["robust","aptas","classical","bin","packing","problem","epstein","levin"],"keywords":["calculus of variations and optimal control; optimization","mathematical methods in physics","mathematical and computational physics","mathematics of computing","numerical analysis","combinatorics"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}