Tianming Zhao
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Tianming Zhao has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Albert Y. Zomaya
The University of Sydney
6 shared publications - Wei Li
The University of Sydney
6 shared publications - Weisheng Si
School of Computer, Data and Mathematical Sciences, Western Sydney University, Parramatta, NSW, Australia
2 shared publications - Boyu Qin
School of Energy and Electrical Engineering, Qinghai University, Xining 810016, China
1 shared publication - Chunqiu Xia
Centre for Distributed and High Performance Computing, School of Information Technologies, The University of Sydney, Camperdown, Australia
1 shared publication - Ling Wang
Tsinghua University
1 shared publication
Latest Publications
- 12 August 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 73 (11) , 2548-2562
Learning-Augmented Scheduling
The recent revival in learning theory has provided us with improved capabilities for accurate predictions. This work contributes to an emerging research agenda of online scheduling with predictions by studying makespan minimization in uniformly related machine non-clairvoyant scheduling with job size predictions. Our task is to design online algorithms that use predictions and have performance guarantees tied to prediction quality. We first propose a simple algorithm-independent prediction error metric to quantify prediction quality. Then we design an offline improved 2-relaxed decision procedure approximating the optimal schedule to effectively use the predictions. With the decision procedure, we propose an online$O(\min\{\log\eta,\log m\})$ -competitive static scheduling algorithm assuming a known prediction error. We use this algorithm to construct a robust$O(\min\{\log\eta,\log m\})$ -competitive static scheduling algorithm that does not assume a known error. Finally, we extend these static scheduling algorithms to address dynamic scheduling where jobs arrive over time. The dynamic scheduling algorithms attain the same competitive ratios as the static ones. The presented algorithms require just moderate predictions to break the$\Omega(\log m)$ competitive ratio lower bound, showing the potential of predictions in managing uncertainty.- 12 August 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 73 (11) , 2548-2562
Learning-Augmented Scheduling
The recent revival in learning theory has provided us with improved capabilities for accurate predictions. This work contributes to an emerging research agenda of online scheduling with predictions by studying makespan minimization in uniformly related machine non-clairvoyant scheduling with job size predictions. Our task is to design online algorithms that use predictions and have performance guarantees tied to prediction quality. We first propose a simple algorithm-independent prediction error metric to quantify prediction quality. Then we design an offline improved 2-relaxed decision procedure approximating the optimal schedule to effectively use the predictions. With the decision procedure, we propose an online$O(\min\{\log\eta,\log m\})$ -competitive static scheduling algorithm assuming a known prediction error. We use this algorithm to construct a robust$O(\min\{\log\eta,\log m\})$ -competitive static scheduling algorithm that does not assume a known error. Finally, we extend these static scheduling algorithms to address dynamic scheduling where jobs arrive over time. The dynamic scheduling algorithms attain the same competitive ratios as the static ones. The presented algorithms require just moderate predictions to break the$\Omega(\log m)$ competitive ratio lower bound, showing the potential of predictions in managing uncertainty.- Open Access
- 27 March 2023
- Published by Association for Computing Machinery (ACM)
- p. 618-625
Automatic Pain Assessment with Ultra-short Electrodermal Activity Signal
- 27 March 2023
- Published by Association for Computing Machinery (ACM)
- p. 618-625
Open AccessAutomatic Pain Assessment with Ultra-short Electrodermal Activity Signal
- Open Access
- 7 March 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Performance Evaluation of Computing Systems
- Vol. 8 (1-2) , 1-27
Pulsed Power Load Coordination in Mission- and Time-critical Cyber-physical Systems
Many mission- and time-critical cyber-physical systems deploy an isolated power system for their power supply. Under extreme conditions, the power system must process critical missions by maximizing the Pulsed Power Load (PPL) utility while maintaining the normal loads in the cyber-physical system. Optimal operation requires careful coordination of PPL deployment and power supply processes. In this work, we formulate the coordination problem for maximizing PPL utility under available resources, capacity, and demand constraints. The coordination problem has two scenarios for different use cases, fixed and general normal loads. We develop an exact pseudo-polynomial time dynamic programming algorithm for each scenario with a proven guarantee to produce an optimal coordination schedule. The performance of the algorithms is also experimentally evaluated, and the results agree with our theoretical analysis, showing the practicality of the solutions.
- 7 March 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Performance Evaluation of Computing Systems
- Vol. 8 (1-2) , 1-27
Open AccessPulsed Power Load Coordination in Mission- and Time-critical Cyber-physical Systems
Many mission- and time-critical cyber-physical systems deploy an isolated power system for their power supply. Under extreme conditions, the power system must process critical missions by maximizing the Pulsed Power Load (PPL) utility while maintaining the normal loads in the cyber-physical system. Optimal operation requires careful coordination of PPL deployment and power supply processes. In this work, we formulate the coordination problem for maximizing PPL utility under available resources, capacity, and demand constraints. The coordination problem has two scenarios for different use cases, fixed and general normal loads. We develop an exact pseudo-polynomial time dynamic programming algorithm for each scenario with a proven guarantee to produce an optimal coordination schedule. The performance of the algorithms is also experimentally evaluated, and the results agree with our theoretical analysis, showing the practicality of the solutions.
- 25 February 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Sustainable Computing
- Vol. 7 (4) , 887-898
Lightweight Online Scheduling for Home Energy Management Systems Under Uncertainty
The increasing use of renewable energy sources and electrical energy storage systems creates a new energy paradigm for residential houses and buildings. Such design reduces carbon footprint, but it also introduces a new challenge for minimizing the electricity bill while still meeting users' needs. This challenge is often accompanied by deep uncertainty in user load demands, electricity tariffs, and renewable energy generations. To address this challenge, we propose an online algorithm, Virtual Algorithm-based Lightweight Online Scheduling (VALOS), to manage electricity purchasing and battery operations. Our solution does not use any prediction components in dealing with uncertainties. Instead, our algorithm employs a lightweight routine, Virtual Algorithm (VA), for making critical decisions to manage uncertainty. We prove that VA achieves an expected probability of 1/e for choosing the optimal purchasing timing online and incurs only a logarithmic computational cost. With VA, VALOS decides how the energy storage reacts to the load demands, which incurs only a linear-logarithmic online computational cost while achieving optimal performance under the specified conditions. Finally, we conduct extensive trace-driven simulations on real-world datasets to confirm the theoretical results and demonstrate the potential of VALOS.
- 25 February 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Sustainable Computing
- Vol. 7 (4) , 887-898
Lightweight Online Scheduling for Home Energy Management Systems Under Uncertainty
The increasing use of renewable energy sources and electrical energy storage systems creates a new energy paradigm for residential houses and buildings. Such design reduces carbon footprint, but it also introduces a new challenge for minimizing the electricity bill while still meeting users' needs. This challenge is often accompanied by deep uncertainty in user load demands, electricity tariffs, and renewable energy generations. To address this challenge, we propose an online algorithm, Virtual Algorithm-based Lightweight Online Scheduling (VALOS), to manage electricity purchasing and battery operations. Our solution does not use any prediction components in dealing with uncertainties. Instead, our algorithm employs a lightweight routine, Virtual Algorithm (VA), for making critical decisions to manage uncertainty. We prove that VA achieves an expected probability of 1/e for choosing the optimal purchasing timing online and incurs only a logarithmic computational cost. With VA, VALOS decides how the energy storage reacts to the load demands, which incurs only a linear-logarithmic online computational cost while achieving optimal performance under the specified conditions. Finally, we conduct extensive trace-driven simulations on real-world datasets to confirm the theoretical results and demonstrate the potential of VALOS.
- 3 September 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 8 (4) , 3290-3302
Towards Minimizing the $R$ Metric for Measuring Network RobustnessWith the prevalence of cyber-attacks on infrastructure networks such as the Internet backbone, measuring the robustness of network topologies has become a critical issue. To this end, a metric called ‘ $R$ ’ has been proposed and widely used. ‘ $R$ ’ assumes that an attack on a network consists of $n$ rounds of node removals with one node removed each round, where $n$ is the number of nodes in the network. Since the value of $R$ depends on the sequence of node removals, finding the sequence minimizing $R$ becomes an interesting problem, denoted as Min-R hereafter. Although many heuristic approaches have been proposed for Min-R, there has been no optimal polynomial-time algorithm given so far, nor is Min-R proved NP-hard. To fill this gap, this paper presents the following fundamental results. First, to minimize $R$ , a node needs to be always removed from the largest connected component of the current network in each round. Second, the Min-R problem has an Optimal Substructure, which allows it to be solved by Dynamic Programming in exponential time instead of the naive factorial time on general graphs. Finally, an efficient and optimal logarithmic-time algorithm is given for Min-R on path graphs, with its complexity and optimality proved.
- 3 September 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 8 (4) , 3290-3302
Towards Minimizing the $R$ Metric for Measuring Network RobustnessWith the prevalence of cyber-attacks on infrastructure networks such as the Internet backbone, measuring the robustness of network topologies has become a critical issue. To this end, a metric called ‘ $R$ ’ has been proposed and widely used. ‘ $R$ ’ assumes that an attack on a network consists of $n$ rounds of node removals with one node removed each round, where $n$ is the number of nodes in the network. Since the value of $R$ depends on the sequence of node removals, finding the sequence minimizing $R$ becomes an interesting problem, denoted as Min-R hereafter. Although many heuristic approaches have been proposed for Min-R, there has been no optimal polynomial-time algorithm given so far, nor is Min-R proved NP-hard. To fill this gap, this paper presents the following fundamental results. First, to minimize $R$ , a node needs to be always removed from the largest connected component of the current network in each round. Second, the Min-R problem has an Optimal Substructure, which allows it to be solved by Dynamic Programming in exponential time instead of the naive factorial time on general graphs. Finally, an efficient and optimal logarithmic-time algorithm is given for Min-R on path graphs, with its complexity and optimality proved.
- 10 February 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 29 (3) , 1088-1104
Optimizing the Maximum Vertex Coverage Attacks Under Knapsack Constraint
Only when we understand how hackers think, can we defend against their attacks. Towards this end, this paper studies the cyber-attacks that aim to remove nodes or links from network topologies. We particularly focus on one type of such attacks called Maximum Vertex Coverage Attacks under Knapsack constraint (MVCAK), in which a hacker has a fixed budget to remove nodes from a network with the nodes involving different costs for removal, and the hacker's goal is to maximize the number of links incident to the nodes removed. Since the MVCAK problem is NP-hard, we firstly propose an optimal solution by Integer Linear Program formulation. Secondly, we give an approximate solution by Linear Programming relaxation that achieves an approximation ratio of 3/4, outperforming the existing 1 - 1/sqrt(e) (about 0.39). Thirdly, since the straightforward implementation of our approximate solution has a high time complexity, we propose two heuristics to significantly reduce its complexity while preserving the approximation ratio. We formally prove the correctness and the effectiveness of these two heuristics. Finally, we conduct extensive experiments on both artificial and real-world networks, showing that our approximate solution produces almost the same results as the optimal solution in practice and has an acceptable running time.
- 10 February 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 29 (3) , 1088-1104
Optimizing the Maximum Vertex Coverage Attacks Under Knapsack Constraint
Only when we understand how hackers think, can we defend against their attacks. Towards this end, this paper studies the cyber-attacks that aim to remove nodes or links from network topologies. We particularly focus on one type of such attacks called Maximum Vertex Coverage Attacks under Knapsack constraint (MVCAK), in which a hacker has a fixed budget to remove nodes from a network with the nodes involving different costs for removal, and the hacker's goal is to maximize the number of links incident to the nodes removed. Since the MVCAK problem is NP-hard, we firstly propose an optimal solution by Integer Linear Program formulation. Secondly, we give an approximate solution by Linear Programming relaxation that achieves an approximation ratio of 3/4, outperforming the existing 1 - 1/sqrt(e) (about 0.39). Thirdly, since the straightforward implementation of our approximate solution has a high time complexity, we propose two heuristics to significantly reduce its complexity while preserving the approximation ratio. We formally prove the correctness and the effectiveness of these two heuristics. Finally, we conduct extensive experiments on both artificial and real-world networks, showing that our approximate solution produces almost the same results as the optimal solution in practice and has an acceptable running time.