4 papers
Additively Competitive Secretaries
Mohammad Mahdian, Jieming Mao, Enze Sun +2
In the secretary problem, a set of secretary candidates arrive in a uniformly random order and reveal their values one by one. A company, who can only hire one candidate and hopes…
Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
Yutong Geng, Enze Sun, Zonghan Yang +1
This paper studies the online scheduling problem of minimizing total flow time for jobs on identical machines. A classical lower bound shows that no deterministic si…
Edge-weighted Matching in the Dark
Zhiyi Huang, Enze Sun, Xiaowei Wu +1
We present a -competitive Quadratic Ranking algorithm for the Oblivious Bipartite Matching problem, a distribution-free version of Query-Commit Matching. This result breaks…
Stochastic Online Correlated Selection
Ziyun Chen, Zhiyi Huang, Enze Sun
We study Stochastic Online Correlated Selection (SOCS), a family of online rounding algorithms for Non-IID Stochastic Online Submodular Welfare Maximization and special cases such…