3 citations · 5 across the 4 of their papers we have counts for
9 papers
Online Correlation Clustering with Metric Weights
Sami Davies, Benjamin Moseley, Heather Newman
The standard online version of correlation clustering is prohibitively hard, as even randomized algorithms cannot achieve competitive ratio better than . Prior works bypass t…
Online Correlation Clustering: Simultaneously Optimizing All -norms
Sami Davies, Benjamin Moseley, Heather Newman
The -norm objectives for correlation clustering present a fundamental trade-off between minimizing total disagreements (the -norm) and ensuring fairness to individu…
Robust Gittins for Stochastic Scheduling
Benjamin Moseley, Heather Newman, Kirk Pruhs +1
A common theme in stochastic optimization problems is that, theoretically, stochastic algorithms need to "know" relatively rich information about the underlying distributions. This…
Simultaneously Approximating All -norms in Correlation Clustering
Sami Davies, Benjamin Moseley, Heather Newman
This paper considers correlation clustering on unweighted complete graphs. We give a combinatorial algorithm that returns a single clustering solution that is simultaneously …
Online -Median with Consistent Clusters
Benjamin Moseley, Heather Newman, Kirk Pruhs
We consider the online -median clustering problem in which points arrive online and must be irrevocably assigned to a cluster on arrival. As there are lower bound instances…
Fast Combinatorial Algorithms for Min Max Correlation Clustering
Sami Davies, Benjamin Moseley, Heather Newman
We introduce fast algorithms for correlation clustering with respect to the Min Max objective that provide constant factor approximations on complete graphs. Our algorithms are the…
Matroid-Based TSP Rounding for Half-Integral Solutions
Anupam Gupta, Euiwoong Lee, Jason Li +3
We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-1.5 factor. Such a rounding algorithm was recently given…
Uniform Edge Betweenness Centrality
Heather A. Newman, Hector Miranda, Rigoberto Florez +1
The edge betweenness centrality of an edge is loosely defined as the fraction of shortest paths between all pairs of vertices passing through that edge. In this paper, we investiga…
Edge-Transitive Graphs
Heather A. Newman, Hector Miranda, Darren A. Narayan
A graph is said to be edge-transitive if its automorphism group acts transitively on its edges. It is known that edge-transitive graphs are either vertex-transitive or bipartite. I…