research
∙
04/19/2023
The Price of Explainability for Clustering
Given a set of points in d-dimensional space, an explainable clustering ...
share
research
∙
11/16/2022
The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
Given a graph with edges colored red or blue and an integer k, the exact...
research
∙
04/11/2022
Submodular Maximization Subject to Matroid Intersection on the Fly
Despite a surge of interest in submodular maximization in the data strea...
research
∙
02/15/2022
A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem
The Matching Augmentation Problem (MAP) has recently received significan...
research
∙
02/04/2022
Flow Time Scheduling and Prefix Beck-Fiala
We relate discrepancy theory with the classic scheduling problems of min...
research
∙
10/06/2021
Towards Non-Uniform k-Center with Constant Types of Radii
In the Non-Uniform k-Center problem we need to cover a finite metric spa...
research
∙
07/15/2021
Streaming Submodular Maximization with Matroid and Matching Constraints
Recent progress in (semi-)streaming algorithms for monotone submodular f...
research
∙
07/14/2021
A QPTAS for stabbing rectangles
We consider the following geometric optimization problem: Given n axis-a...
research
∙
06/30/2021
Nearly-Tight and Oblivious Algorithms for Explainable Clustering
We study the problem of explainable clustering in the setting first form...
research
∙
02/08/2021
Semi-Streaming Algorithms for Submodular Matroid Intersection
While the basic greedy algorithm gives a semi-streaming algorithm with a...
research
∙
12/22/2020
Fast and Accurate k-means++ via Rejection Sampling
k-means++ <cit.> is a widely used clustering algorithm that is easy to i...
research
∙
11/13/2020
Consistent k-Clustering for General Metrics
Given a stream of points in a metric space, is it possible to maintain a...
research
∙
10/22/2020
The Primal-Dual method for Learning Augmented Algorithms
The extension of classical online algorithms when provided with predicti...
research
∙
10/22/2020
Learning Augmented Energy Minimization via Speed Scaling
As power management has become a primary concern in modern data centers,...
research
∙
07/08/2020
Fair Colorful k-Center Clustering
An instance of colorful k-center consists of points in a metric space th...
research
∙
04/27/2020
Robust Algorithms under Adversarial Injections
In this paper, we study streaming and online algorithms in the context o...
research
∙
03/30/2020
The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness
We consider the classical problem of maximizing a monotone submodular fu...
research
∙
09/27/2019
Beating Greedy for Stochastic Bipartite Matching
We consider the maximum bipartite matching problem in stochastic setting...
research
∙
05/04/2019
New Notions and Constructions of Sparsification for Graphs and Hypergraphs
A sparsifier of a graph G (Benczúr and Karger; Spielman and Teng) is a s...
research
∙
04/17/2019
Online Matching with General Arrivals
The online matching problem was introduced by Karp, Vazirani and Vaziran...
research
∙
11/07/2018
Weighted Matchings via Unweighted Augmentations
We design a generic method for reducing the task of finding weighted mat...
research
∙
08/06/2018
Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams
Many tasks in machine learning and data mining, such as data diversifica...
research
∙
03/02/2018
Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
We study k-means clustering in a semi-supervised setting. Given an oracl...
research
∙
01/26/2018