research
∙
08/02/2023
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
A spanning tree T of graph G is a ρ-approximate universal Steiner tree (...
share
research
∙
04/18/2023
Parallel Greedy Spanners
A t-spanner of a graph is a subgraph that t-approximates pairwise distan...
research
∙
11/02/2021
Fast Algorithms for Hop-Constrained Flows and Moving Cuts
Hop-constrained flows and their duals, moving cuts, are two fundamental ...
research
∙
10/07/2021
Bad-Policy Density: A Measure of Reinforcement Learning Hardness
Reinforcement learning is hard in general. Yet, in many specific environ...
research
∙
04/01/2021
O(1) Steiner Point Removal in Series-Parallel Graphs
We study how to vertex-sparsify a graph while preserving both the graph'...
research
∙
02/11/2021
District-Fair Participatory Budgeting
Participatory budgeting is a method used by city governments to select p...
research
∙
02/09/2021
Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries
Embeddings of graphs into distributions of trees that preserve distances...
research
∙
11/11/2020
Tree Embeddings for Hop-Constrained Network Design
Network design problems aim to compute low-cost structures such as route...
research
∙
11/11/2020
An Optimal Rounding for Half-Integral Weighted Minimum Strongly Connected Spanning Subgraph
In the weighted minimum strongly connected spanning subgraph (WMSCSS) pr...
research
∙
12/31/2019
Near-Optimal Schedules for Simultaneous Multicasts
We study the store-and-forward packet routing problem for simultaneous m...
research
∙
11/28/2018
Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty
In this paper we study how to optimally balance cheap inflexible resourc...
research
∙
10/03/2018
Reverse Greedy is Bad for k-Center
We demonstrate that the reverse greedy algorithm is a Θ(k) approximation...
research
∙
06/14/2018
A Computational Approach to Organizational Structure
An organizational structure defines how an organization arranges and man...
research
∙
05/10/2018
Erasure Correction for Noisy Radio Networks
The radio network model is a well-studied abstraction for modeling wirel...
research
∙
01/16/2018
Round- and Message-Optimal Distributed Graph Algorithms
Distributed graph algorithms that separately optimize for either the num...
research
∙
01/16/2018
Round- and Message-Optimal Distributed Part-Wise Aggregation
Distributed graph algorithms that separately optimize for either the num...
research
∙
01/15/2017