Karol Wkegrzycki

collaborators

3 papers

cs.DS2024

Space-Efficient Algorithm for Integer Programming with Few Constraints

Lars Rohwedder, Karol Węgrzycki

Integer linear programs $min {c^{T} x : A x = b, x \in Z_{\geq 0}^{n}}$ , where $A \in Z^{m \times n}$ , $b \in Z^{m}$ , and $c \in Z^{n}$ , can be solved…

cs.DS2024

Fine-Grained Equivalence for Problems Related to Integer Linear Programming

Lars Rohwedder, Karol Węgrzycki

Integer Linear Programming with $n$ binary variables and $m$ many $0/1$ -constraints can be solved in time $2^{O ~ (m^{2})} poly (n)$ and it is open whether the dependence o…

cs.DS2021

Knapsack and Subset Sum with Small Items

Adam Polak, Lars Rohwedder, Karol Węgrzycki

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomi…