6 papers
Combinatorial Philosopher Inequalities
Enze Sun, Zhihao Gavin Tang, Yifan Wang
In online combinatorial allocation, agents arrive sequentially and items are allocated in an online manner. The algorithm designer only knows the distribution of each agent's valua…
Online Stochastic Matching with Unknown Arrival Order: Beating against the Online Optimum
Enze Sun, Zhihao Gavin Tang, Yifan Wang
We study the online stochastic matching problem. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal -competitive algorithm. A recent li…
Improved Algorithms for Online Rent Minimization Problem Under Unit-Size Jobs
Enze Sun, Zonghan Yang, Yuhao Zhang
We consider the Online Rent Minimization problem, where online jobs with release times, deadlines, and processing times must be scheduled on machines that can be rented for a fixed…
Better Approximation for Interdependent SOS Valuations
Pinyan Lu, Enze Sun, Chenghan Zhou
Submodular over signal (SOS) defines a family of interesting functions for which there exist truthful mechanisms with constant approximation to the social welfare for agents with i…
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
Nick Gravin, Enze Sun, Zhihao Gavin Tang
We consider ordinal online problems, i.e., tasks that only require pairwise comparisons between elements of the input. A classic example is the secretary problem and the game of go…
Generalized Sorting with Predictions
Pinyan Lu, Xuandi Ren, Enze Sun +1
Generalized sorting problem, also known as sorting with forbidden comparisons, was first introduced by Huang et al. together with a randomized algorithm which requires $\tilde O(n^…