13 citations · 26 across the 10 of their papers we have counts for
4 papers · 1 filter
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
Billy Jin, Nathan Klein, David P. Williamson
A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP is at most 4/3. Despite…
Proportionally Fair Online Allocation of Public Goods with Predictions
Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain +3
We design online algorithms for the fair allocation of public goods to a set of agents over a sequence of rounds and focus on improving their performance using predictions.…
The Two-Stripe Symmetric Circulant TSP is in P
Samuel C. Gutekunst, Billy Jin, David P. Williamson
The symmetric circulant TSP is a special case of the traveling salesman problem in which edge costs are symmetric and obey circulant symmetry. Despite the substantial symmetry of t…
Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
Billy Jin, Will Ma
Two-stage bipartite matching is a fundamental problem of optimization under uncertainty introduced by Feng, Niazadeh, and Saberi (2021), who study it under the stochastic and adver…