Matthias Mnich

collaborators

3 papers

cs.DS2025

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously

Matthias Kaul, Kelin Luo, Matthias Mnich +1

We study the problem of partitioning a set of $n$ objects in a metric space into $k$ clusters $V_{1}, \dots, V_{k}$ . The quality of the clustering is measured by considering the vector o…

cs.DS2024

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates

Matthias Kaul, Matthias Mnich, Hendrik Molter

We study the fundamental scheduling problem $1 ∣ r_{j} ∣ \sum w_{j} U_{j}$ : schedule a set of $n$ jobs with weights, processing times, release dates, and due dates on a single machine…

cs.DS2024

A $(\frac{3}{2} + \frac{1}{e})$ -Approximation Algorithm for Ordered TSP

Susanne Armbruster, Matthias Mnich, Martin Nägele

We present a new $(\frac{3}{2} + \frac{1}{e})$ -approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metri…

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates

A (23​+e1​)-Approximation Algorithm for Ordered TSP

A $(\frac{3}{2} + \frac{1}{e})$ -Approximation Algorithm for Ordered TSP