MLMozhengfu Liu

Mozhengfu Liu

*This is an algorithmically generated author record based on publicly available information.

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


Mozhengfu Liu has a total of 2 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Online Span Minimization for Flexible Uniform Jobs

    by Mozhengfu Liu, Samir Khuller, Xueyan Tang

  • Open Access

    Tight Bounds for Dynamic Bin Packing with Predictions

    by Mozhengfu Liu, Xueyan Tang

    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

    Tight Bounds for Dynamic Bin Packing with Predictions

    by Mozhengfu Liu, Xueyan Tang

    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

    Brief Announcement: Tight bounds for Dynamic Bin Packing with Predictions

    by Mozhengfu Liu, Xueyan Tang

    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

    Brief Announcement: Scheduling Jobs for Minimum Span: Improved Bounds and Learning-Augmented Algorithms

    by Mozhengfu Liu, Xueyan Tang

    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

    Dynamic Bin Packing with Predictions

    by Mozhengfu Liu, Xueyan Tang

    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

    Dynamic Bin Packing with Predictions

    by Mozhengfu Liu, Xueyan Tang

    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

    Dynamic Bin Packing with Predictions

    by Mozhengfu Liu, Xueyan Tang

    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.


  • Busy-Time Scheduling on Heterogeneous Machines: Algorithms and Analysis

    by Mozhengfu Liu, Xueyan Tang

    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.