Sami Davies
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Sami Davies has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
Benjamin Moseley
Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
1 shared publication- Heather Newman
Carnegie Mellon University, Pittsburgh, PA, USA
1 shared publication - Venkatesan Guruswami
University of California at Berkeley, Berkeley, USA
1 shared publication - Xuandi Ren
UC Berkeley, Berkeley, CA, USA
1 shared publication
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 486-489
Brief Announcement: Scheduling Problems with Constrained Rejections
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 486-489
Open AccessBrief Announcement: Scheduling Problems with Constrained Rejections
- 10 September 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Fast Combinatorial Algorithms for Simultaneously Approximating All ℓp-Norms in Correlation Clustering
We design the first purely combinatorial [ ]-factor algorithms for correlation clustering with respect to the [ ]-norm of the disagreement vector. Our main technical contribution is the construction of a novel semimetric on the set of vertices, which we call the correlation metric, that indicates to our clustering algorithms whether pairs of nodes should be in the same cluster. The power of the correlation metric allows us to design an algorithm that outputs a single clustering solution that is simultaneously [ ]-approximate for all [ ]-norms, thus proving that minimal sacrifice is needed in order to optimize different norms. Our algorithms are also faster than those in all previous works, with runtime [ ], for [ ] the running time for matrix multiplication on [ ] matrices. Further, the runtime improves to [ ], when the maximum positive degree in the graph is at most [ ]. Funding: B. Moseley and H. Newman were supported in part by a Google Research Award, an Infor Research Award, a Carnegie Bosch Junior Faculty Chair, NSF Division of Computing and Communication Foundations [Grants CCF-2121744 and CCF-1845146], and the Office of Naval Research Global [Grant N000142212702].
- 10 September 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Fast Combinatorial Algorithms for Simultaneously Approximating All ℓp-Norms in Correlation Clustering
We design the first purely combinatorial [ ]-factor algorithms for correlation clustering with respect to the [ ]-norm of the disagreement vector. Our main technical contribution is the construction of a novel semimetric on the set of vertices, which we call the correlation metric, that indicates to our clustering algorithms whether pairs of nodes should be in the same cluster. The power of the correlation metric allows us to design an algorithm that outputs a single clustering solution that is simultaneously [ ]-approximate for all [ ]-norms, thus proving that minimal sacrifice is needed in order to optimize different norms. Our algorithms are also faster than those in all previous works, with runtime [ ], for [ ] the running time for matrix multiplication on [ ] matrices. Further, the runtime improves to [ ], when the maximum positive degree in the graph is at most [ ]. Funding: B. Moseley and H. Newman were supported in part by a Google Research Award, an Infor Research Award, a Carnegie Bosch Junior Faculty Chair, NSF Division of Computing and Communication Foundations [Grants CCF-2121744 and CCF-1845146], and the Office of Naval Research Global [Grant N000142212702].