4 papers · 1 filter
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…
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…
Faster algorithms for k-Orthogonal Vectors in low dimension
Anita Dürr, Evangelos Kipouridis, Michael Lampis +1
In the Orthogonal Vectors problem (OV), we are given two families of subsets of , each of size , and the task is to decide whether there exists a pair $a…
Hitting Meets Packing: How Hard Can it Be?
Jacob Focke, Fabian Frei, Shaohua Li +4
We study a general family of problems that form a common generalization of classic hitting (also referred to as covering or transversal) and packing problems. An instance of X-HitP…