1 citations · 1 across the 1 of their papers we have counts for
6 papers · 1 filter
A upper bound on the number of stable matchings
Ebrahim Ghorbani, Matthias Mnich
We study the maximum number of stable matchings in an instance with men and women. Karlin, Oveis Gharan, and Weber (STOC 2018) proved the first single-exponen…
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…