Vincent Cohen-Addad

Alessandro Epasto

Silvio Lattanzi

CoRR, 2024

A PTAS for ℓ0-Low Rank Approximation: Solving Dense CSPs over Reals.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018).

[BibT_eX]

[DOI]

SIAM J. Comput., December, 2023

A Linear-Time n0.4-Approximation for Longest Common Subsequence.

[BibT_eX]

[DOI]

Karl Bringmann

Debarati Das

ACM Trans. Algorithms, January, 2023

A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies.

[BibT_eX]

[DOI]

CoRR, 2023

A PTAS for 𝓁0-Low Rank Approximation: Solving Dense CSPs over Reals.

[BibT_eX]

[DOI]

CoRR, 2023

Streaming Euclidean MST to a Constant Factor.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

On the Fine-Grained Complexity of Approximating k-Center in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Private estimation algorithms for stochastic block models and mixture models.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Multi-Swap k-Means++.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Graph Searching with Predictions.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Differentially Private Hierarchical Clustering with Provable Approximation Guarantees.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Streaming Euclidean k-median and k-means with o(log n) Space.

[BibT_eX]

[DOI]

David P. Woodruff

Samson Zhou

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

On Complexity of 1-Center in Various Metrics.

[BibT_eX]

[DOI]

Amir Abboud

MohammadHossein Bateni

Saeed Seddighin

Proceedings of the Approximation, 2023

2022

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median.

[BibT_eX]

[DOI]

CoRR, 2022

Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy.

[BibT_eX]

[DOI]

Limor Gultchin

Sophie Giffard-Roisin

CoRR, 2022

Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets.

[BibT_eX]

[DOI]

CoRR, 2022

Towards optimal lower bounds for k-median and k-means coresets.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Bypassing the surface embedding: approximation schemes for network design in minor-free graphs.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

An Improved Local Search Algorithm for k-Median.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees.

[BibT_eX]

[DOI]

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Improved Coresets for Euclidean k-Means.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Near-Optimal Correlation Clustering with Privacy.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Near-Optimal Private and Scalable $k$-Clustering.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Scalable Differentially Private Clustering via Hierarchically Separated Trees.

[BibT_eX]

[DOI]

Proceedings of the KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14, 2022

A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time.

[BibT_eX]

[DOI]

Tobias Mömke

Victor Verdugo

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Massively Parallel k-Means Clustering for Perturbation Resilient Instances.

[BibT_eX]

[DOI]

Vahab S. Mirrokni

Peilin Zhong

Proceedings of the International Conference on Machine Learning, 2022

Online and Consistent Correlation Clustering.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Correlation Clustering with Sherali-Adams.

[BibT_eX]

[DOI]

Alantha Newman

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Fitting Metrics and Ultrametrics with Minimum Disagreements.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

The Power of Uniform Sampling for Coresets.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Community Recovery in the Degree-Heterogeneous Stochastic Block Model.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

On Facility Location Problem in the Local Differential Privacy Model.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals.

[BibT_eX]

[DOI]

Éric Colin de Verdière

Arnaud de Mesmay

SIAM J. Comput., 2021

Mitigating COVID-19 outbreaks in workplaces and schools by hybrid telecommuting.

[BibT_eX]

[DOI]

PLoS Comput. Biol., 2021

Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.

[BibT_eX]

[DOI]

Éric Colin de Verdière

Dániel Marx

Arnaud de Mesmay

J. ACM, 2021

Near-linear Time Approximation Schemes for Clustering in Doubling Metrics.

[BibT_eX]

[DOI]

Andreas Emil Feldmann

J. ACM, 2021

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics.

[BibT_eX]

[DOI]

CoRR, 2021

A Linear-Time n0.4-Approximation for Longest Common Subsequence.

[BibT_eX]

[DOI]

Karl Bringmann

Debarati Das

CoRR, 2021

A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut.

[BibT_eX]

[DOI]

CoRR, 2021

A new coreset framework for clustering.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

A quasipolynomial (2 + ε)-approximation for planar sparsest cut.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

On Approximability of Clustering Problems Without Candidate Centers.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Parallel and Efficient Hierarchical k-Median Clustering.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Improving Ultrametrics Embeddings Through Coresets.

[BibT_eX]

[DOI]

Rémi de Joannis de Verclos

Guillaume Lagarde

Proceedings of the 38th International Conference on Machine Learning, 2021

Correlation Clustering in Constant Many Parallel Rounds.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting.

[BibT_eX]

[DOI]

Proceedings of the 2nd Symposium on Foundations of Responsible Computing, 2021

Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Online k-means Clustering.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

On the computational tractability of a geographic clustering problem arising in redistricting.

[BibT_eX]

[DOI]

Dániel Marx

CoRR, 2020

New hardness results for planar graph problems in p and an algorithm for sparsest cut.

[BibT_eX]

[DOI]

Amir Abboud

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Instance-Optimality in the Noisy Value-and Comparison-Model.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Approximation Schemes for Capacitated Clustering in Doubling Metrics.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Fast and Accurate $k$-means++ via Rejection Sampling.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

On the Power of Louvain in the Stochastic Block Model.

[BibT_eX]

[DOI]

Adrian Kosowski

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

On Efficient Low Distortion Ultrametric Embedding.

[BibT_eX]

[DOI]

Guillaume Lagarde

Proceedings of the 37th International Conference on Machine Learning, 2020

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Hierarchical Clustering: Objective Functions and Algorithms.

[BibT_eX]

[DOI]

J. ACM, 2019

Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Lower bounds for text indexing with mismatches and differences.

[BibT_eX]

[DOI]

Laurent Feuilloley

Tatiana Starikovskaya

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Fully Dynamic Consistent Facility Location.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Subquadratic High-Dimensional Hierarchical Clustering.

[BibT_eX]

[DOI]

Amir Abboud

Hussein Houdrouge

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

On the Fixed-Parameter Tractability of Capacitated Clustering.

[BibT_eX]

[DOI]

Jason Li

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Tight FPT Approximations for k-Median and k-Means.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics.

[BibT_eX]

[DOI]

Andreas Emil Feldmann

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Inapproximability of Clustering in Lp Metrics.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs.

[BibT_eX]

[DOI]

Michal Pilipczuk

Marcin Pilipczuk

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs.

[BibT_eX]

[DOI]

Marcin Pilipczuk

Michal Pilipczuk

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Instance-Optimality in the Noisy Value-and Comparison-Model - Accept, Accept, Strong Accept: Which Papers get in?

[BibT_eX]

[DOI]

CoRR, 2018

Fast fencing.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Bane of Low-Dimensionality Clustering.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A Fast Approximation Scheme for Low-Dimensional k-Means.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Balanced centroidal power diagrams for redistricting.

[BibT_eX]

[DOI]

Neal E. Young

Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2018

2017

Steinberg's Conjecture is false.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2017

Balanced power diagrams for redistricting.

[BibT_eX]

[DOI]

Neal E. Young

CoRR, 2017

A Fast Approximation Scheme for Low-Dimensional k-Means.

[BibT_eX]

[DOI]

CoRR, 2017

One Size Fits All : Effectiveness of Local Search on Structured Data.

[BibT_eX]

[DOI]

CoRR, 2017

Hierarchical Clustering Beyond the Worst-Case.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

On the Local Structure of Stable Clustering Instances.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Fast and Compact Exact Distance Oracle for Planar Graphs.

[BibT_eX]

[DOI]

Søren Dahlgaard

Christian Wulff-Nilsen

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Online Optimization of Smoothed Piecewise Constant Functions.

[BibT_eX]

[DOI]

Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017

2016

Algorithmic aspects of switch cographs.

[BibT_eX]

[DOI]

Michel Habib

Fabien de Montgolfier

Discret. Appl. Math., 2016

The power of local search for clustering.

[BibT_eX]

[DOI]

CoRR, 2016

Approximating connectivity domination in weighted bounded-genus graphs.

[BibT_eX]

[DOI]

Éric Colin de Verdière

David Meierfrankenfeld

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

The Invisible Hand of Dynamic Market Pricing.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Conference on Economics and Computation, 2016

Diameter and k-Center in Sliding Windows.

[BibT_eX]

[DOI]

Christian Sohler

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface.

[BibT_eX]

[DOI]

Arnaud de Mesmay

Proceedings of the Algorithms - ESA 2015, 2015

Effectiveness of Local Search for Geometric Optimization.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014

The Unreasonable Success of Local Search: Geometric Optimization.

[BibT_eX]

[DOI]