Document Open Access Logo

Scheduling Kernels via Configuration LP

Authors Dušan Knop, Martin Koutecký

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.73.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Dušan Knop
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
Martin Koutecký
  • Computer Science Institute of Charles University, Prague, Czech Republic

Funding

  • Knop, Dušan: Supported by the OP VVV MEYS funded project "Research Center for Informatics" (nr. CZ.02.1.01/0.0/0.0/16_019/0000765).
  • Koutecký, Martin: Partially supported by Charles University project UNCE/SCI/004, by the Czech Science Foundation (GA ČR) project 19-27871X, and by the Israel Science Foundation grant 308/18.

Acknowledgements

Authors wish to thank the Lorentz Center for making it possible to organize the workshop Scheduling Meets Fixed-Parameter Tractability, which output resulted in this paper. The contribution of the Lorentz Center in stimulating suggestions, giving feedback and taking care of all practicalities, helped us to focus on our research and to organize a meeting of high scientific quality. Furthermore, the authors thank Stefan Kratsch for bringing Proposition 5 to their attention.

Cite AsGet BibTex

Dušan Knop and Martin Koutecký. Scheduling Kernels via Configuration LP. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.73

Abstract

Makespan minimization (on parallel identical or unrelated machines) is arguably the most natural and studied scheduling problem. A common approach in practical algorithm design is to reduce the size of a given instance by a fast preprocessing step while being able to recover key information even after this reduction. This notion is formally studied as kernelization (or simply, kernel) - a polynomial time procedure which yields an equivalent instance whose size is bounded in terms of some given parameter. It follows from known results that makespan minimization parameterized by the longest job processing time p_max has a kernelization yielding a reduced instance whose size is exponential in p_max. Can this be reduced to polynomial in p_max? We answer this affirmatively not only for makespan minimization, but also for the (more complicated) objective of minimizing the weighted sum of completion times, also in the setting of unrelated machines when the number of machine kinds is a parameter. Our algorithm first solves the Configuration LP and based on its solution constructs a solution of an intermediate problem, called huge N-fold integer programming. This solution is further reduced in size by a series of steps, until its encoding length is polynomial in the parameters. Then, we show that huge N-fold IP is in NP, which implies that there is a polynomial reduction back to our scheduling problem, yielding a kernel. Our technique is highly novel in the context of kernelization, and our structural theorem about the Configuration LP is of independent interest. Moreover, we show a polynomial kernel for huge N-fold IP conditional on whether the so-called separation subproblem can be solved in polynomial time. Considering that integer programming does not admit polynomial kernels except for quite restricted cases, our "conditional kernel" provides new insight.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Integer programming
Keywords
  • Scheduling
  • Kernelization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Iskander Aliev, Jesús A. De Loera, Friedrich Eisenbrand, Timm Oertel, and Robert Weismantel. The support of integer optimal solutions. SIAM Journal on Optimization, 28(3):2152-2157, 2018. Google Scholar
  2. Matthias Bentert, René van Bevern, Till Fluschnik, André Nichterlein, and Rolf Niedermeier. Polynomial-time preprocessing for weighted problems beyond additive goal functions. CoRR, abs/1910.00277, 2019. URL: http://arxiv.org/abs/1910.00277.
  3. Hans L. Bodlaender and Michael R. Fellows. W[2]-hardness of precedence constrained k-processor scheduling. Operations Research Letters, 18(2):93-97, 1995. URL: https://doi.org/10.1016/0167-6377(95)00031-9.
  4. Robert Bredereck, Andrzej Kaczmarczyk, Dušan Knop, and Rolf Niedermeier. High-multiplicity fair allocation: Lenstra empowered by n-fold integer programming. In Anna Karlin, Nicole Immorlica, and Ramesh Johari, editors, Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019, pages 505-523. ACM, 2019. URL: https://doi.org/10.1145/3328526.3329649.
  5. Laurent Bulteau, Danny Hermelin, Dušan Knop, Anthony Labarre, and Stéphane Vialette. The clever shopper problem. Theory of Computing Systems, 64(1):17-34, 2020. URL: https://doi.org/10.1007/s00224-019-09917-z.
  6. Liming Cai, Jianer Chen, Rodney G. Downey, and Michael R. Fellows. Advice classes of parameterized tractability. Annal of Pure Appliled Logic, 84(1):119-138, 1997. URL: https://doi.org/10.1016/S0168-0072(95)00020-8.
  7. Timothy Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král, and Kristýna Pekárková. A row-invariant parameterized algorithm for integer programming. CoRR, abs/1907.06688, 2019. URL: http://arxiv.org/abs/1907.06688.
  8. Steven Chaplick, Fedor V. Fomin, Petr A. Golovach, Dušan Knop, and Peter Zeman. Kernelization of graph hamiltonicity: Proper h-graphs. In Zachary Friggstad, Jörg-Rüdiger Sack, and Mohammad R. Salavatipour, editors, Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, volume 11646 of Lecture Notes in Computer Science, pages 296-310. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24766-9_22.
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  10. Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein. Faster algorithms for integer programs with block structure. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 49:1-49:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.49.
  11. Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin, and Shmuel Onn. An algorithmic theory of integer programming. CoRR, abs/1904.01361, 2019. URL: http://arxiv.org/abs/1904.01361.
  12. Friedrich Eisenbrand and Gennady Shmonin. Carathéodory bounds for integer cones. Operations Research Letters, 34(5):564-568, 2006. Google Scholar
  13. Michael Etscheid, Stefan Kratsch, Matthias Mnich, and Heiko Röglin. Polynomial kernels for weighted problems. Journal of Computer and System Sciences, 84:1-10, 2017. URL: https://doi.org/10.1016/j.jcss.2016.06.004.
  14. Michael R. Fellows and Catherine McCartin. On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 298(2):317-324, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00811-3.
  15. Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: theory of parameterized preprocessing. Cambridge University Press, 2019. Google Scholar
  16. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. Google Scholar
  17. Tomáš Gavenčiak, Dušan Knop, and Martin Koutecký. Integer programming in parameterized complexity: Three miniatures. In Christophe Paul and Michal Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland, volume 115 of LIPIcs, pages 21:1-21:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.21.
  18. P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem. Operations Research, 9:849-859, 1961. Google Scholar
  19. Steffen Goebbels, Frank Gurski, Jochen Rethmann, and Eda Yilmaz. Change-making problems revisited: a parameterized point of view. Journal of Combinatorial Optimization, 34(4):1218-1236, November 2017. URL: https://doi.org/10.1007/s10878-017-0143-z.
  20. Michel X. Goemans and Thomas Rothvoß. Polynomiality for bin packing with a constant number of item types. In Proc. SODA 2014, pages 830-839, 2014. Google Scholar
  21. Frank Gurski, Carolin Rehs, and Jochen Rethmann. Knapsack problems: A parameterized point of view. Theoretical Compututer Science, 775:93-108, 2019. URL: https://doi.org/10.1016/j.tcs.2018.12.019.
  22. Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard J. Woeginger. Scheduling two competing agents when one agent has significantly fewer jobs. In Thore Husfeldt and Iyad A. Kanj, editors, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, volume 43 of LIPIcs, pages 55-65. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.IPEC.2015.55.
  23. Danny Hermelin, Michael Pinedo, Dvir Shabtay, and Nimrod Talmon. On the parameterized tractability of single machine scheduling with rejection. European Journal of Operational Research, 273(1):67-73, 2019. URL: https://doi.org/10.1016/j.ejor.2018.07.038.
  24. Danny Hermelin, Dvir Shabtay, and Nimrod Talmon. On the parameterized tractability of the just-in-time flow-shop scheduling problem. Journal of Scheduling, 22(6):663-676, 2019. URL: https://doi.org/10.1007/s10951-019-00617-7.
  25. D. S. Hochbaum and J. G. Shantikumar. Convex separable optimization is not much harder than linear optimization. J. ACM, 37(4):843-862, 1990. Google Scholar
  26. Bart M. P. Jansen and Stefan Kratsch. A structural approach to kernels for ilps: Treewidth and total unimodularity. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 779-791. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48350-3_65.
  27. Klaus Jansen, Marten Maack, and Roberto Solis-Oba. Structural parameters for scheduling with assignment restrictions. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, volume 10236 of Lecture Notes in Computer Science, pages 357-368, 2017. URL: https://doi.org/10.1007/978-3-319-57586-5_30.
  28. Narendra Karmarkar and Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, FOCS '82, pages 312-320, Washington, DC, USA, 1982. IEEE Computer Society. Google Scholar
  29. Dušan Knop and Martin Koutecký. Scheduling meets n-fold integer programming. Journal of Scheduling, 21:493-503, 2018. Google Scholar
  30. Dušan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, and Shmuel Onn. Multitype integer monoid optimization and applications. CoRR, abs/1909.07326, 2019. URL: http://arxiv.org/abs/1909.07326.
  31. Dušan Knop, Martin Koutecký, and Matthias Mnich. Combinatorial n-fold integer programming and applications. Mathematical Programming, November 2019. URL: https://doi.org/10.1007/s10107-019-01402-2.
  32. Dušan Knop, Martin Koutecký, and Matthias Mnich. Voting and bribing in single-exponential time. ACM Transactions on Economics and Computation, 8(3), June 2020. URL: https://doi.org/10.1145/3396855.
  33. Martin Koutecký, Asaf Levin, and Shmuel Onn. A parameterized strongly polynomial algorithm for block structured integer programs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 85:1-85:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.85.
  34. Stefan Kratsch. On polynomial kernels for integer linear programs: Covering, packing and feasibility. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, volume 8125 of Lecture Notes in Computer Science, pages 647-658. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40450-4_55.
  35. Stefan Kratsch. On polynomial kernels for sparse integer linear programs. Journal of Computer and System Sciences, 82(5):758-766, 2016. URL: https://doi.org/10.1016/j.jcss.2015.12.002.
  36. Daniel Lokshtanov, Fahad Panolan, MS Ramanujan, and Saket Saurabh. Lossy kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 224-237, 2017. Google Scholar
  37. Matthias Mnich and René van Bevern. Parameterized complexity of machine scheduling: 15 open problems. Computers & Operations Research, 100:254-261, 2018. Google Scholar
  38. Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. Math. Program., 154(1-2):533-562, 2015. Google Scholar
  39. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. URL: https://doi.org/10.1093/ACPROF:OSO/9780198566076.001.0001.
  40. Guntram Scheithauer and Johannes Terno. The modified integer round-up property of the one-dimensional cutting stock problem. European Journal of Operational Research, 84(3):562-571, 1995. Google Scholar
  41. René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. On (1+backslashvarepsilon)-approximate data reduction for the rural postman problem. In Michael Khachay, Yury Kochetov, and Panos M. Pardalos, editors, Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Ekaterinburg, Russia, July 8-12, 2019, Proceedings, volume 11548 of Lecture Notes in Computer Science, pages 279-294. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-22629-9_20.
  42. René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. Parameterized algorithms and data reduction for the short secluded s-t-path problem. Networks, 75(1):34-63, 2020. URL: https://doi.org/10.1002/net.21904.
  43. René van Bevern, Matthias Mnich, Rolf Niedermeier, and Mathias Weller. Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5):449-469, 2015. URL: https://doi.org/10.1007/s10951-014-0398-5.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact