7 papers
A Simple Algorithm for Counting Solutions to Integer Programs
Daniel Dadush, Anita Dürr, Thekla Hamm +2
We consider the problem of counting solutions to integer linear programming problems of the form where $A \in \{-Δ,\ldots,Δ\}^{m \times n…
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…
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…
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…
Computing Generalized Convolutions Faster Than Brute Force
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
In this paper, we consider a general notion of convolution. Let be a finite domain and let be the set of -length vectors (tuples) of . Let be…