| Publication | Date of Publication | Type |
|---|
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 k -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 1
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 |
