Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
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…
cs.DS2021
An Lower Bound for Online Matching on the Line
Kangning Wang
For online matching with the line metric, we present a lower bound of on the approximation ratio of any online (possibly randomized) algorithm. This beats the previous…