{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:23:39Z","timestamp":1726410219906},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_38","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T01:36:30Z","timestamp":1373506590000},"page":"439-450","source":"Crossref","is-referenced-by-count":10,"title":["Bounding the Running Time of Algorithms for Scheduling and Packing Problems"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[]},{"given":"Felix","family":"Land","sequence":"additional","affiliation":[]},{"given":"Kati","family":"Land","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"38_CR1","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1137\/0211058","volume":"11","author":"J.O. Achugbue","year":"1982","unstructured":"Achugbue, J.O., Chin, F.Y.: Scheduling the open shop to minimize mean flow time. SIAM Journal on Computing\u00a011(4), 709\u2013720 (1982)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"38_CR2","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0377-2217(99)00261-1","volume":"123","author":"A. Caprara","year":"2000","unstructured":"Caprara, A., Kellerer, H., Pferschy, U., Pisinger, D.: Approximation algorithms for knapsack problems with cardinality constraints. European Journal of Operational Research\u00a0123(2), 333\u2013345 (2000)","journal-title":"European Journal of Operational Research"},{"key":"38_CR3","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10878-006-7137-6","volume":"11","author":"J. Chen","year":"2006","unstructured":"Chen, J., et al.: On the computational hardness based on linear FPT-reductions. Journal of Combinatorial Optimization\u00a011, 231\u2013247 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"38_CR4","first-page":"381","volume":"43","author":"M. Drozdowski","year":"1995","unstructured":"Drozdowski, M.: On The Complexity of Multiprocessor Task Scheduling. Bulletin of the Polish Academy of Sciences. Technical Sciences\u00a043(3), 381\u2013392 (1995)","journal-title":"Bulletin of the Polish Academy of Sciences. Technical Sciences"},{"issue":"1","key":"38_CR5","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jagm.1993.1002","volume":"14","author":"J. Du","year":"1993","unstructured":"Du, J., Leung, J.Y.-T.: Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops. Journal of Algorithms\u00a014(1), 24\u201344 (1993)","journal-title":"Journal of Algorithms"},{"key":"38_CR6","first-page":"483","volume-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"T. Ebenlendr","year":"2008","unstructured":"Ebenlendr, T., Kr\u010d\u00e1l, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. In: Teng, S.-H. (ed.) Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 483\u2013490. SIAM, Philadelphia (2008)"},{"key":"38_CR7","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"38_CR9","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Mathematical Operations Research\u00a01, 117\u2013129 (1976)","journal-title":"Mathematical Operations Research"},{"key":"38_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"1","key":"38_CR11","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/opre.26.1.36","volume":"26","author":"T. Gonzalez","year":"1978","unstructured":"Gonzalez, T., Sahni, S.: Flowshop and jobshop schedules: complexity and approximation. Operations Research\u00a026(1), 36\u201352 (1978)","journal-title":"Operations Research"},{"issue":"1","key":"38_CR12","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.: A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial and Applied Mathematics\u00a010(1), 196\u2013210 (1962)","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"issue":"2","key":"38_CR13","first-page":"157","volume":"13","author":"H. Hoogeveen","year":"2001","unstructured":"Hoogeveen, H., Schuurman, P., Woeginger, G.J.: Non-approximability results for scheduling problems with minsum criteria. Journal on Computing\u00a013(2), 157\u2013168 (2001)","journal-title":"Journal on Computing"},{"issue":"2","key":"38_CR14","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing Partitions with Applications to the Knapsack Problem. Journal of the ACM\u00a021(2), 277\u2013292 (1974)","journal-title":"Journal of the ACM"},{"issue":"2","key":"38_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the Complexity of k-Sat. Journal of Computer and System Sciences\u00a062(2), 367\u2013375 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"38_CR16","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-642-27660-6_26","volume-title":"SOFSEM 2012: Theory and Practice of Computer Science","author":"K. Jansen","year":"2012","unstructured":"Jansen, K.: A Fast Approximation Scheme for the Multiple Knapsack Problem. In: Bielikov\u00e1, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur\u00e1n, G. (eds.) SOFSEM 2012. LNCS, vol.\u00a07147, pp. 313\u2013324. Springer, Heidelberg (2012)"},{"key":"38_CR18","first-page":"439","volume-title":"Lecture Notes in Computer Science","author":"Klaus Jansen","year":"2013","unstructured":"Jansen, K., Land, K., Land, F.: Bounding the Running Time of Algorithms for Scheduling and Packing Problems. Technical Report 1302. Institute of Computer Science, University of Kiel, Germany (2013)"},{"issue":"1","key":"38_CR19","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jcss.2012.04.004","volume":"79","author":"K. Jansen","year":"2013","unstructured":"Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences\u00a079(1), 39\u201349 (2013)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR20","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/j.ipl.2010.05.031","volume":"16","author":"A. Kulik","year":"2010","unstructured":"Kulik, A., Shachnai, H.: There is no EPTAS for two-dimensional knapsack. Information Processing Letters 110\u00a016, 707\u2013710 (2010)","journal-title":"Information Processing Letters 110"},{"issue":"1","key":"38_CR21","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J.K. Lenstra","year":"1978","unstructured":"Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of Scheduling under Precedence Constraints. Operations Research\u00a026(1), 22\u201335 (1978)","journal-title":"Operations Research"},{"key":"38_CR22","doi-asserted-by":"crossref","unstructured":"Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of Machine Scheduling Problems. In: Hammer, P., Johnson, E., Korte, B., Nemhauser, G. (eds.) Studies in Integer Programming. Annals of Discrete Mathematics, vol.\u00a01, pp. 343\u2013362. Elsevier (1977)","DOI":"10.1016\/S0167-5060(08)70743-X"},{"key":"38_CR23","unstructured":"Lent\u00e9, C., Liedloff, M., Soukhal, A., T\u2019kindt, V.: Exponential-time algorithms for scheduling problems. In: 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2011), Nymburk, Czech Republic (2011)"},{"key":"38_CR24","first-page":"41","volume":"105","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS\u00a0105, 41\u201372 (2011)","journal-title":"Bulletin of the EATCS"},{"issue":"1","key":"38_CR25","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D. Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal\u00a051(1), 60\u201378 (2008)","journal-title":"The Computer Journal"},{"key":"38_CR26","unstructured":"O\u2019Neil, T.E.: Sub-Exponential Algorithms for 0\/1-Knapsack and Bin Packing. In: Arabnia, H.R., Gravvanis, G.A., Solo, A.M.G. (eds.) Proceedings of the 2011 International Conference on Foundations of Computer Science, pp. 209\u2013214. CSREA Press (2011)"},{"key":"38_CR27","unstructured":"O\u2019Neil, T.E., Kerlin, S.: A simple 2 $^{O(\\sqrt{x})}$ -algorithm for Partition and Subset Sum. In: Arabnia, H.R., Gravvanis, G.A., Solo, A.M.G. (eds.) Proceedings of the 2010 International Conference on Foundations of Computer Science, pp. 55\u201358. CSREA Press (2010)"},{"issue":"3","key":"38_CR28","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043(3), 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR29","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1137\/1.9781611973075.86","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M. P\u0103tra\u015fcu","year":"2010","unstructured":"P\u0103tra\u015fcu, M., Williams, R.: On the possibility of faster Sat algorithms. In: Charikar, M. (ed.) Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1065\u20131075. SIAM, Philadelphia (2010)"},{"key":"38_CR30","unstructured":"Rinnooy Kan, A.H.G.: Machine scheduling problems: classification, complexity and computations. Stenfert Kroese (1976)"},{"key":"38_CR31","unstructured":"Wegener, I.: Complexity Theory: Exploring the Limits of Efficient Algorithms. Trans. from the German by R. J. Pruim. Springer (2003)"},{"issue":"2","key":"38_CR32","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1287\/opre.45.2.288","volume":"45","author":"D.P. Williamson","year":"1997","unstructured":"Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, C.A.J., Lenstra, J.K., Sevast\u2019janov, S.V., Shmoys, D.B.: Short shop schedules. Operations Research\u00a045(2), 288\u2013294 (1997)","journal-title":"Operations Research"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,17]],"date-time":"2019-07-17T21:09:53Z","timestamp":1563397793000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}