5 citations · 7 across the 4 of their papers we have counts for
7 papers · 1 filter
Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries
Bernhard Haeupler, D Ellis Hershkowitz, Goran Zuzic
Embeddings of graphs into distributions of trees that preserve distances in expectation are a cornerstone of many optimization algorithms. Unfortunately, online or dynamic algorith…
Tree Embeddings for Hop-Constrained Network Design
Bernhard Haeupler, D Ellis Hershkowitz, Goran Zuzic
Network design problems aim to compute low-cost structures such as routes, trees and subgraphs. Often, it is natural and desirable to require that these structures have small hop l…
An Optimal Rounding for Half-Integral Weighted Minimum Strongly Connected Spanning Subgraph
D Ellis Hershkowitz, Gregory Kehne, R. Ravi
In the weighted minimum strongly connected spanning subgraph (WMSCSS) problem we must purchase a minimum-cost strongly connected spanning subgraph of a digraph. We show that half-i…
Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty
D Ellis Hershkowitz, R. Ravi, Sahil Singla
In this paper we study how to optimally balance cheap inflexible resources with more expensive, reconfigurable resources despite uncertainty in the input problem. Specifically, we…
Reverse Greedy is Bad for k-Center
D Ellis Hershkowitz, Gregory Kehne
We show the reverse greedy algorithm is between a - and a -approximation for -center.
Computation-Aware Data Aggregation
Bernhard Haeupler, D Ellis Hershkowitz, Anson Kahng +1
Data aggregation is a fundamental primitive in distributed computing wherein a network computes a function of every nodes' input. However, while compute time is non-negligible in m…