Mozhengfu Liu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Mozhengfu Liu has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Xueyan Tang
Nanyang technological university, Singapore, Singapore
10 shared publications - Samir Khuller
Department of Computer Science, Northwestern University, Evanston, IL, USA
1 shared publication
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 37-49
Online Span Minimization for Flexible Uniform Jobs
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 37-49
Open AccessOnline Span Minimization for Flexible Uniform Jobs
- Open Access
- 16 June 2025
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 53 (1) , 94-96
Tight Bounds for Dynamic Bin Packing with Predictions
A variant of the Dynamic Bin Packing (DBP) problem known as MinUsageTime DBP seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This paper studies MinUsageTime DBP with predictions about item durations and establishes tight competitiveness bounds over the entire spectrum of prediction errors.
- 16 June 2025
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 53 (1) , 94-96
Open AccessTight Bounds for Dynamic Bin Packing with Predictions
A variant of the Dynamic Bin Packing (DBP) problem known as MinUsageTime DBP seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This paper studies MinUsageTime DBP with predictions about item durations and establishes tight competitiveness bounds over the entire spectrum of prediction errors.
- Open Access
- 9 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 94-96
Tight Bounds for Dynamic Bin Packing with Predictions
- 9 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 94-96
Open AccessTight Bounds for Dynamic Bin Packing with Predictions
- Open Access
- 10 December 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 8 (3) , 1-28
Tight Bounds for Dynamic Bin Packing with Predictions
MinUsageTime DBP is a variant of the Dynamic Bin Packing (DBP) problem that seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This DBP variant models job dispatching for optimizing the busy time of machines, which finds applications in cloud computing and energy-efficient computing. This paper studies the MinUsageTime DBP problem with predictions about item durations (job lengths). We establish tight competitiveness bounds over the entire spectrum of prediction errors. First, we give a lower bound Ω(min {max{ε ⋅ √ log μ, ε 2 }, μ}) on the competitive ratio of any deterministic online algorithm, where μ is the max/min duration ratio of all items and ε is the maximum multiplicative prediction error. Then, we show that the competitive ratio of a recent algorithm has strictly higher asymptotic order than the above lower bound when ε = ω(1) ∧ ε = o(√ μ). Finally, we present an enhanced algorithm and prove that it achieves a competitive ratio matching the above lower bound, closing the gap for this problem.
- 10 December 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 8 (3) , 1-28
Open AccessTight Bounds for Dynamic Bin Packing with Predictions
MinUsageTime DBP is a variant of the Dynamic Bin Packing (DBP) problem that seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This DBP variant models job dispatching for optimizing the busy time of machines, which finds applications in cloud computing and energy-efficient computing. This paper studies the MinUsageTime DBP problem with predictions about item durations (job lengths). We establish tight competitiveness bounds over the entire spectrum of prediction errors. First, we give a lower bound Ω(min {max{ε ⋅ √ log μ, ε 2 }, μ}) on the competitive ratio of any deterministic online algorithm, where μ is the max/min duration ratio of all items and ε is the maximum multiplicative prediction error. Then, we show that the competitive ratio of a recent algorithm has strictly higher asymptotic order than the above lower bound when ε = ω(1) ∧ ε = o(√ μ). Finally, we present an enhanced algorithm and prove that it achieves a competitive ratio matching the above lower bound, closing the gap for this problem.
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 297-299
Brief Announcement: Tight bounds for Dynamic Bin Packing with Predictions
MinUsageTime DBP is a variant of the Dynamic Bin Packing (DBP) problem that seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This paper studies the MinUsageTime DBP problem with predictions about item durations. We establish tight competitiveness bounds over the entire spectrum of prediction errors.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 297-299
Open AccessBrief Announcement: Tight bounds for Dynamic Bin Packing with Predictions
MinUsageTime DBP is a variant of the Dynamic Bin Packing (DBP) problem that seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This paper studies the MinUsageTime DBP problem with predictions about item durations. We establish tight competitiveness bounds over the entire spectrum of prediction errors.
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 141-143
Brief Announcement: Scheduling Jobs for Minimum Span: Improved Bounds and Learning-Augmented Algorithms
We study a flexible job scheduling problem. A set of jobs is released over time, each with a starting deadline and a processing length. The jobs are to be started by an online scheduler no later than their starting deadlines and will run nonpreemptively. The objective is to minimize the span -- the time duration for which at least one job is running. We present a new lower bound of 4 on the competitiveness of any online algorithm. We also establish tight competitiveness bounds in the learning-augmented setting of the problem.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 141-143
Open AccessBrief Announcement: Scheduling Jobs for Minimum Span: Improved Bounds and Learning-Augmented Algorithms
We study a flexible job scheduling problem. A set of jobs is released over time, each with a starting deadline and a processing length. The jobs are to be started by an online scheduler no later than their starting deadlines and will run nonpreemptively. The objective is to minimize the span -- the time duration for which at least one job is running. We present a new lower bound of 4 on the competitiveness of any online algorithm. We also establish tight competitiveness bounds in the learning-augmented setting of the problem.
- Open Access
- 26 June 2023
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 51 (1) , 57-58
Dynamic Bin Packing with Predictions
The MinUsageTime Dynamic Bin Packing (DBP) problem aims to minimize the accumulated bin usage time for packing a sequence of items into bins. It is often used to model job dispatching for optimizing the busy time of servers, where the items and bins match the jobs and servers respectively. It is known that the competitiveness of MinUsageTime DBP has tight bounds of Θ(√, log μ) and Θ(μ) in the clairvoyant and non-clairvoyant settings respectively, where μ is the max/min duration ratio of all items. In practice, the information about items' durations (i.e., job lengths) obtained via predictions is usually prone to errors. In this paper, we study the MinUsageTime DBP problem with predictions of items' durations. We find that an existing O(√ log μ)-competitive clairvoyant algorithm, if using predicted durations rather than real durations for packing, does not provide any bounded performance guarantee when the predictions are adversarially bad. We develop a new online algorithm with a competitive ratio of {O(∈2 √ log(∈2 μ)}, O(μ) (where ε is the maximum multiplicative error of prediction among all items), achieving O(√ log μ) consistency (competitiveness under perfect predictions where ∈ = 1) and O(μ) robustness (competitiveness under terrible predictions), both of which are asymptotically optimal.
- 26 June 2023
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 51 (1) , 57-58
Open AccessDynamic Bin Packing with Predictions
The MinUsageTime Dynamic Bin Packing (DBP) problem aims to minimize the accumulated bin usage time for packing a sequence of items into bins. It is often used to model job dispatching for optimizing the busy time of servers, where the items and bins match the jobs and servers respectively. It is known that the competitiveness of MinUsageTime DBP has tight bounds of Θ(√, log μ) and Θ(μ) in the clairvoyant and non-clairvoyant settings respectively, where μ is the max/min duration ratio of all items. In practice, the information about items' durations (i.e., job lengths) obtained via predictions is usually prone to errors. In this paper, we study the MinUsageTime DBP problem with predictions of items' durations. We find that an existing O(√ log μ)-competitive clairvoyant algorithm, if using predicted durations rather than real durations for packing, does not provide any bounded performance guarantee when the predictions are adversarially bad. We develop a new online algorithm with a competitive ratio of {O(∈2 √ log(∈2 μ)}, O(μ) (where ε is the maximum multiplicative error of prediction among all items), achieving O(√ log μ) consistency (competitiveness under perfect predictions where ∈ = 1) and O(μ) robustness (competitiveness under terrible predictions), both of which are asymptotically optimal.
- Open Access
- 19 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 57-58
Dynamic Bin Packing with Predictions
The MinUsageTime Dynamic Bin Packing (DBP) problem aims to minimize the accumulated bin usage time for packing a sequence of items into bins. It is often used to model job dispatching for optimizing the busy time of servers, where the items and bins match the jobs and servers respectively. It is known that the competitiveness of MinUsageTime DBP has tight bounds of Θ(√, log μ) and Θ(μ) in the clairvoyant and non-clairvoyant settings respectively, where μ is the max/min duration ratio of all items. In practice, the information about items' durations (i.e., job lengths) obtained via predictions is usually prone to errors. In this paper, we study the MinUsageTime DBP problem with predictions of items' durations. We find that an existing O(√ log μ)-competitive clairvoyant algorithm, if using predicted durations rather than real durations for packing, does not provide any bounded performance guarantee when the predictions are adversarially bad. We develop a new online algorithm with a competitive ratio of {O(∈2 √ log(∈2 μ)}, O(μ) (where ε is the maximum multiplicative error of prediction among all items), achieving O(√ log μ) consistency (competitiveness under perfect predictions where ∈ = 1) and O(μ) robustness (competitiveness under terrible predictions), both of which are asymptotically optimal.
- 19 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 57-58
Open AccessDynamic Bin Packing with Predictions
The MinUsageTime Dynamic Bin Packing (DBP) problem aims to minimize the accumulated bin usage time for packing a sequence of items into bins. It is often used to model job dispatching for optimizing the busy time of servers, where the items and bins match the jobs and servers respectively. It is known that the competitiveness of MinUsageTime DBP has tight bounds of Θ(√, log μ) and Θ(μ) in the clairvoyant and non-clairvoyant settings respectively, where μ is the max/min duration ratio of all items. In practice, the information about items' durations (i.e., job lengths) obtained via predictions is usually prone to errors. In this paper, we study the MinUsageTime DBP problem with predictions of items' durations. We find that an existing O(√ log μ)-competitive clairvoyant algorithm, if using predicted durations rather than real durations for packing, does not provide any bounded performance guarantee when the predictions are adversarially bad. We develop a new online algorithm with a competitive ratio of {O(∈2 √ log(∈2 μ)}, O(μ) (where ε is the maximum multiplicative error of prediction among all items), achieving O(√ log μ) consistency (competitiveness under perfect predictions where ∈ = 1) and O(μ) robustness (competitiveness under terrible predictions), both of which are asymptotically optimal.
- Open Access
- 8 December 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 6 (3) , 1-24
Dynamic Bin Packing with Predictions
The MinUsageTime Dynamic Bin Packing (DBP) problem aims to minimize the accumulated bin usage time for packing a sequence of items into bins. It is often used to model job dispatching for optimizing the busy time of servers, where the items and bins match the jobs and servers respectively. It is known that the competitiveness of MinUsageTime DBP has tight bounds of Θ(√łog μ ) and Θ(μ) in the clairvoyant and non-clairvoyant settings respectively, where μ is the max/min duration ratio of all items. In practice, the information about the items' durations (i.e., job lengths) obtained via predictions is usually prone to errors. In this paper, we study the MinUsageTime DBP problem with predictions of the items' durations. We find that an existing O(√łog μ )-competitive clairvoyant algorithm, if using predicted durations rather than real durations for packing, does not provide any bounded performance guarantee when the predictions are adversarially bad. We develop a new online algorithm with a competitive ratio of minØ(ε^2 √łog(ε^2 μ) ), O(μ) (where ε is the maximum multiplicative error of prediction among all items), achieving O(√łog μ) consistency (competitiveness under perfect predictions where ε = 1) and O(μ) robustness (competitiveness under terrible predictions), both of which are asymptotically optimal.
- 8 December 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 6 (3) , 1-24
Open AccessDynamic Bin Packing with Predictions
The MinUsageTime Dynamic Bin Packing (DBP) problem aims to minimize the accumulated bin usage time for packing a sequence of items into bins. It is often used to model job dispatching for optimizing the busy time of servers, where the items and bins match the jobs and servers respectively. It is known that the competitiveness of MinUsageTime DBP has tight bounds of Θ(√łog μ ) and Θ(μ) in the clairvoyant and non-clairvoyant settings respectively, where μ is the max/min duration ratio of all items. In practice, the information about the items' durations (i.e., job lengths) obtained via predictions is usually prone to errors. In this paper, we study the MinUsageTime DBP problem with predictions of the items' durations. We find that an existing O(√łog μ )-competitive clairvoyant algorithm, if using predicted durations rather than real durations for packing, does not provide any bounded performance guarantee when the predictions are adversarially bad. We develop a new online algorithm with a competitive ratio of minØ(ε^2 √łog(ε^2 μ) ), O(μ) (where ε is the maximum multiplicative error of prediction among all items), achieving O(√łog μ) consistency (competitiveness under perfect predictions where ε = 1) and O(μ) robustness (competitiveness under terrible predictions), both of which are asymptotically optimal.
- 23 May 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 33 (12) , 3942-3958
Busy-Time Scheduling on Heterogeneous Machines: Algorithms and Analysis
We study a generalized busy-time scheduling model on heterogeneous machines. The input to the model includes a set of jobs and a set of machine types. Each job has a size and a time interval during which it should be processed. Each job is to be placed on a machine for execution. Different types of machines have distinct capacities and cost rates. The total size of the jobs running on a machine must always be kept within the machine's capacity, giving rise to placement restrictions for jobs of various sizes among the machine types. Each machine used is charged according to the time duration in which it is busy, i.e., it is processing jobs. The objective is to schedule the jobs into machines to minimize the total cost of all the machines used. We develop an$O(1)$ -approximation algorithm in the offline setting and an$O(\mu)$ -competitive algorithm in the online setting (where$\mu$ is the max/min job length ratio), both of which are asymptotically optimal. This article significantly improves the analysis of the algorithms over our preliminary work.- 23 May 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 33 (12) , 3942-3958
Busy-Time Scheduling on Heterogeneous Machines: Algorithms and Analysis
We study a generalized busy-time scheduling model on heterogeneous machines. The input to the model includes a set of jobs and a set of machine types. Each job has a size and a time interval during which it should be processed. Each job is to be placed on a machine for execution. Different types of machines have distinct capacities and cost rates. The total size of the jobs running on a machine must always be kept within the machine's capacity, giving rise to placement restrictions for jobs of various sizes among the machine types. Each machine used is charged according to the time duration in which it is busy, i.e., it is processing jobs. The objective is to schedule the jobs into machines to minimize the total cost of all the machines used. We develop an$O(1)$ -approximation algorithm in the offline setting and an$O(\mu)$ -competitive algorithm in the online setting (where$\mu$ is the max/min job length ratio), both of which are asymptotically optimal. This article significantly improves the analysis of the algorithms over our preliminary work.