4 papers
The Online -Taxi Problem Is Competitive on All Metrics
Christian Coester, Yichen Huang, Tze-Yang Poon
The online -taxi problem is a natural generalization of the -server problem: taxis must serve a sequence of requests in a metric space. Each request is a pair of points $…
Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings
Sándor Kisfaludi-Bak, Tze-Yang Poon, Geert van Wordragen
Hyperbolic tilings are natural infinite planar graphs where each vertex has degree and each face has edges for some . We study the structure of sho…
Online 3-Taxi on General Metrics
Christian Coester, Tze-Yang Poon
The online -taxi problem, introduced in 1990 by Fiat, Rabani and Ravid, is a generalization of the -server problem where taxis must serve a sequence of requests in a metr…
Approximate Proportionality in Online Fair Division
Davin Choo, Winston Fu, Derek Khu +3
We study the online fair division problem, where indivisible goods arrive sequentially and must be allocated immediately and irrevocably. Prior work establishes strong impossibilit…