David G. Harris

activity

20242026

collaborators

8 papers

cs.DS2026

A note on rounding fractional matchings with constant-factor strong negative correlation

David G. Harris

We describe new dependent-rounding algorithms for bipartite graphs. Given a fractional matching $x$ of graph $G = (U \cup V, E)$ , the algorithms return an integral solution $X$ suc…

math.CO2026

The singleton hypergraph is extremal for the Isolation Lemma

Vance Faber, David G. Harris

Let $H$ be an inclusion-free hypergraph on $n$ vertices. A weight assignment $w : [n] \to [d]$ is isolating if there is a unique edge $e$ whose weight $w (e) = \sum_{i \in e} w (i)$ is m…

cs.DS2026

The Dirichlet Mechanism for rounding with strong negative correlation, with applications

David G. Harris, George Z. Li, Nitya Raju +1

Many optimization and scheduling problems can be abstracted in terms of a bipartite ``assignment graph" $G = (U \cup V, E)$ , where the goal is to select exactly one edge for each r…

cs.DS2025

A faster algorithm for Vertex Cover parameterized by solution size

David G. Harris, N. S. Narayanaswamy

We describe a new algorithm for vertex cover with runtime $O^{*} (1.2528 4^{k})$ , where $k$ is the size of the desired solution and $O^{*}$ hides polynomial factors in the input size. This…

cs.DS2025

Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time

David G. Harris

We describe a new dependent-rounding algorithmic framework for bipartite graphs. Given a fractional assignment $x$ of values to edges of graph $G = (U \cup V, E)$ , the algorit…

cs.DS2025

A new notion of commutativity for the algorithmic LovÃ¡sz Local Lemma

David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov

The LovÃ¡sz Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakth…