6 papers
Exact MMS Allocations under Personalized Bivalued Valuations: Goods and Chores
Yuhao Zhang
The maximin share (MMS) is a central fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting, where each a…
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 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…
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…
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…
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…