3 papers
cs.DS2026
Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Bicriteria Optimality in 2D
Karl Bringmann, Ariel Kulik, Karol Węgrzycki
We revisit the -dimensional Vector Knapsack problem (-Knapsack): Given a -dimensional capacity vector and a set of items, each with a -dimensional weight vector and a p…
cs.DS2025
Beating Meet-in-the-Middle for Subset Balancing Problems
Tim Randolph, Karol Węgrzycki
We consider exact algorithms for Subset Balancing, a family of related problems that generalizes Subset Sum, Partition, and Equal Subset Sum. Specifically, given as input an intege…
cs.CG2025
On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
Sujoy Bhore, Baris Can Esmer, Daniel Marx +1
We study the Steiner Tree problem on the intersection graph of most natural families of geometric objects, e.g., disks, squares, polygons, etc. Given a set of objects in the pl…