1 citations · 1 across the 4 of their papers we have counts for
5 papers · 1 filter
Approximation Algorithms for -Shortest Path and -Group Steiner Tree
Yury Makarychev, Max Ovsiankin, Erasmo Tani
We present polylogarithmic approximation algorithms for variants of the Shortest Path, Group Steiner Tree, and Group ATSP problems with vector costs. In these problems, each edge e…
Learning-Based Algorithms for Graph Searching Problems
Adela Frances DePavia, Erasmo Tani, Ali Vakilian
We consider the problem of graph searching with prediction recently introduced by Banerjee et al. (2022). In this problem, an agent, starting at some vertex has to traverse a (…
Hypergraph Diffusions and Resolvents for Norm-Based Hypergraph Laplacians
Konstantinos Ameranis, Antares Chen, Adela DePavia +2
The development of simple and fast hypergraph spectral methods has been hindered by the lack of numerical algorithms for simulating heat diffusions and computing fundamental object…
Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle
Adela Frances DePavia, Olga Medrano Martín del Campo, Erasmo Tani
This paper initiates the study of active learning for exact recovery of partitions exclusively through access to a same-cluster oracle in the presence of bounded adversarial error.…
Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game
Antares Chen, Lorenzo Orecchia, Erasmo Tani
Despite there being significant work on developing spectral, and metric embedding based approximation algorithms for hypergraph generalizations of conductance, little is known rega…