Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Learning Low Degree Hypergraphs
Eric Balkanski, Oussama Hanguir, Shatian Wang
We study the problem of learning a hypergraph via edge detecting queries. In this problem, a learner queries subsets of vertices of a hidden hypergraph and observes whether these s…
cs.GT2024
Randomized Strategic Facility Location with Predictions
Eric Balkanski, Vasilis Gkatzelis, Golnoosh Shahkarami
In the strategic facility location problem, a set of agents report their locations in a metric space and the goal is to use these reports to open a new facility, minimizing an aggr…
cs.DS2024
Submodular Maximization in Exactly Queries
Eric Balkanski, Steven DiSilvio, Alan Kuhnle +1
In this work, we study the classical problem of maximizing a submodular function subject to a matroid constraint. We develop deterministic algorithms that are very parsimonious wit…