From the 1 of 6 linked papers with an AI index.
6 papers
Causal Discovery in Mixtures of Populations
Bijan Mazaheri, Spencer Gordon, Yuval Rabani +1
The paper proposes a method to identify causal graphs in data that come from a mixture of a few latent populations, even when a global latent confounder is present, by using rank p…
-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids
Chris Gartland, Mikhail Ostrovskii, Yuval Rabani +1
We prove that the distortion of any embedding into of the transportation cost space or earth mover distance over a -dimensional grid is , whe…
Budget and Profit Approximations for Spanning Tree Interdiction
Rafail Ostrovsky, Yuval Rabani, Yoav Siman Tov
We give polynomial time logarithmic approximation guarantees for the budget minimization, as well as for the profit maximization versions of minimum spanning tree interdiction. In…
New Results on a General Class of Minimum Norm Optimization Problems
Kuowen Chen, Jian Li, Yuval Rabani +1
We study the general norm optimization for combinatorial problems, initiated by Chakrabarty and Swamy (STOC 2019). We propose a general formulation that captures a large class of c…
On Approximability of Min-Sum Clustering
Karthik C. S., Euiwoong Lee, Yuval Rabani +2
The min-sum -clustering problem is to partition an input set into clusters to minimize . Although $\ell_2^2…
Shortest Paths without a Map, but with an Entropic Regularizer
Sébastien Bubeck, Christian Coester, Yuval Rabani
In a 1989 paper titled "shortest paths without a map", Papadimitriou and Yannakakis introduced an online model of searching in a weighted layered graph for a target node, while att…