Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
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…
cs.DS2024
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…
cs.DS2023
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…