Abstract
We investigate the implications of the exponential time hypothesis on algorithms for scheduling and packing problems. Our main focus is to show tight lower bounds on the running time of these algorithms. For exact algorithms we investigate the dependence of the running time on the number n of items (for packing) or jobs (for scheduling). We show that many of these problems, including SubsetSum, Knapsack, BinPacking, 〈P2 | | C max 〉, and 〈P2 | | ∑ w j C j 〉, have a lower bound of 2o(n) × ∥ I ∥ O(1). We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2O(n) × ∥ I ∥ O(1). Finally, we show that there is no PTAS for MultipleKnapsack and 2d-Knapsack with running time \(2^{o}({\frac{1}{\epsilon }}) \times \parallel I \parallel^{O(1)}\) and \(n^{o({\frac{1}{\epsilon }})} \times \parallel{I}\parallel^{O(1)}\).
A full version of this work is available as technical report [18]. Research supported by German Research Foundation (DFG) projects JA 612/16-1 and JA 612/12-1.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Achugbue, J.O., Chin, F.Y.: Scheduling the open shop to minimize mean flow time. SIAM Journal on Computing 11(4), 709–720 (1982)
Caprara, A., Kellerer, H., Pferschy, U., Pisinger, D.: Approximation algorithms for knapsack problems with cardinality constraints. European Journal of Operational Research 123(2), 333–345 (2000)
Chen, J., et al.: On the computational hardness based on linear FPT-reductions. Journal of Combinatorial Optimization 11, 231–247 (2006)
Drozdowski, M.: On The Complexity of Multiprocessor Task Scheduling. Bulletin of the Polish Academy of Sciences. Technical Sciences 43(3), 381–392 (1995)
Du, J., Leung, J.Y.-T.: Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops. Journal of Algorithms 14(1), 24–44 (1993)
Ebenlendr, T., Krčál, 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–490. SIAM, Philadelphia (2008)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer (2010)
Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Mathematical Operations Research 1, 117–129 (1976)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Gonzalez, T., Sahni, S.: Flowshop and jobshop schedules: complexity and approximation. Operations Research 26(1), 36–52 (1978)
Held, M., Karp, R.: A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial and Applied Mathematics 10(1), 196–210 (1962)
Hoogeveen, H., Schuurman, P., Woeginger, G.J.: Non-approximability results for scheduling problems with minsum criteria. Journal on Computing 13(2), 157–168 (2001)
Horowitz, E., Sahni, S.: Computing Partitions with Applications to the Knapsack Problem. Journal of the ACM 21(2), 277–292 (1974)
Impagliazzo, R., Paturi, R.: On the Complexity of k-Sat. Journal of Computer and System Sciences 62(2), 367–375 (2001)
Impagliazzo, R., Paturi, R., Zane, F.: Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences 63(4), 512–530 (2001)
Jansen, K.: A Fast Approximation Scheme for the Multiple Knapsack Problem. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 313–324. Springer, Heidelberg (2012)
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)
Jansen, K., Kratsch, S., Marx, D., Schlotter, I.: Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences 79(1), 39–49 (2013)
Kulik, A., Shachnai, H.: There is no EPTAS for two-dimensional knapsack. Information Processing Letters 110 16, 707–710 (2010)
Lenstra, J.K., Rinnooy Kan, A.H.G.: Complexity of Scheduling under Precedence Constraints. Operations Research 26(1), 22–35 (1978)
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. 1, pp. 343–362. Elsevier (1977)
Lenté, C., Liedloff, M., Soukhal, A., T’kindt, 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)
Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS 105, 41–72 (2011)
Marx, D.: Parameterized complexity and approximation algorithms. The Computer Journal 51(1), 60–78 (2008)
O’Neil, 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–214. CSREA Press (2011)
O’Neil, 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–58. CSREA Press (2010)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43(3), 425–440 (1991)
Pătraşcu, 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–1075. SIAM, Philadelphia (2010)
Rinnooy Kan, A.H.G.: Machine scheduling problems: classification, complexity and computations. Stenfert Kroese (1976)
Wegener, I.: Complexity Theory: Exploring the Limits of Efficient Algorithms. Trans. from the German by R. J. Pruim. Springer (2003)
Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, C.A.J., Lenstra, J.K., Sevast’janov, S.V., Shmoys, D.B.: Short shop schedules. Operations Research 45(2), 288–294 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jansen, K., Land, F., Land, K. (2013). Bounding the Running Time of Algorithms for Scheduling and Packing Problems. In: Dehne, F., Solis-Oba, R., Sack, JR. (eds) Algorithms and Data Structures. WADS 2013. Lecture Notes in Computer Science, vol 8037. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40104-6_38
Download citation
DOI: https://doi.org/10.1007/978-3-642-40104-6_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40103-9
Online ISBN: 978-3-642-40104-6
eBook Packages: Computer ScienceComputer Science (R0)