5 Search Results for "Kaul, Matthias"

Document
DOI: 10.4230/LIPIcs.STACS.2025.47
Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines

Authors: Klaus Heeger and Hendrik Molter

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In this work, we study the computational (parameterized) complexity of P∣ r_j, p_j = p ∣∑ w_j U_j. Here, we are given m identical parallel machines and n jobs with equal processing time, each characterized by a release date, a due date, and a weight. The task is to find a feasible schedule, that is, an assignment of the jobs to starting times on machines, such that no job starts before its release date and no machine processes several jobs at the same time, that minimizes the weighted number of tardy jobs. A job is considered tardy if it finishes after its due date. Our main contribution is showing that P∣r_j, p_j = p∣∑ U_j (the unweighted version of the problem) is NP-hard and W[2]-hard when parameterized by the number of machines. The former resolves an open problem in Note 2.1.19 by Kravchenko and Werner [Journal of Scheduling, 2011] and Open Problem 2 by Sgall [ESA, 2012], and the latter resolves Open Problem 7 by Mnich and van Bevern [Computers & Operations Research, 2018]. Furthermore, our result shows that the known XP-algorithm by Baptiste et al. [4OR, 2004] for P∣r_j, p_j = p∣∑ w_j U_j parameterized by the number of machines is optimal from a classification standpoint. On the algorithmic side, we provide alternative running time bounds for the above-mentioned known XP-algorithm. Our analysis shows that P∣r_j, p_j = p∣∑ w_j U_j is contained in XP when parameterized by the processing time, and that it is contained in FPT when parameterized by the combination of the number of machines and the processing time. Finally, we give an FPT-algorithm for P∣r_j, p_j = p∣∑ w_j U_j parameterized by the number of release dates or the number of due dates. With this work, we lay out the foundation for a systematic study of the parameterized complexity of P∣r_j, p_j = p∣∑ w_j U_j.
Cite as

Klaus Heeger and Hendrik Molter. Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{heeger_et_al:LIPIcs.STACS.2025.47,
  author =	{Heeger, Klaus and Molter, Hendrik},
  title =	{{Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.47},
  URN =		{urn:nbn:de:0030-drops-228736},
  doi =		{10.4230/LIPIcs.STACS.2025.47},
  annote =	{Keywords: Scheduling, Identical Parallel Machines, Weighted Number of Tardy Jobs, Uniform Processing Times, Release Dates, NP-hard Problems, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.57
Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously

Authors: Matthias Kaul, Kelin Luo, Matthias Mnich, and Heiko Röglin

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We study the problem of partitioning a set of n objects in a metric space into k clusters V₁,...,V_k. The quality of the clustering is measured by considering the vector of cluster costs and then minimizing some monotone symmetric norm of that vector (in particular, this includes the 𝓁_p-norms). For the costs of the clusters we take the weight of a minimum-weight spanning tree on the objects in V_i, which may serve as a proxy for the cost of traversing all objects in the cluster, for example in the context of Multirobot Coverage as studied by Zheng, Koenig, Kempe, Jain (IROS 2005), but also as a shape-invariant measure of cluster density similar to Single-Linkage Clustering. This problem has been studied by Even, Garg, Könemann, Ravi, Sinha (Oper. Res. Lett., 2004) for the setting of minimizing the weight of the largest cluster (i.e., using 𝓁_∞) as Min-Max Tree Cover, for which they gave a constant-factor approximation algorithm. We provide a careful adaptation of their algorithm to compute solutions which are approximately optimal with respect to all monotone symmetric norms simultaneously, and show how to find them in polynomial time. In fact, our algorithm is purely combinatorial and can process metric spaces with 10,000 points in less than a second. As an extension, we also consider the case where instead of a target number of clusters we are provided with a set of depots in the space such that every cluster should contain at least one such depot. One can consider these as the fixed starting points of some agents that will traverse all points of a cluster. For this setting also we are able to give a polynomial-time algorithm computing a constant-factor approximation with respect to all monotone symmetric norms simultaneously. To show that the algorithmic results are tight up to the precise constant of approximation attainable, we also prove that such clustering problems are already APX-hard when considering only one single 𝓁_p norm for the objective.
Cite as

Matthias Kaul, Kelin Luo, Matthias Mnich, and Heiko Röglin. Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 57:1-57:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kaul_et_al:LIPIcs.STACS.2025.57,
  author =	{Kaul, Matthias and Luo, Kelin and Mnich, Matthias and R\"{o}glin, Heiko},
  title =	{{Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{57:1--57:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.57},
  URN =		{urn:nbn:de:0030-drops-228821},
  doi =		{10.4230/LIPIcs.STACS.2025.57},
  annote =	{Keywords: Clustering, spanning trees, all-norm approximation}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.19
Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates

Authors: Matthias Kaul, Matthias Mnich, and Hendrik Molter

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
We study the fundamental scheduling problem 1|r_j|∑ w_j U_j: schedule a set of n jobs with weights, processing times, release dates, and due dates on a single machine, such that each job starts after its release date and we maximize the weighted number of jobs that complete execution before their due date. Problem 1|r_j|∑ w_j U_j generalizes both Knapsack and Partition, and the simplified setting without release dates was studied by Hermelin et al. [Annals of Operations Research, 2021] from a parameterized complexity viewpoint. Our main contribution is a thorough complexity analysis of 1|r_j|∑ w_j U_j in terms of four key problem parameters: the number p_# of processing times, the number w_# of weights, the number d_# of due dates, and the number r_# of release dates of the jobs. 1|r_j|∑ w_j U_j is known to be weakly para-NP-hard even if w_#+d_#+r_# is constant, and Heeger and Hermelin [ESA, 2024] recently showed (weak) 𝖶[1]-hardness parameterized by p_# or w_# even if r_# is constant. Algorithmically, we show that 1|r_j|∑ w_j U_j is fixed-parameter tractable parameterized by p_# combined with any two of the remaining three parameters w_#, d_#, and r_#. We further provide pseudo-polynomial XP-time algorithms for parameter r_# and d_#. To complement these algorithms, we show that 1|r_j|∑ w_j U_j is (strongly) 𝖶[1]-hard when parameterized by d_#+r_# even if w_# is constant. Our results provide a nearly complete picture of the complexity of 1|r_j|∑ w_j U_j for p_#, w_#, d_#, and r_# as parameters, and extend those of Hermelin et al. [Annals of Operations Research, 2021] for the problem 1||∑ w_j U_j without release dates.
Cite as

Matthias Kaul, Matthias Mnich, and Hendrik Molter. Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kaul_et_al:LIPIcs.IPEC.2024.19,
  author =	{Kaul, Matthias and Mnich, Matthias and Molter, Hendrik},
  title =	{{Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.19},
  URN =		{urn:nbn:de:0030-drops-222450},
  doi =		{10.4230/LIPIcs.IPEC.2024.19},
  annote =	{Keywords: Scheduling, Release Dates, Fixed-Parameter Tractability}
}
Document
Survey
DOI: 10.4230/TGDK.1.1.4
Knowledge Graph Embeddings: Open Challenges and Opportunities

Authors: Russa Biswas, Lucie-Aimée Kaffee, Michael Cochez, Stefania Dumbrava, Theis E. Jendal, Matteo Lissandrini, Vanessa Lopez, Eneldo Loza Mencía, Heiko Paulheim, Harald Sack, Edlira Kalemi Vakaj, and Gerard de Melo

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
While Knowledge Graphs (KGs) have long been used as valuable sources of structured knowledge, in recent years, KG embeddings have become a popular way of deriving numeric vector representations from them, for instance, to support knowledge graph completion and similarity search. This study surveys advances as well as open challenges and opportunities in this area. For instance, the most prominent embedding models focus primarily on structural information. However, there has been notable progress in incorporating further aspects, such as semantics, multi-modal, temporal, and multilingual features. Most embedding techniques are assessed using human-curated benchmark datasets for the task of link prediction, neglecting other important real-world KG applications. Many approaches assume a static knowledge graph and are unable to account for dynamic changes. Additionally, KG embeddings may encode data biases and lack interpretability. Overall, this study provides an overview of promising research avenues to learn improved KG embeddings that can address a more diverse range of use cases.
Cite as

Russa Biswas, Lucie-Aimée Kaffee, Michael Cochez, Stefania Dumbrava, Theis E. Jendal, Matteo Lissandrini, Vanessa Lopez, Eneldo Loza Mencía, Heiko Paulheim, Harald Sack, Edlira Kalemi Vakaj, and Gerard de Melo. Knowledge Graph Embeddings: Open Challenges and Opportunities. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 4:1-4:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{biswas_et_al:TGDK.1.1.4,
  author =	{Biswas, Russa and Kaffee, Lucie-Aim\'{e}e and Cochez, Michael and Dumbrava, Stefania and Jendal, Theis E. and Lissandrini, Matteo and Lopez, Vanessa and Menc{\'\i}a, Eneldo Loza and Paulheim, Heiko and Sack, Harald and Vakaj, Edlira Kalemi and de Melo, Gerard},
  title =	{{Knowledge Graph Embeddings: Open Challenges and Opportunities}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:32},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.4},
  URN =		{urn:nbn:de:0030-drops-194783},
  doi =		{10.4230/TGDK.1.1.4},
  annote =	{Keywords: Knowledge Graphs, KG embeddings, Link prediction, KG applications}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.39
A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots

Authors: Max Deppert, Matthias Kaul, and Matthias Mnich

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial tours, to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot v₀, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. For this case, only a (2-1/d)-approximation in polynomial time is known, as well as a 3/2-approximation for constant d which requires a prohibitive run time of n^Θ(d) (Xu and Rodrigues, INFORMS J. Comput., 2015). A recent work of Traub, Vygen and Zenklusen (STOC 2020) gives another approximation algorithm for metric Multiple TSP with run time n^Θ(d), which reduces the problem to approximating metric TSP. In this paper we overcome the n^Θ(d) time barrier: we give the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Our algorithm runs in time (1/ε)^O(dlog d) ⋅ n^O(1), and produces a (3/2+ε)-approximation with constant probability. For the graphic case, we obtain a deterministic 3/2-approximation in time 2^d ⋅ n^O(1).
Cite as

Max Deppert, Matthias Kaul, and Matthias Mnich. A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{deppert_et_al:LIPIcs.ESA.2023.39,
  author =	{Deppert, Max and Kaul, Matthias and Mnich, Matthias},
  title =	{{A (3/2 + \epsilon)-Approximation for Multiple TSP with a Variable Number of Depots}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.39},
  URN =		{urn:nbn:de:0030-drops-186925},
  doi =		{10.4230/LIPIcs.ESA.2023.39},
  annote =	{Keywords: Traveling salesperson problem, rural postperson problem, multiple TSP, vehicle routing}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2024
  • 2 2023

  • Refine by Author
  • 3 Kaul, Matthias
  • 3 Mnich, Matthias
  • 2 Molter, Hendrik
  • 1 Biswas, Russa
  • 1 Cochez, Michael
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Computing methodologies → Machine learning approaches
  • 1 Computing methodologies → Planning and scheduling
  • 1 Computing methodologies → Semantic networks
  • 1 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 2 Release Dates
  • 2 Scheduling
  • 1 Clustering
  • 1 Fixed-Parameter Tractability
  • 1 Identical Parallel Machines
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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