Anita Dürr

activity

20232026

collaborators

4 papers

cs.DS2026

Faster Exponential Algorithms for Multi-Machine Scheduling Problems

Anubhav Dhar, Anita Dürr, Ahmed Ghazy +2

Minimizing the weighted completion times ( $P ∣∣ Σ w_{j} C_{j}$ ) and weighted number of tardy jobs ( $P ∣∣ Σ w_{j} U_{j}$ ) on multiple identical machines are two classical NP-har…

cs.DS2025

Faster algorithms for k-Orthogonal Vectors in low dimension

Anita Dürr, Evangelos Kipouridis, Michael Lampis +1

In the Orthogonal Vectors problem (OV), we are given two families $A, B$ of subsets of ${1, \dots, d}$ , each of size $n$ , and the task is to decide whether there exists a pair $a…

cs.DS2024

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing

Karl Bringmann, Anita Dürr, Adam Polak

We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time $O (n + t p_{m a x})$ , where $n$ is the number of items, $t$ is the knap…

cs.DS2023

An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs

Anita Dürr, Nicolas El Maalouly, Lasse Wulf

In 1982 Papadimitriou and Yannakakis introduced the Exact Matching problem, in which given a red and blue edge-colored graph $G$ and an integer $k$ one has to decide whether there…