13 citations · 26 across the 10 of their papers we have counts for
11 papers
Straightforward Entropy-Sensitive Mergesort
Bill Jin, Alex Zihan Xu
In this paper, we present a stable mergesort variant, "directional mergesort", that to sort an array of elements makes no more than comparisons and moves w…
Sample Complexity Analysis for Adaptive Optimization Algorithms with Stochastic Oracles
Billy Jin, Katya Scheinberg, Miaolan Xie
Several classical adaptive optimization algorithms, such as line search and trust region methods, have been recently extended to stochastic settings where function values, gradient…
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…
Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows
Monika Henzinger, Billy Jin, Richard Peng +1
We study the problem of finding flows in undirected graphs so as to minimize the weighted -norm of the flow for any . When , the problem is that of finding an electr…
High Probability Complexity Bounds for Adaptive Step Search Based on Stochastic Oracles
Billy Jin, Katya Scheinberg, Miaolan Xie
We consider a step search method for continuous optimization under a stochastic setting where the function values and gradients are available only through inexact probabilistic zer…
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
Monika Henzinger, Billy Jin, Richard Peng +1
Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems whose coefficient matrix is the Laplacian matrix of a we…
Online Nash Social Welfare Maximization with Predictions
Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh +1
We consider the problem of allocating a set of divisible goods to agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which provi…
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model
Billy Jin, David P. Williamson
In this paper, we consider the online vertex-weighted bipartite matching problem in the random arrival model. We consider the generalization of the RANKING algorithm for this probl…