Anita Dürr

most citedTight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling

1 citations · 1 across the 2 of their papers we have counts for

collaborators

3 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.DS2026★ 1 cited

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling

Karl Bringmann, Anita DÃ¼rr, Karol WÄgrzycki

Bin Packing with $k$ bins is a fundamental optimisation problem in which we are given a set of $n$ integers and a capacity $T$ and the goal is to partition the set into $k$ subsets…

cs.DS2026

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 + I ¨ }{2}})$ time algorithm to compute Monotone Min-Plus Product between two square matrices…