| Publication | Date of Publication | Type |
|---|
How to DP-fy your data: a practical guide to generating synthetic data with differential privacy
The Journal of Artificial Intelligence Research (JAIR) | 2026-07-31 | Paper |
| Recent progress on correlation clustering: from local algorithms to better approximation algorithms and back (invited talk) | 2026-05-26 | Paper |
Polynomial-time approximation schemes for facility location on planar graphs
SIAM Journal on Computing | 2025-09-16 | Paper |
| Planar and minor-free metrics embed into metrics of polylogarithmic treewidth with expected multiplicative distortion arbitrarily close to 1 | 2025-08-15 | Paper |
| Deterministic clustering in high dimensional spaces: sketches and approximation | 2025-08-15 | Paper |
| Handling correlated rounding error via preclustering: a 1.73-approximation for correlation clustering | 2025-08-15 | Paper |
| Streaming euclidean k-median and k-means with o( n) space | 2025-08-15 | Paper |
| Correlation clustering with Sherali-Adams | 2025-08-15 | Paper |
| The power of uniform sampling for coresets | 2025-08-15 | Paper |
| Fitting metrics and ultrametrics with minimum disagreements | 2025-08-15 | Paper |
| Fitting distances by tree metrics minimizing the total error within a constant factor | 2025-08-13 | Paper |
| On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs | 2025-08-12 | Paper |
| A polynomial-time approximation scheme for facility location on planar graphs | 2025-08-12 | Paper |
| Near-linear time approximations schemes for clustering in doubling metrics | 2025-08-12 | Paper |
| Inapproximability of clustering in Lp metrics | 2025-08-12 | Paper |
| Fast and compact exact distance oracle for planar graphs | 2025-08-06 | Paper |
| On the local structure of stable clustering instances | 2025-08-06 | Paper |
| Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics | 2025-08-06 | Paper |
Fitting distances by tree metrics minimizing the total error within a constant factor
Journal of the ACM | 2025-02-06 | Paper |
Fitting metrics and ultrametrics with minimum disagreements
SIAM Journal on Computing | 2025-01-23 | Paper |
| On complexity of 1-center in various metrics | 2025-01-14 | Paper |
| A PTAS for _0-low rank approximation: solving dense CSPs over reals | 2024-11-28 | Paper |
| Graph searching with predictions | 2024-09-25 | Paper |
A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
Mathematical Programming. Series A. Series B | 2024-08-20 | Paper |
| Johnson coverage hypothesis: inapproximability of k-means and k-median in _p-metrics | 2024-07-19 | Paper |
| An improved local search algorithm for k-median | 2024-07-19 | Paper |
| Improved approximation algorithms and lower bounds for search-diversification problems | 2024-06-24 | Paper |
| On the fine-grained complexity of approximating \(k\)-center in sparse graphs | 2024-05-14 | Paper |
| Streaming Euclidean MST to a constant factor | 2024-05-08 | Paper |
A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
scientific article; zbMATH DE number 7788494 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Bypassing the surface embedding: approximation schemes for network design in minor-free graphs
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Towards optimal lower bounds for k-median and k-means coresets
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Improved approximations for Euclidean <i>k</i> -means and <i>k</i> -median, via nested quasi-independent sets
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
A new coreset framework for clustering
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
A quasipolynomial (2 + <i>ε</i> )-approximation for planar sparsest cut
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
A Linear-Time <i>n</i> <sup>0.4</sup> -Approximation for Longest Common Subsequence
ACM Transactions on Algorithms | 2023-10-23 | Paper |
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
Journal of the ACM | 2022-12-08 | Paper |
Near-linear Time Approximation Schemes for Clustering in Doubling Metrics
Journal of the ACM | 2022-12-08 | Paper |
A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
(available as arXiv preprint) | 2022-08-16 | Paper |
On the fixed-parameter tractability of capacitated clustering
(available as arXiv preprint) | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7561535 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
Almost tight lower bounds for hard cutting problems in embedded graphs
(available as arXiv preprint) | 2022-07-18 | Paper |
Efficient approximation schemes for uniform-cost clustering problems in planar graphs
(available as arXiv preprint) | 2022-05-11 | Paper |
A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
SIAM Journal on Computing | 2021-02-08 | Paper |
Instance-Optimality in the Noisy Value-and Comparison-Model
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Approximation Schemes for Capacitated Clustering in Doubling Metrics
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
New hardness results for planar graph problems in p and an algorithm for sparsest cut
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
| On Efficient Low Distortion Ultrametric Embedding | 2020-08-15 | Paper |
Hierarchical clustering. Objective functions and algorithms
Journal of the ACM | 2020-02-11 | Paper |
Oblivious dimension reduction for \(k\)-means: beyond subspaces and the Johnson-Lindenstrauss lemma
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Lower bounds for text indexing with mismatches and differences
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Fast fencing
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
SIAM Journal on Computing | 2019-05-07 | Paper |
Hierarchical clustering: objective functions and algorithms
(available as arXiv preprint) | 2018-03-15 | Paper |
| Hierarchical clustering: objective functions and algorithms | 2018-03-15 | Paper |
A fast approximation scheme for low-dimensional k-means
(available as arXiv preprint) | 2018-03-15 | Paper |
| A fast approximation scheme for low-dimensional k-means | 2018-03-15 | Paper |
scientific article; zbMATH DE number 6850339 (Why is no real title available?)
(available as arXiv preprint) | 2018-03-15 | Paper |
| scientific article; zbMATH DE number 6850339 (Why is no real title available?) | 2018-03-15 | Paper |
| A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals | 2018-03-15 | Paper |
| scientific article; zbMATH DE number 6820208 (Why is no real title available?) | 2017-12-19 | Paper |
Effectiveness of local search for geometric optimization
(available as arXiv preprint) | 2017-10-10 | Paper |
Approximating connectivity domination in weighted bounded-genus graphs
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Steinberg's conjecture is false
Journal of Combinatorial Theory. Series B | 2016-11-25 | Paper |
Algorithmic aspects of switch cographs
Discrete Applied Mathematics | 2016-01-21 | Paper |
Energy-efficient algorithms for non-preemptive speed-scaling
Approximation and Online Algorithms | 2015-11-20 | Paper |
A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
Algorithms - ESA 2015 | 2015-11-19 | Paper |
