4 papers
MMS Allocation for Chores with Online Agent Arrivals
Haolong Li, Zehan Lin, Huahua Miao +1
We study the fair allocation of indivisible chores to agents with subadditive cost functions arriving online in an arbitrary order. Upon an agent's arrival, we are informed…
Minimization Prophet Inequality with Bounded Costs
Haolong Li, Xiaowei Wu
We study the cost-minimization prophet inequality problem, in which a decision-maker sequentially observes independent and identically distributed (IID) random variables. After…
Online Matching with KIID Edge Arrivals
Yilong Feng, Haolong Li, Xiaowei Wu
In the classic online stochastic matching proposed by Feldman et al. (FOCS 2009), there is a known bipartite type-graph, where one side of the graph is given offline. Upon the arri…
Degree-bounded Online Bipartite Matching: OCS vs. Ranking
Yilong Feng, Haolong Li, Xiaowei Wu +1
We revisit the online bipartite matching problem on -regular graphs, for which Cohen and Wajc (SODA 2018) proposed an algorithm with a competitive ratio of $1-2\sqrt{H_d/d} = 1-…