Anita Dürr

activity

20222026

collaborators

6 papers

cs.CC2026

A Simple Algorithm for Counting Solutions to Integer Programs

Daniel Dadush, Anita Dürr, Thekla Hamm +2

We consider the problem of counting solutions to integer linear programming problems of the form ${x \in Z_{\geq 0}^{n} : A x = b}$ where $A \in \{-Δ,\ldots,Δ\}^{m \times n…

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…

cs.DS2022

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications

Anita Dürr

In a recent breakthrough paper, Chi et al. (STOC'22) introduce an $O ~ (n^{\frac{3 + ω}{2}})$ time algorithm to compute Monotone Min-Plus Product between two square matrices o…