{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:50Z","timestamp":1740122390930,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,25]],"date-time":"2017-05-25T00:00:00Z","timestamp":1495670400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11371216"],"award-info":[{"award-number":["11371216"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s10878-017-0140-2","type":"journal-article","created":{"date-parts":[[2017,5,25]],"date-time":"2017-05-25T09:47:57Z","timestamp":1495705677000},"page":"1198-1209","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Bin packing under linear constraints"],"prefix":"10.1007","volume":"34","author":[{"given":"Zhenbo","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kameng","family":"Nip","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,25]]},"reference":[{"key":"140_CR1","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1007\/978-1-4419-7997-1_35","volume-title":"Handbook of combinatorial optimization","author":"EG Coffman Jr","year":"2013","unstructured":"Coffman EG Jr, Csirik J, Galambos G, Martello S, Vigo D (2013) Bin packing approximation algorithms: survey and classification. In: Pardalos PM, Du D-Z, Graham RL (eds) Handbook of combinatorial optimization. Springer, New York, pp 455\u2013531"},{"key":"140_CR2","first-page":"34-1","volume-title":"Handbook of approximation algorithms and metaheuristics","author":"EG Coffman Jr","year":"2006","unstructured":"Coffman EG Jr, Csirik J, Leung JY-T (2006) Variable-sized bin packing and bin covering. In: Gonzales T (ed) Handbook of approximation algorithms and metaheuristics. Taylor and Francis Books, Boca Raton, pp 34-1\u201334-11 (chapter 34)"},{"key":"140_CR3","first-page":"46","volume-title":"Approximation algorithms for np-hard problems","author":"EG Coffman Jr","year":"1997","unstructured":"Coffman EG Jr, Garey MR, Johnson DS (1997) Approximation algorithms for bin packing: a survey. In: Hochbaum DS (ed) Approximation algorithms for np-hard problems. PWS, Boston, pp 46\u201393"},{"issue":"8","key":"140_CR4","doi-asserted-by":"crossref","first-page":"1003","DOI":"10.1016\/j.ic.2008.04.005","volume":"206","author":"JR Correa","year":"2008","unstructured":"Correa JR, Epstein L (2008) Bin packing with controllable item sizes. Inf Comput 206(8):1003\u20131016","journal-title":"Inf Comput"},{"key":"140_CR5","first-page":"339","volume-title":"Activity analysis of production and allocation","author":"GB Dantzig","year":"1951","unstructured":"Dantzig GB (1951) Maximization of a linear function of variables subject to linear inequalities. In: Koopmans TC (ed) Activity analysis of production and allocation. Wiley, London, pp 339\u2013347"},{"key":"140_CR6","unstructured":"D\u00f3sa G, Sgall J (2013) First fit bin packing: a tight analysis. In 30th symposium on theoretical aspects of computer science (STACS), pp 538\u2013549"},{"key":"140_CR7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tcs.2013.09.007","volume":"510","author":"G D\u00f3sa","year":"2013","unstructured":"D\u00f3sa G, Li R, Han X, Tuza Z (2013) Tight absolute bound for first fit decreasing bin-packing: \n                        $$FFD(I)\\le 11\/9OPT(I) + 6\/9$$\n                        \n                            \n                                            \n                                \n                                    F\n                                    F\n                                    D\n                                    (\n                                    I\n                                    )\n                                    \u2264\n                                    11\n                                    \/\n                                    9\n                                    O\n                                    P\n                                    T\n                                    (\n                                    I\n                                    )\n                                    +\n                                    6\n                                    \/\n                                    9\n                                \n                            \n                        \n                    . Theor Comput Sci 510:13\u201361","journal-title":"Theor Comput Sci"},{"issue":"4","key":"140_CR8","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega W, Lueker GS (1981) Bin packing can be solved within 1 + \n                        $$\\epsilon $$\n                        \n                            \n                                            \n                                \u03f5\n                            \n                        \n                     in linear time. Combinatorica 1(4):349\u2013355","journal-title":"Combinatorica"},{"issue":"1","key":"140_CR9","first-page":"222","volume":"15","author":"DK Friesen","year":"1986","unstructured":"Friesen DK, Langston MA (1986) Variable sized bin packing SIAM. J Comput 15(1):222\u2013230","journal-title":"J Comput"},{"key":"140_CR10","doi-asserted-by":"crossref","unstructured":"Garey MR, Graham RL, Ullman JD (1972) Worst-case analysis of memory allocation algorithms. Proceedings of the 4th annual ACM symposium on theory of computing STOC \u201972. Plenum Press, New York, pp 143\u2013150.","DOI":"10.1145\/800152.804907"},{"key":"140_CR11","volume-title":"Computers and intractability: a guide to the theory of np-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of np-completeness. W. H. Freeman and Co., San Francisco"},{"key":"140_CR12","volume-title":"Approximation algorithms for NP-hard problems","author":"DS Hochbaum","year":"1996","unstructured":"Hochbaum DS (1996) Approximation algorithms for NP-hard problems. PWS, Boston"},{"key":"140_CR13","unstructured":"Johnson D\u00a0S (1973) Near-optimal bin packing algorithms. Ph.D. thesis, MIT, Cambridge, MA"},{"issue":"4","key":"140_CR14","first-page":"299","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson DS, Demers A, Ullman JD, Garey MR, Graham RL (1974) Worst-case performance bounds for simple one-dimensional packing algorithms SIAM. J Comput 3(4):299\u2013325","journal-title":"J Comput"},{"issue":"4","key":"140_CR15","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4(4):373\u2013395","journal-title":"Combinatorica"},{"issue":"1","key":"140_CR16","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"LG Khachiyan","year":"1980","unstructured":"Khachiyan LG (1980) Polynomial algorithms in linear programming USSR. Comput Math Math Phys 20(1):53\u201372","journal-title":"Comput Math Math Phys"},{"key":"140_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial optimization: theory and algorithms","author":"B Korte","year":"2012","unstructured":"Korte B, Vygen J (2012) Combinatorial optimization: theory and algorithms, 4th edn. Springer, Berlin","edition":"4"},{"issue":"2","key":"140_CR18","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1016\/j.ejor.2016.02.028","volume":"253","author":"K Nip","year":"2016","unstructured":"Nip K, Wang Z, Wang Z (2016) Scheduling under linear constraints. Eur J Oper Res 253(2):290\u2013297","journal-title":"Eur J Oper Res"},{"issue":"1","key":"140_CR19","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1287\/moor.13.1.140","volume":"13","author":"WT Rhee","year":"1988","unstructured":"Rhee WT (1988) Optimal bin packing with items of random sizes. Math Oper Res 13(1):140\u2013151","journal-title":"Math Oper Res"},{"issue":"1","key":"140_CR20","first-page":"139","volume":"18","author":"WT Rhee","year":"1989","unstructured":"Rhee WT, Talagrand M (1989) Optimal bin packing with items of random sizes II SIAM. J Comput 18(1):139\u2013151","journal-title":"J Comput"},{"key":"140_CR21","unstructured":"Ullman JD (1971) The performance of a memory allocation algorithm. Technical report, Princeton University, Princeton"},{"key":"140_CR22","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032701","volume-title":"Interior point algorithms: theory and analysis","author":"Y Ye","year":"1997","unstructured":"Ye Y (1997) Interior point algorithms: theory and analysis. Wiley, London"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0140-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0140-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0140-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,10,9]],"date-time":"2017-10-09T07:44:37Z","timestamp":1507535077000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0140-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,25]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["140"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0140-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,5,25]]}}}