| Publication | Date of Publication | Type |
|---|
| Dimension reduction in the _1 norm | 2026-05-29 | Paper |
| On the impossibility of dimension reduction in _1 | 2026-05-29 | Paper |
| Clustering with qualitative information | 2026-05-29 | Paper |
| Maximizing quadratic programs: extending Grothendieck's inequality | 2026-05-29 | Paper |
| On the integrality ratio for asymmetric TSP | 2026-05-29 | Paper |
| Combinatorial feature selection problems | 2026-05-08 | Paper |
| Improved combinatorial algorithms for the facility location and k-median problems | 2026-05-06 | Paper |
| A model for ant trail formation and its convergence properties (extended abstract) | 2026-04-15 | Paper |
| The finite capacity dial-a-ride problem | 2025-10-29 | Paper |
| Approximating a finite metric by a small number of tree metrics | 2025-10-29 | Paper |
| Almost 3-approximate correlation clustering in constant rounds | 2025-08-15 | Paper |
| Multiway online correlated selection | 2025-08-13 | Paper |
| Kernel density estimation through density constrained near neighbor search | 2025-08-12 | Paper |
| Multi-resolution hashing for fast pairwise summations | 2025-08-12 | Paper |
| Efficient density evaluation for smooth kernels | 2025-08-12 | Paper |
| Hashing-based-estimators for kernel density in high dimensions | 2025-08-06 | Paper |
| Vertex sparsifiers and abstract rounding algorithms | 2025-04-29 | Paper |
Breaking the metric voting distortion barrier
Journal of the ACM | 2025-04-25 | Paper |
Distributed algorithms from arboreal ants for the shortest path problem
Proceedings of the National Academy of Sciences of the United States of America | 2025-03-06 | Paper |
On-line load balancing for related machines
Lecture Notes in Computer Science | 2022-08-19 | Paper |
Constrained TSP and low-power computing
Lecture Notes in Computer Science | 2022-08-19 | Paper |
| scientific article; zbMATH DE number 7559216 (Why is no real title available?) | 2022-07-18 | Paper |
| Min-cost bipartite perfect matching with delays | 2021-07-28 | Paper |
scientific article; zbMATH DE number 7375961 (Why is no real title available?)
(available as arXiv preprint) | 2021-07-28 | Paper |
| Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier | 2021-07-28 | Paper |
Resilience: a criterion for learning in the presence of arbitrary outliers
(available as arXiv preprint) | 2021-06-15 | Paper |
The one-way communication complexity of dynamic time warping distance
(available as arXiv preprint) | 2021-03-17 | Paper |
Efficient profile maximum likelihood for universal symmetric property estimation
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Hierarchical clustering better than average-linkage
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
(available as arXiv preprint) | 2019-05-10 | Paper |
| Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph | 2019-05-10 | Paper |
Approximate hierarchical clustering via sparsest cut and spreading metrics
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| On approximating target set selection | 2018-04-19 | Paper |
The hardness of approximation of Euclidean k-means
(available as arXiv preprint) | 2017-10-10 | Paper |
| Tight hardness results for minimizing discrepancy | 2017-09-29 | Paper |
Local guarantees in graph cuts and clustering
(available as arXiv preprint) | 2017-08-31 | Paper |
Learning from untrusted data
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Multireference alignment using semidefinite programming
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
Relax, no need to round: integrality of clustering formulations
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
On targeting Markov segments
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Spectral embedding of \(k\)-cliques, graph partitioning and \(k\)-means
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Aggregating inconsistent information: ranking and clustering
Journal of the ACM | 2015-11-11 | Paper |
| scientific article; zbMATH DE number 6472577 (Why is no real title available?) | 2015-08-14 | Paper |
Smoothed analysis of tensor decompositions
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Approximating min-sum <i>k</i> -clustering in metric spaces
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Clustering to minimize the sum of cluster diameters
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Integrality gaps for Sherali-Adams relaxations
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
MaxMin allocation via degree lower-bounded arborescences
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
| scientific article; zbMATH DE number 6381632 (Why is no real title available?) | 2014-12-18 | Paper |
| A divide and conquer algorithm for d-dimensional arrangement | 2014-12-18 | Paper |
Near-optimal algorithms for unique games
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Near-optimal algorithms for maximum constraint satisfaction problems
ACM Transactions on Algorithms | 2014-11-18 | Paper |
| Approximating the average response time in broadcast scheduling | 2014-10-13 | Paper |
| A tight threshold for metric Ramsey phenomena | 2014-10-13 | Paper |
Query strategies for priced information (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
A dependent LP-rounding approach for the k-median problem
Automata, Languages, and Programming | 2013-08-12 | Paper |
On quadratic programming with a ratio objective
Automata, Languages, and Programming | 2013-08-12 | Paper |
Fitting Tree Metrics: Hierarchical Clustering and Phylogeny
SIAM Journal on Computing | 2012-02-11 | Paper |
Beating the random ordering is hard: every ordering CSP is approximation resistant
SIAM Journal on Computing | 2011-10-18 | Paper |
Improved approximation algorithms for label cover problems
Algorithmica | 2011-08-16 | Paper |
Embedding the Ulam metric into \(\ell_{1}\)
Theory of Computing | 2011-05-24 | Paper |
Local global tradeoffs in metric embeddings
SIAM Journal on Computing | 2011-01-17 | Paper |
A robust maximum completion time measure for scheduling
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Directed metrics and directed graph partitioning problems
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
\(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Aggregating inconsistent information
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Better streaming algorithms for clustering problems
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
On non-uniform multicommodity buy-at-bulk network design
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Approximating the smallest grammar
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Similarity estimation techniques from rounding algorithms
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Improved Approximation Algorithms for Label Cover Problems
Lecture Notes in Computer Science | 2009-10-29 | Paper |
Improved approximation for directed cut problems
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing | 2009-01-05 | Paper |
On the impossibility of dimension reduction in l <sub>1</sub>
Journal of the ACM | 2008-12-21 | Paper |
The Smallest Grammar Problem
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
Mathematics of Operations Research | 2008-05-27 | Paper |
A derandomization using min-wise independent permutations
Journal of Discrete Algorithms | 2007-04-26 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
Clustering with qualitative information
Journal of Computer and System Sciences | 2005-10-10 | Paper |
Improved Combinatorial Algorithms for Facility Location Problems
SIAM Journal on Computing | 2005-09-16 | Paper |
Minimizing Wirelength in Zero and Bounded Skew Clock Trees
SIAM Journal on Discrete Mathematics | 2005-02-28 | Paper |
Incremental Clustering and Dynamic Information Retrieval
SIAM Journal on Computing | 2005-02-21 | Paper |
| scientific article; zbMATH DE number 2119717 (Why is no real title available?) | 2004-11-29 | Paper |
Clustering to minimize the sum of cluster diameters
Journal of Computer and System Sciences | 2004-11-22 | Paper |
| scientific article; zbMATH DE number 2086643 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 1775395 (Why is no real title available?) | 2004-01-27 | Paper |
A constant-factor approximation algorithm for the k-median problem
Journal of Computer and System Sciences | 2003-05-04 | Paper |
Delayed information and action in on-line algorithms
Information and Computation | 2003-01-14 | Paper |
| scientific article; zbMATH DE number 1775418 (Why is no real title available?) | 2002-09-17 | Paper |
Query strategies for priced information
Journal of Computer and System Sciences | 2002-09-12 | Paper |
| scientific article; zbMATH DE number 1775420 (Why is no real title available?) | 2002-08-01 | Paper |
Algorithms for capacitated vehicle routing
SIAM Journal on Computing | 2002-04-23 | Paper |
On page migration and other relaxed task systems
Theoretical Computer Science | 2002-03-03 | Paper |
| Algorithms for facility location problems with outliers. (Extended abstract) | 2002-01-30 | Paper |
| scientific article; zbMATH DE number 1559578 (Why is no real title available?) | 2001-02-28 | Paper |
On-Line Load Balancing for Related Machines
Journal of Algorithms | 2000-10-04 | Paper |
Min-wise independent permutations
Journal of Computer and System Sciences | 2000-08-27 | Paper |
| scientific article; zbMATH DE number 1303582 (Why is no real title available?) | 2000-06-21 | Paper |
Approximation Algorithms for Directed Steiner Problems
Journal of Algorithms | 2000-05-28 | Paper |
| scientific article; zbMATH DE number 1303557 (Why is no real title available?) | 1999-06-17 | Paper |
| scientific article; zbMATH DE number 1305406 (Why is no real title available?) | 1999-06-17 | Paper |
