111 citations · 131 across the 17 of their papers we have counts for
18 papers · 1 filter
Improved Parallel Algorithms for EF1 Allocations
Kishen N Gowda, D Ellis Hershkowitz, Richard Z Huang +1
Allocating indivisible goods among agents is a fundamental task in fair division. Recent work of Garg and Psomas [AAMAS 2025] initiated the study of parallel algorithms for…
The Steiner Path Aggregation Problem
Da Qi Chen, Daniel Hathcock, D Ellis Hershkowitz +1
In the Steiner Path Aggregation Problem, our goal is to aggregate paths in a directed network into a single arborescence without significantly disrupting the paths. In particular,…
Parallel Hierarchical Agglomerative Clustering in Low Dimensions
MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher +4
Hierarchical Agglomerative Clustering (HAC) is an extensively studied and widely used method for hierarchical clustering in based on repeatedly merging the closest p…
Simple Length-Constrained Minimum Spanning Trees
D Ellis Hershkowitz, Richard Z Huang
In the length-constrained minimum spanning tree (MST) problem, we are given an -node edge-weighted graph and a length constraint . Our goal is to find a spanning t…
Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li +2
We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flow…
Efficient Centroid-Linkage Clustering
MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher +4
We give an efficient algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a -approximate clustering in roughly time. We ob…
New Structures and Algorithms for Length-Constrained Expander Decompositions
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
Expander decompositions form the basis of one of the most flexible paradigms for close-to-linear-time graph algorithms. Length-constrained expander decompositions generalize this p…
It's Hard to HAC with Average Linkage!
MohammadHossein Bateni, Laxman Dhulipala, Kishen N Gowda +3
Average linkage Hierarchical Agglomerative Clustering (HAC) is an extensively studied and applied method for hierarchical clustering. Recent applications to massive datasets have d…
Ghost Value Augmentation for -Edge-Connectivity
D Ellis Hershkowitz, Nathan Klein, Rico Zenklusen
We give a poly-time algorithm for the -edge-connected spanning subgraph (-ECSS) problem that returns a solution of cost no greater than the cheapest -ECSS on the same…
Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast
Bernhard Haeupler, D Ellis Hershkowitz, Thatchaphol Saranurak
Computing routing schemes that support both high throughput and low latency is one of the core challenges of network optimization. Such routes can be formalized as -length flows…
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…
Near-Optimal Schedules for Simultaneous Multicasts
Bernhard Haeupler, D Ellis Hershkowitz, David Wajc
We study the store-and-forward packet routing problem for simultaneous multicasts, in which multiple packets have to be forwarded along given trees as fast as possible. This is a n…
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…
Erasure Correction for Noisy Radio Networks
Keren Censor-Hillel, Bernhard Haeupler, D Ellis Hershkowitz +1
The radio network model is a well-studied model of wireless, multi-hop networks. However, radio networks make the strong assumption that messages are delivered deterministically. T…