Published in Algorithmica, Volume 87, pages 1340–1368, 2025
We study fair repetitive interval scheduling, showing NP-hardness under natural restrictions and providing algorithmic and parameterized results for several tractable cases.
Recommended citation: Heeger, K., Hermelin, D., Itzhaki, Y., Molter, H. and Shabtay, D., 2025. Fair Repetitive Interval Scheduling. Algorithmica, 87, pp. 1340–1368.
Download Paper | Download Slides | Download Bibtex
Published in Journal of Computer and System Sciences, Volume 144, p.103533., 2024
We show W[1]-hardness for the number of machines \(m\) in Interval Scheduling with Eligible Machines, prove NP-hardness for bounded \(p_{\max}\), and give an FPT algorithm for the combined parameter \(p_{\max} + m\).
Recommended citation: Hermelin, D., Itzhaki, Y., Molter, H. and Shabtay, D., 2024. On the parameterized complexity of interval scheduling with eligible machine sets. Journal of Computer and System Sciences, 144, p.103533.
Download Paper | Download Slides | Download Bibtex
Published in Theoretical Computer Science, Volume 961, p.113885., 2023
We give hardness, approximation, and parameterized results for Temporal Clique and Temporal Independent Set on temporal interval graphs.
Recommended citation: Hermelin, D., Itzhaki, Y., Molter, H. and Niedermeier, R., 2023. Temporal interval cliques and independent sets. Theoretical Computer Science, 961, p.113885.
Download Paper | Download Bibtex
Published in 17th International Symposium on Parameterized and Exact Computation (IPEC 2022), 2022
Hardness results for Interval Scheduling on Unrelated Machines, including W[1]-hardness in the machine parameter and NP-completeness of the unweighted case.
Recommended citation: Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Dvir Shabtay. Hardness of Interval Scheduling on Unrelated Machines. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Download Paper | Download Bibtex
Published in 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), 2022
We study the complexity of finding large independent sets in temporal unit interval graphs, and obtain hardness, constant-factor approximation, and fixed-parameter tractability results.
Recommended citation: Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Rolf Niedermeier. Temporal Unit Interval Independent Sets. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Download Paper | Download Slides | Download Bibtex