16 citations · 23 across the 2 of their papers we have counts for
6 papers
Nearly-Tight and Oblivious Algorithms for Explainable Clustering
Buddhima Gamlath, Xinrui Jia, Adam Polak +1
We study the problem of explainable clustering in the setting first formalized by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). A -clustering is said to be explainabl…
Approximating Star Cover Problems
Buddhima Gamlath, Vadim Grinberg
Given a metric space , we consider star covers of with balanced loads. A star is a pair where and , and the load of a star…
Beating Greedy for Stochastic Bipartite Matching
Buddhima Gamlath, Sagar Kale, Ola Svensson
We consider the maximum bipartite matching problem in stochastic settings, namely the query-commit and price-of-information models. In the query-commit model, an edge e independent…
Online Matching with General Arrivals
Buddhima Gamlath, Michael Kapralov, Andreas Maggiori +2
The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertice…
Weighted Matchings via Unweighted Augmentations
Buddhima Gamlath, Sagar Kale, Slobodan Mitrović +1
We design a generic method for reducing the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide eff…
Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
Buddhima Gamlath, Sangxia Huang, Ola Svensson
We study -means clustering in a semi-supervised setting. Given an oracle that returns whether two given points belong to the same cluster in a fixed optimal clustering, we inves…