6 papers
Maximum-Cost Strategic Facility Location: The Limits of Randomization
Jabari Hastings, Misha Ivkov
We consider strategic facility location in Euclidean space , where a mechanism selects a single facility based on the reported locations of agents and seeks to min…
Optimal Metric Distortion for Learning-Augmented Matching on the Line
Jabari Hastings, Marena Richter
We revisit the problem of matching on the line with ordinal preferences. In the classic setting, there are agents and items in a shared unknown line metric, and the goal is…
Strategic Facility Location with -Norm Social Costs
Jabari Hastings
We consider the strategic facility location problem in spaces where the social cost is defined by an arbitrary -norm of the individual costs. While the opt…
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
Sumegha Garg, Jabari Hastings, Chirag Pabbaraju +1
We present a unified framework for proving memory lower bounds for multi-pass streaming algorithms that detect planted structures. Planted structures -- such as cliques or biclique…
Fair metric distortion for matching with preferences
Jabari Hastings, Prasanna Ramakrishnan
We consider the matching problem in the metric distortion framework. There are agents and items occupying points in a shared metric space, and the goal is to design a match…
Wedge-Lifted Codes
Jabari Hastings, Amy Kanne, Ray Li +1
We define wedge-lifted codes, a variant of lifted codes, and we study their locality properties. We show that (taking the trace of) wedge-lifted codes yields binary codes with the…