4 papers
4-Block Integer Programming is in FPT
Martin Koutecký, Alexandra Lassota, Koen Ligthart
Integer programming is a fundamental and important NP-hard problem. This motivated extensive efforts in studying several tractable subclasses. One of the top unresolved complexity…
Computing Thiele Rules on Interval Elections and their Generalizations
Dimitris Avramidis, Alexandra Lassota, Ulrike Schmidt-Kraepelin +1
Approval-based committee voting has received significant attention in the social choice community. Among the studied rules, Thiele rules, and especially Proportional Approval Votin…
Tight Lower Bounds for Block-Structured Integer Programs
Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký +2
We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few…
Sometimes, Convex Separable Optimization Is Much Harder than Linear Optimization, and Other Surprises
Cornelius Brand, Martin Koutecký, Alexandra Lassota +1
An influential 1990 paper of Hochbaum and Shanthikumar made it common wisdom that "convex separable optimization is not much harder than linear optimization" [JACM 1990]. We exhibi…