1 citations · 1 across the 3 of their papers we have counts for
6 papers · 1 filter
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 of graph , the algorithms return an integral solution suc…
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" , where the goal is to select exactly one edge for each r…
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 of values to edges of graph , the algorit…
Simple and efficient four-cycle counting on sparse graphs
Paul Burkhardt, David G. Harris
We consider the problem of counting 4-cycles () in an undirected graph of vertices and edges (in bipartite graphs, 4-cycles are also often referred to as $\textit{…
Derandomizing the Lovasz Local Lemma via log-space statistical tests
David G. Harris
The Lovász Local Lemma (LLL) is a keystone principle in probability theory, guaranteeing the existence of configurations which avoid a collection of "bad" events which…
A Lottery Model for Center-type Problems With Outliers
David G. Harris, Thomas Pensyl, Aravind Srinivasan +1
In this paper, we give tight approximation algorithms for the -center and matroid center problems with outliers. Unfairness arises naturally in this setting: certain clients cou…