research
∙
10/25/2022
Efficient and Stable Fully Dynamic Facility Location
We consider the classic facility location problem in fully dynamic data ...
share
research
∙
03/28/2022
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems
Motivated by a real-world vehicle routing application, we consider the m...
research
∙
03/02/2022
Near-Optimal Correlation Clustering with Privacy
Correlation clustering is a central problem in unsupervised learning, wi...
research
∙
11/17/2021
Optimal Decremental Connectivity in Non-Sparse Graphs
We present a dynamic algorithm for maintaining the connected and 2-edge-...
research
∙
10/06/2021
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor
We consider the numerical taxonomy problem of fitting a positive distanc...
research
∙
06/15/2021
Correlation Clustering in Constant Many Parallel Rounds
Correlation clustering is a central topic in unsupervised learning, with...
research
∙
05/26/2021
New instances for maximum weight independent set from a vehicle routing application
We present a set of new instances of the maximum weight independent set ...
research
∙
01/07/2021
Planar Reachability Under Single Vertex or Edge Failures
In this paper we present an efficient reachability oracle under single-e...
research
∙
07/17/2020
All-Pairs LCA in DAGs: Breaking through the O(n^2.5) barrier
Let G=(V,E) be an n-vertex directed acyclic graph (DAG). A lowest common...
research
∙
05/22/2019
Dynamic Algorithms for the Massively Parallel Computation Model
The Massive Parallel Computing (MPC) model gained popularity during the ...
research
∙
01/28/2019
Dominating Sets and Connected Dominating Sets in Dynamic Graphs
In this paper we study the dynamic versions of two basic graph problems:...
research
∙
07/16/2018
Faster Algorithms for All-Pairs Bounded Min-Cuts
Given a directed graph, the vertex connectivity from u to v is the maxim...
research
∙
06/04/2018
Online Reciprocal Recommendation with Theoretical Performance Guarantees
A reciprocal recommendation problem is one where the goal of learning is...
research
∙
02/27/2018