On the Hardness of Compressing Weights

Bart M. P. Jansen, Shivesh K. Roy, Michał Włodarczyk

We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the inst…