5 papers
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 s…
Approximate Butterfly Counting in Sublinear Time
Chi Luo, Jiaxin Song, Yuhao Zhang +3
Bipartite graphs serve as a natural model for representing relationships between two different types of entities. When analyzing bipartite graphs, butterfly counting is a fundament…
Online MMS Allocation for Chores
Jiaxin Song, Biaoshuai Tao, Wenqian Wang +1
We study the problem of fair division of indivisible chores among agents in an online setting, where items arrive sequentially and must be allocated irrevocably upon arrival. T…
Online Makespan Minimization: Beat LPT by Dynamic Locking
Zhaozi Wang, Zhiwei Ying, Yuhao Zhang
Online makespan minimization is a fundamental problem in scheduling. In this paper, we investigate its over-time formulation, where each job has a release time and a processing tim…
Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
Tianle Jiang, Yuhao Zhang
Online matching is a fundamental problem in the study of online algorithms. We study the problem under a very general arrival model: the edge arrival model. Free disposal is an imp…