Karol Węgrzycki

collaborators

2 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

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…