1 citations · 1 across the 1 of their papers we have counts for
5 papers
A deterministic -approximation for directed feedback vertex sets in tournaments
Ebrahim Ghorbani, Matthias Mnich
We nearly settle the polynomial-time approximability of the Directed Feedback Vertex Set problem in tournaments. This problem is Vertex Cover-hard, and thus cannot have a $(2 - \va…
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 objects in a metric space into clusters . The quality of the clustering is measured by considering the vector o…
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 : schedule a set of jobs with weights, processing times, release dates, and due dates on a single machine…
A -Approximation Algorithm for Ordered TSP
Susanne Armbruster, Matthias Mnich, Martin Nägele
We present a new -approximation algorithm for the Ordered Traveling Salesperson Problem (Ordered TSP). Ordered TSP is a variant of the classical metri…
Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding
Ariel Kulik, Matthias Mnich, Hadas Shachnai
We study the -dimensional Vector Bin Packing (VBP) problem, a generalization of Bin Packing with central applications in resource allocation and scheduling. In VBP, we are…