Prudence's Publications

Journals and Conferences

2023

• The Power of Amortization on Scheduling with Explorable Uncertainty. (with F.H. Liu and H.H. Liu)
  Accepted to Proceedings of the 21st Workshop on Approximation and Online Algorithms (WAOA), 2023, to appear. [Download paper (pdf)]
• RNA Secondary Structures: From ab initio Prediction to Better Compression, and Back. (with E. Onokpasa and S. Wild)
  Proceedings of the 2023 Data Compression Conference (DCC), 2023, pp278--287. [Download paper (pdf)] [From IEEE]

2021

• Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs. (with F.H. Liu and H.H. Liu)
  Theory of Computing Systems, 2021. [Download paper (pdf)] [From Springer]

2020

• Non-preemptive Scheduling in a Smart Grid Model and its Implications on Machine Minimization. (with F.H. Liu and H.H. Liu)
  Algorithmica, 82:3415-3457, 2020. [Download paper (pdf)] [From Springer]
• Predicting the Availability of Hematopoietic Stem Cell Donors Using Machine Learning. (with Y. Li, A. Masiliune, D. Winstone, L. Gasieniec, H. Lin, R. Pawson, G. Parkes and Andrew Hadley)
  Biology of Blood and Marrow Transplantation,, 26(8):1406-1413, 2020. [Download paper (pdf)] [From ASTCT, Elsevier]
• Dynamic Programming Optimization in Line of Sight Network. (with P. Sangha and M. Zito)
  Information and Computation (IC), 270:article104460, 2020. [Download paper (pdf)] [From ScienceDirect]
• Optimizing mmWave Wireless Backhaul Scheduling. (with E. Arribas, A. Fernandez Anta, D.R. Kowalski, V. Mancuso, M.A. Mosteiro and J. Widmer)
  IEEE Transactions on Mobile Computing, 19(10):2409-2428, 2020. [Download paper (pdf)] [From IEEE]
• Semiglobal Sequence Alignment with Gaps using GPU. (with T.C. Carroll and J.-T. Ojiaku)
  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 17(6): 2086-2097, 2020. [Download paper (pdf)] [From IEEE]
• Profit Maximization in Flex-Grid All-Optical Networks. (with M. Shalom and S. Zaks)
  Theory of Computing Systems (TOCS), 64(2):311-326, 2020. [Download paper (pdf)] [From Springer]

2019

• Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs. (with F.-H. Liu and H.-H. Liu)
  Proceedings of the 17th Workshop on Approximation and Online Algorithms (WAOA), 2019, pp217--231. [Download paper (pdf)] [From Springer]
• Fault-Tolerant Parallel Scheduling of Arbitrary Length Jobs on a Shared Channel. (with M. Klonowski, D. Kowalski and J. Mirek)
  Proceedings of the 22nd International Symposium on Fundamentals of Computation Theory (FCT), 2019, pp306--321. [Download paper (pdf)] [From Springer]
• Performing Partially Ordered Sets of Jobs on a MAC in Presence of Adversarial Crashes. (with M. Klonowski, D. Kowalski and J. Mirek)
  Proceedings of the 18th IEEE International Symposium on Network Computing and Applications (NCA), 2019, pp1--4. [Download paper (pdf)] [From IEEE]
• Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals. (with T. Erlebach, H.H Liu, F.H. Liu, M. Shalom and S. Zaks)
  Invited to Theoretical Computer Science (TCS), 788:66--78, 2019. [Download paper (pdf)] [From Springer]
• Station Assignment with Reallocation. (with A. Halper, M.A. Mosteiro and Y. Rossikova)
  Algorithmica, 81(3):1096-1125, 2019. [Download paper (pdf)] [From Springer]
• Testing Methods to Minimise Range-shifting Time with Conservation Actions. (with D. Aloqalaa, J. Hodgson and D. Kowalski)
  Proceedings of the 11th International Conference on Bioinformatics and Biomedical Technology (ICBBT), pp32--39, 2019. [Download paper (pdf)] [From ACM]

2018

• Scheduling Dynamic Parallel Workload of Mobile Devices with Access Guarantees. (with A. Fernandez Anta, D.R. Kowalski and M.A. Mosteiro )
  ACM Transactions on Parallel Computing (TOPC), 5(2):artcle 10. [Download paper (pdf)] [From Springer]
• Hardness and Approximation of The Asynchronous Border Minimization Problem (with A. Popa, C. Li and F.C.C. Yung)
  Discrete Applied Mathematics (DAM), 235(30):101-117, 2018. [Download paper (pdf)] [From ScienceDirect]

2017

• Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals. (with T. Erlebach, H.H Liu, F.H. Liu, M. Shalom and S. Zaks)
  Proceedings of the 11th International Conference of Combinatorial Optimization and Applications (COCOA), pp. 317-332, 2017. [Download paper (pdf)] [From Springer]
• Fault Tolerant Scheduling of Tasks of Two Sizes under Resource Augmentation. (with D.R. Kowalski and E. Zavou)
  Journal of Scheduling (JoS), 20(6):695-711, 2017. [Download paper (pdf)] [From Springer]
• Online Regenerator Placement. (with G. Mertzios, M. Shalom and S. Zaks)
  Theory of Computing Systems (TOCS), 61(3):739–754, 2017. [Download paper (pdf)] [From Springer]
• Independent Sets in Restricted Line of Sight Networks. (with P. Sangha and M. Zito)
  Proceedings of the 13th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), pp. 211-222, 2017. [Download paper (pdf)] [From Springer]
• Complexity and Online Algorithms for a Coloring Problem on a Line. (with T. Erlebach, H.H Liu, F.H. Liu, M. Shalom and S. Zaks)
  Proceedings of the 13th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2017. [Download paper (pdf)]
• The Impact of Landscape Sparsification on Modelling and Analysis of the Invasion Process. (with D. Aloqalaa and J. Hodgson)
  Proceedings of the 16th International Symposium on Experimental Algorithms (SEA), 2017, 32:1-16. [Download paper (pdf)] [From DROPS]
• An Improved Abstract GPU Model with Data Transfer. (with T.C. Carroll)
  Proceedings of 46th International Conference on Parallel Processing Workshops - Workshop on Heterogeneous and Unconventional Cluster Architectures and Applications (HUCAA), pp. 113-120, 2017. [Download paper (pdf)] [From IEEE]
• Lightweight Framework for Reliable Job Scheduling in Heterogeneous Clouds. (with M.B. Abdulazeez and P. Garncarek)
  7th Workshop on Industrial Internet of Things Communication Networks – (IioTCom), 2017. [Download paper (pdf)] [From IEEE]
• Lightweight Robust Framework for Workload Scheduling in Clouds. (with M.B. Abdulazeez, P. Garncarek and D. Kowalski)
  The 1st IEEE International Conference on Edge Computing (EDGE), pp. 206-209, 2017. [Download paper (pdf)] [From IEEE]

2016

• Optimal Nonpreemptive Scheduling in a Smart Grid Model. (with F.H. Liu and H.H. Liu)
  Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC), 2016, 53:1-53:13, 2016. [Download paper (pdf)] [From DROPS]
• Scheduling for Electricity Cost in Smart Grid. (with M. Burcea, W.K. Hon, H.H. Liu and D.K.Y. Yau)
  Journal of Scheduling (JoS), 19(6), 687--699, 2016. [Download paper (pdf)] [From Springer]
• Routing in Geometric Networks. (with S. Durocher and L. Gasieniec)
  Encyclopedia of Algorithms, 1871--1875, 2016. [From Springer]
• On-line Maximum Matching in Complete Multi-partite Graphs with an Application to Optical Networks. (with M. Shalom and S. Zaks)
  Discrete Applied Mathematics (DAM), 199, 123--136, 2016. [From ScienceDirect]

2015

• Pairwise Sequence Alignment with Gaps with GPU. (with T.C. Carroll and J.-T. Ojiaku)
  Proceedings of IEEE Cluster 2015 - 4th International Workshop on Heterogenous and Unconventional Cluster Architectures and Applications (HUCAA), pp. 603--610, 2015. [Download paper (pdf)] [From IEEE]
• Station Assignment with Reallocation. (with M.A. Mosteiro and Y. Rossikova)
  The 14th International Symposium on Experimental Algorithms (SEA), pp. 151--164, 2015. [Download paper (pdf)] [From Springer]
• Fault Tolerant Scheduling of Non-uniform Tasks Under Resource Augmentation. (with D.R. Kowalski and E. Zavou)
  The 12th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2015.
• Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines. (with P. Bell)
  Journal of Combinatorial Optimization (JoCO), 29(4) 739--749, 2015. [Download paper (pdf)] [From Springer]
• Optimizing Busy Time on Parallel Machines (with G. Mertzios, M. Shalom, A. Voloshin and S. Zaks)
  Theoretical Computer Science (TCS), 562, 524--541, 2015. [From ScienceDirect]

2014

• A Framework for Brand Reputation Mining and Visualisation. (with A. Alshukri, F. Coenen, Y. Li and A. Redfern)
  Proceedings of the Thirty-fourth SGAI International Conference on Artificial Intelligence (SGAI), Research and Development in Intelligent Systems XXXI, pp. 301--315, 2014. [Download paper (pdf)] [From Springer]
• Online Optimization of Busy Time on Parallel Machines (with M. Shalom, A. Voloshin, F.C.C. Yung and S. Zaks)
  Invited to Theoretical Computer Science (TCS), 560, 190--206, 2014. [Download paper (pdf)] [From ScienceDirect]

2013

• Transcriptome Analysis of the Filamentous Fungus Aspergillus nidulans Directed to the Global Identification of Promoters. (with C. Sibthorp, H. Wu, G. Cowley, P. Palaima, I.Y. Morozov, G.D. Weedall and M.X. Caddick)
  BMC Genomics, 14:847, 2013. [From BioMed Central]
• Scheduling for Electricity Cost in Smart Grid. (with M. Burcea, W.K. Hon, H.H Liu and D.K.Y. Yau)
  Proceedings of the 7th International Conference of Combinatorial Optimization and Applications (COCOA), 2013, pp. 306--317. [Download paper (pdf)] [From Springer]
• Station Assignment with Applications to Sensing. (with A. Fernandez Anta, D.R. Kowalski and M.A. Mosteiro)
  Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), 2013, pp. 155--169. [Download paper (pdf)] [From Springer]
• Profit Maximization in Flex-Grid All-Optical Networks. (with M. Shalom and S. Zaks)
  Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2013, pp. 249--260. [Download paper (pdf)] [From Springer]
• Online Scheduling of Simple Linear Deteriorating Jobs to Minimize Total General Completion Time. (with S. Yu)
  Theoretical Computer Science (TCS), 487, 95--102, 2013. [Download paper (pdf)] [From ScienceDirect]
• Online Multi-dimensional Dynamic Bin Packing of Unit-Fraction Items (with M. Burcea and F.C.C. Yung)
  Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC), 2013, pp. 85--96. [Download paper (pdf)] [From Springer]
• Online Speed Scaling Based on Active Job Count to Minimize Flow plus Energy. (with T.W. Lam, L.K. Lee and I.K.K. To)
  Algorithmica, 65:3, 605--633, 2013. [Download paper (pdf)] [From Springer]
• Finding DNA Regulatory Motifs with Position-dependent Models. (with H. Wu, M.X. Caddick and C. Sibthorp)
  Journal of Medical and Bioengineering (JoMB), 2:2, 103--109, 2013. [Download paper (pdf)] [From ETPub]
• Improved Results on Online Dynamic Bin Packing. (with M. Burcea and F.C.C. Yung)
  The 11th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2013. [Download paper (pdf)]
• Interval Scheduling to Maximize Bandwidth Provision. (with M. Shalom and S. Zaks)
  The 11th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2013. [Download paper (pdf)]
• Energy-efficient Flow Time Scheduling: An Experimental Study. (with J.-T. Ojiaku and D. Thomas)
  The 11th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2013. [Download paper (pdf)]

2012

• An 8/3 Lower Bound for Online Dynamic Bin Packing (with F.C.C. Yung and M. Burcea)
  Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC), 2012, pp. 44--53. [Download paper (pdf)] [From Springer]
• Hardness and Approximation of The Asynchronous Border Minimization Problem (with A. Popa and F.C.C. Yung)
  Proceedings of the 9th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2012, pp. 164--176. [Download paper (pdf)] [From Springer]
• Online Makespan Scheduling of Linear Deteriorating Jobs on Parallel Machines (with S. Yu, J. Ojiaku and Y. Xu)
  Proceedings of the 9th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2012, pp. 260--272. [Download paper (pdf)] [From Springer]
• Online Optimization of Busy Time on Parallel Machines (with M. Shalom, A. Voloshin, F.C.C. Yung and S. Zaks)
  Proceedings of the 9th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2012, pp. 448--460. [Download paper (pdf)] [From Springer]
• Optimizing Busy Time on Parallel Machines (with G. Mertzios, M. Shalom, A. Voloshin and S. Zaks)
  Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2012, pp. 238--248. [Download paper (pdf)] [From IEEE]
• A Note on "An Optimal Online Algorithm for Single Machine Scheduling to Minimize Total General Completion Time". (with S. Yu)
  Information Processing Letters (IPL), 112:(1-2), 55--58, 2012. [Download paper (pdf)] [From ScienceDirect]
• Improved Multi-processor Scheduling for Flow Time and Energy. (with T.W. Lam, L.K. Lee and I.K.K. To)
  Journal of Scheduling (JoS), 15(1):105--116, 2012. [Download paper (pdf)] [From Springer]

2011

• Online Regenerator Placement (with G. Mertzios, M. Shalom and S. Zaks)
  Proceedings of the 15th International Conference On Principles Of Distributed Systems (OPODIS), 2011, pp. 4--17. [Download paper (pdf)] [From Springer]
• New Structural and Functional Contexts of the Dx[DN]xDG Linear Motif: Insights into Evolution of Calcium-binding Proteins. (with D.J. Rigden, D.D. Woodhead and M.Y. Galperinc)
  PLoS ONE, 6(6): e21507, 2011. [From PLoS]
• Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines. (with P. Bell)
  Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2011, pp. 27--36. [Download paper (pdf)] [From Springer]
• Online Scheduling of Linear Deteriorating Jobs on Parallel Machines. (with S Yu and Y Xu)
  The 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2011. [Download paper (pdf)]

2010

• Deadline Scheduling and Power Management for Speed Bounded Processors. (with X. Han, T.W. Lam, L.K. Lee and I.K.K. To)
  Theoretical Computer Science (TCS), 411:40-42, pp. 3587--3600, 2010. [Download paper (pdf)] [From ScienceDirect]
• Optimal On-line Colorings for Minimizing the Number of ADMs in Optical Networks. (with M. Shalom and S. Zaks)
  Journal of Discrete Algorithms, 8(2):174--188, 2010. [Download paper (pdf)] [From ScienceDirect]
• High throughput sequencing and Motif Analysis of the A. nidulans transcriptome. (with M. Caddick, C. Sibthorp, H. Wu and N. Hall)
  Poster at the 10th Workshop on Algorithms in Bioinformatics (WABI), 2010.
• High throughput sequencing of the A. nidulans transcriptome. (with M. Caddick, C. Sibthorp, H. Wu and N. Hall)
  Poster at the 10th European Conference on Fungal Genetics (EFG), 2010.

2009

• Optimizing Throughput and Energy in Online Deadline Scheduling. (with H.L. Chan, W.T. Chan, T.W. Lam, L.K. Lee and K.S. Mak)
  Transactions on Algorithms (TALG), 6(1):10, 2009. [Download paper (pdf)] [From ACM]
• Competitive Multi-Dimensional Dynamic Bin Packing via L-Shape Bin Packing. (with F.C.C. Yung)
  Proceedings of the 7th Workshop on Approximation and Online Algorithms (WAOA), 2009, pp. 242--254. [Download paper (pdf)] [From Springer]
• Sleep with Guilt and Work Faster to Minimize Flow plus Energy. (with T.W. Lam, L.K. Lee, H.F. Ting and I.K.K. To)
  Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), 2009, 665--676. [Download paper (pdf)] [From Springer]
• On-line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology. (with M. Shalom and S. Zaks)
  Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2009, pp. 281--294. [Download paper (pdf)] [From Springer]
• Deadline Scheduling and Power Management for Speed Bounded Processors. (with X. Han, T.W. Lam, L.K. Lee and I.K.K. To)
  The 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2009, pp. 82--84. [Download paper (pdf)]
• Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines. (with P. Bell)
  The 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2009, pp. 44--46. [Download paper (pdf)]
• On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis. (with W.T. Chan and F.C.C. Yung)
  Invited to Algorithmica, 53(2):172-206, 2009. [Download paper (pdf)] [From Springer]

2008

• Dynamic Bin Packing of Unit Fractions Items. (with W.T. Chan and T.W. Lam)
  Theoretical Computer Science (TCS), 409(3):521-529, 2008. [Download paper (pdf)] [From Springer]
• Non-migratory Multi-processor Scheduling for Response Time and Energy. (with T.W. Lam, L.K. Lee and I.K.K. To)
  IEEE Transactions on Parallel and Distributed Systems (TPDS) Special Issue on Power-Aware Parallel and Distributed Systems, 19(11):1527-1539, 2008. [Download paper (ps)] [From IEEE]
• Improved On-line Broadcast Scheduling with Deadlines. (with S.P.Y. Fung, F. Zheng, W.T. Chan, F.Y.L. Chin and C.K. Poon)
  Journal of Scheduling (JoS), 11(4):299-308, 2008. [From Springer]
• Routing in Geometric Networks. (with L. Gasieniec and C. Su)
  Encyclopedia of Algorithms, 2008, Part 17. [From Springer]
• Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count. (with T.W. Lam, L.K. Lee and I.K.K. To)
  Proceedings of the 16th Annual European Symposium on Algorithms (ESA), 2008, pp. 647--659. [Download paper (pdf)] [From Springer]
• Competitive Non-migratory Scheduling for Flow Time and Energy. (with T.W. Lam, L.K. Lee and I.K.K. To)
  Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2008, pp. 256--264. [Download paper (pdf)] [From ACM]
• Approximating Border Length for DNA Microarray Synthesis. (with C.Y. Li, Q. Xin and F.C.C. Yung)
  Proceedings of the 5th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2008, pp. 410--422. [Download paper (pdf)] [From Springer]
• Non-overlapping Common Substrings Allowing Mutations. (with H.L. Chan, T.W. Lam, W.K. Sung and S.M. Yiu)
  Mathematics in Computer Science (MCS) Special Issue on Combinatorial Algorithms, 1(4):543--555, 2008. [Download paper (ps)] [From Springer]

2007

• Allowing Mismatches in Anchors for Whole Genome Alignment. (with S.M. Yiu, P.Y. Chan, T.W. Lam and and H.F. Ting)
  WSEAS Transactions on Biology and Biomedicine, 1(4), 2007. [From WSEAS]
• Energy Efficient Deadline Scheduling in Two Processor Systems. (with T.W. Lam, L.K. Lee and K.K. To)
  Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC), 2007, pp. 476--487. [Download paper (pdf)] [From Springer]
• Optimal On-line Colorings for Minimizing the Number of ADMs in Optical Networks. (with M. Shalom and S. Zaks)
  Proceedings of the 21st International Symposium on Distributed Computing (DISC), 2007, pp. 435--449. [Download paper (pdf)] [From Springer]
• Randomized Probe Selection Algorithm for Microarray Design. (with L. Gasieniec and C.Y. Li)
  Journal of Theoretical Biology (JTB), 248(3):512--521, 2007. [Download paper (pdf)] [From Science Direct]
• Bandwidth Minimization Algorithms. (with A.V. Fishkin and R. Sitters)
  The 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), 2007. [Download paper (pdf)]
• Efficiency of Data Distribution in BitTorrent-like Systems. (with H.L. Chan and T.W. Lam)
  Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM), 2007, pp. 378--388. [Download paper (pdf)] [From Springer]
• Online Deadline Scheduling with Bounded Energy Efficiency. (with W.T. Chan, T.W. Lam and K.S. Mak)
  Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2007, 416--427. [Download paper (pdf)] [From Springer]
• Energy Efficient Online Deadline Scheduling. (with H.L. Chan, W.T. Chan, T.W. Lam, L.K. Lee and K.S. Mak)
  Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007, pp. 795--804. [Download paper (ps)] [From ACM]
• Routing of Single-source and Multiple-source Queries in Static Sensor Networks. (with L. Gasieniec, C. Su and Q. Xin)
  Journal of Discrete Algorithms (JDA), 5(1):1-11, 2007. [Download paper (pdf)] [From ScienceDirect]

2006

• Efficient Probe Selection in Microarray Design. (with L. Gasieniec, C.Y. Li and P. Sant)
  Proceedings of the IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB), 2006, pp. 247--254. [Download paper (pdf)] [From IEEE]
• New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling. (with W.T. Chan, T.W. Lam and K.S. Liu)
  Theoretical Computer Science (TCS), 359(1-3): 430--439, 2006. [Download paper (pdf)] [From ScienceDirect]
• A Dynamic Programming Approach of Finding an Optimal Broadcast Schedule in Minimizing Total Flow Time. (with W.T. Chan, F.Y.L. Chin, Y. Zhang, H. Zhu and H. Shen)
  Invited to Journal of Combinatorial Optimization (JCO), 11(2):177--187, 2006. [Download paper (pdf)] [From Springer]
• On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis. (with W.T. Chan and F.C.C. Yung)
  Proceedings of the 11th Annual International Computing and Combinatorics Conference (COCOON), 2006, pp. 309--319. [Download paper (postscript)] [From Springer]
• Improved On-line Broadcast Scheduling with Deadlines. (with F. Zheng, S.P.Y. Fung, W.T. Chan, F.Y.L. Chin and C.K. Poon)
  Proceedings of the 11th Annual International Computing and Combinatorics Conference (COCOON), 2006, pp. 320--329. [Download paper (postscript)] [From Springer]

2005

• New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling. (with W.T. Chan, T.W. Lam and K.S. Liu)
  Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2005, pp.236--247. [Download paper (pdf)] [From Springer]
• Off-line Algorithms for Minimizing the Total Flow Time in Broadcast Scheduling. (with W.T. Chan, F.Y.L. Chin, Y. Zhang, H. Zhu and H. Shen)
  Proceedings of the 10th Annual International Computing and Combinatorics Conference (COCOON), 2005, pp.318--328. [Download paper (postscript)] [From Springer]
• On-line Stream Merging with Max Span and Min Coverage. (with W.T. Chan, T.W. Lam and H.F. Ting)
  Theory of Computing Systems (TOCS), 38(4):461--479, 2005. [Download paper (postscript)] [From Springer]
• Dynamic Bin Packing of Unit Fractions Items. (with W.T. Chan and T.W. Lam)
  Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), 2005, pp. 614--626. [Download paper (pdf)] [From Springer]
• The Mutated Subsequence Problem and Locating Conserved Genes. (with H.L. Chan, T.W. Lam, W.K. Sung, S.M. Yiu and X. Fan)
  Bioinformatics, 21(10):2271--2278, 2005. [From Oxford Journals Online]
• Routing via Single-source and Multiple-source Queries in Static Sensor Networks (with L. Gasieniec, C. Su and Q. Xin)
  Proceedings of the 19th International Parallel and Distributed Processing Symposium (IPDPS) - 5th IEEE International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks, (WMAN), 2005. [Download paper (postscript)] [From IEEE]
• Allowing Mismatches in Anchors for Whole Genome Alignment: Generation and Effectiveness. (with S.M. Yiu, P.Y. Chan, T.W. Lam, W.K. Sung and H.F. Ting)
  Proceedings of the 3rd Asia Pacific Bioinformatics Conference (APBC), 2005, pp. 1--10. [Download paper (postscript)] [From NUS]
• Efficient Constrained Multiple Sequence Alignment with Performance Guarantee. (with Francis Y.L. Chin, N.L. Ho and T.W. Lam)
  Journal of Bioinformatics and Computational Biology (JBCB), 3(1):1--18, 2005. [Download paper (pdf)] [From World Scientific]
• Filtering of Ineffective siRNAs and Improved siRNA Design Tool. (with S.M. Yiu, Y.C. Mui, T.W. Lam, H.F. Kung, M. Lin and Y.T. Cheung)
  Bioinformatics, 21(2):144--151, 2005. [From Oxford Journals Online] (receive The University of Hong Kong Research Output Prize 2006)

2004

• An Efficient Algorithm for Optimizing Whole Genome Alignment with Noise. (with T.W. Lam, N. Lu, H.F. Ting and S.M. Yiu)
  Bioinformatics, 20(16):2676--2684, 2004. [From Oxford Journals Online]
• On-line Windows Scheduling of Temporary Items. (with W.T. Chan)
  Proceedings of the 15th International Symposium of Algorithms and Computation (ISAAC), 2004, pp. 259--270. [Download paper (pdf)] [From Springer]
• New Results on On-demand Broadcasting with Deadline via Job Scheduling with Cancellation. (with W.T. Chan, T.W. Lam and H.F. Ting)
  Proceedings of the 10th Annual International Computing and Combinatorics Conference (COCOON), 2004, pp. 210--218. [From Springer]
• A Mutation-Sensitive Approach for Locating Conserved Gene Pairs between Related Species. (with H.L. Chan, T.W. Lam, W.K. Sung and S.M. Yiu)
  Proceedings of IEEE 4th Symposium on Bioinformatics and Bioengineering (BIBE), 2004, pp. 545--552. [Download paper (postscript)] [From IEEE]
• Filtering of Ineffective siRNAs and Improved siRNA Design Tool. (with T.W. Lam, Y.C. Mui, S.M. Yiu, H.F. Kung, M. Lin and Y.T. Cheung)
  Proceedings of the 2nd Asia Pacific Bioinformatics Conference (APBC), 2004, pp. 247--255. [Download paper (postscript)] [From ACM]
• Aggressive Online Deadline Scheduling. (with T.W. Lam, T.W. Johnny Ngan and K.K. To)
  Proceedings of the 10th Computing: The Australasian Theory Symposium (CATS), Electronic Notes in Theoretical Computer Science (91), 2004, pp.148--157. [From ScienceDirect]

2003

• On-line Stream Merging in a General Setting. (with W.T. Chan, T.W. Lam and H.F. Ting)
  Invited to Theoretical Computer Science (TCS), 296(1): 27--46, 2003. [Download paper (postscript)] [From ScienceDirect]
• Efficient Algorithms for Optimizing Whole Genome Alignment with Noise. (with T.W. Lam, N. Lu, H.F. Ting and S.M. Yiu)
  Proceedings of the 14th International Symposium of Algorithms and Computation (ISAAC), 2003, pp. 362--374. [From Springer]
• Efficient Constrained Multiple Sequence Alignment with Performance Guarantee. (with Francis Y.L. Chin, N.L. Ho, T.W. Lam and M.Y. Chan)
  Proceedings of the 2nd IEEE Computer Society Computational Systems Bioinformatics Conference (CSB), 2003, pp.337--346. [Download paper (postscript)] [From IEEE]
• On-line Stream Merging, Max Span, and Min Coverage. (with W.T. Chan, T.W. Lam and H.F. Ting)
  Proceedings of the 5th Conference on Algorithms and Complexity (CIAC), 2003, pp.70--82. [From Springer]

2002

• On-line Load Balancing of Temporary Tasks Revisited. (with T.W. Lam, H.F. Ting and K.K. To)
  Theoretical Computer Science (TCS), 270(1-2):325--340, 2002. [Download paper (postscript)] [From ScienceDirect]
• Competitive Analysis of On-line Stream Merging Algorithms. (with W.T. Chan, T.W. Lam and H.F. Ting)
  Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2002, pp.188--200. [From Springer]
• A Unified Analysis of Hot Video Schedulers. (with W.T. Chan, T.W. Lam and H.F. Ting)
  Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), 2002, pp.179--188. [Download paper (postscript)] [From ACM]

2001 and before

• Improved On-line Stream Merging: from a Restricted to a General Setting. (with W.T. Chan, T.W. Lam and H.F. Ting)
  Proceedings of the 7th Annual International Computing and Combinatorics Conference (COCOON), 2001, pp.432--442. [From Springer]
• A 5-Competitive On-line Scheduler for Merging Video Streams. (with W.T. Chan, T.W. Lam and H.F. Ting)
  Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS) - Workshop on Scheduling and Telecommunications (IWST), 2001, pp.2165--2172. [Download paper (postscript)] [From IEEE]
• On-line Load Balancing of Temporary Tasks Revisited. (with K.K. To)
  Proceedings of the 10th International Symposium of Algorithms and Computation (ISAAC), 1999, pp.103--112.
[From Springer]
• An Approximation Algorithm for Bounded Length Tree Linear Broadcast Routing. (with H.F. Ting)
  Proceedings of the 1996 International Conference on Algorithms (ICS), 1996, pp.98--104.
• An Efficient Algorithm for Optimal Linear Broadcast Routing. (with H.F. Ting and M.H. Yau)
  Proceedings of the 5th Italian Conference on Theoretical Computer Science (ICTCS), 1995, pp.235--249.

Presentations

2012

• Energy-aware Algorithms for Computer Systems.
  Computer Science Industrial Symposium, University of Liverpool, Liverpool, UK, June, 2012.
• Energy Efficient Job Scheduling - Speed Scaling and Sleep.
  Departmental Seminar, Xi'an Jiaotong Liverpool University, Suzhou, China, May, 2012.
• Optimizing Busy Time on Parallel Machines.
  The 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Shanghai, China, May, 2012.
• Energy Efficient Job Scheduling with Speed Scaling and Sleep Management.
  Yangtze Microsoft Colloquium on Theoretical Computer Science, Shanghai Jiaotong University, Shanghai, China, May, 2012.
• Online Optimization of Busy Time on Parallel Machines.
  The 9th Annual Conference on Theory and Applications of Models of Computation (TAMC), Beijing, China, May, 2012.

2011

• Energy Efficient Job Scheduling - Speed Scaling & Sleep.
  Departmental Seminar, Durham University, Durham, UK, November, 2011.
• Online Scheduling of Linear Deteriorating Jobs on Parallel Machines.
  The 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), Nymburk, Czech Repbulic, June, 2011.

2010

• Online Coloring in Optical Networks.
  Theory Talk, Max-Planck Institute for Informatics, Saarbrucken, Germany, July, 2010.
• Speed Scaling and Sleep Management to Save Energy.
  DIMAP Seminar, University of Warwick, Coventry, UK, June, 2010.
• Speed Scaling and Sleep Management to Save Energy.
  Bristol Algorithms Days, Bristol, UK, February, 2010.

2009

• On-line Colorings for Minimizing the Number of ADMs in Optical Networks.
  Departmental Seminar, University of Hong Kong, Hong Kong, December, 2009.
• Competitive Multi-Dimensional Dynamic Bin Packing via L-Shape Bin Packing.
  The 7th Workshop on Approximation and Online Algorithms (WAOA), Copenhagen, Denmark, September 2009.
• Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines.
  The 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), Rolduc, Kerkrade, The Netherlands, June 2009.
• On-line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology.
  The 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Piran, Slovenia, May 2009.

2008

• Energy Efficient Flow Time Scheduling.
  Complexity, Theory and Algorithmics Group (CTAG) Seminar, University of Liverpool, Liverpool, UK, October 2008.
• Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count.
  The 16th Annual European Symposium on Algorithms (ESA), Karlsruhe, Germany, September 2008.
• Competitive Non-migratory Scheduling for Flow Time and Energy.
  The 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Munich, Germany, June 2008.
• Energy Efficient Processor Scheduling using Dynamic Speed Scaling.
  Seminar, SIEMENS AG, Munich, Germany, June 2008.
• Non-migratory Multi-processor Scheduling for Flow Time and Energy.
  Dagstuhl Seminar: Scheduling, Dagstuhl, Germany, February 2008.
• Optimal On-line Colorings for Minimizing the Number of ADMs in Optical Networks.
  Theory Group Seminar, Hong Kong University of Science and Technology, Hong Kong, January 2008.

2007

• Online Computation and Competitive Analysis.
  Invited Lecture, COMP 516, Department of Computer Science, University of Liverpool, Liverpool, UK, October 2007.
• Energy Efficient Online Deadline Scheduling.
  Departmental Seminar, Technion, Haifa, Israel, May 2007.
• Optimal On-line Colorings for Minimizing the Number of ADMs in Optical Networks.
  London Stringology Days, King's College London, London, UK, March 2007.
• Energy Efficient Online Deadline Scheduling.
  Complexity, Theory and Algorithmics Group (CTAG) Seminar, University of Liverpool, Liverpool, UK, March 2007.
• Computational Biology - An Algorithmic Approach.
  Invited Lecture, BIOL 725, School of Biological Sciences, University of Liverpool, Liverpool, UK, February 2007.
• Energy Efficient Online Deadline Scheduling.
  Bristol Algorithm Days, University of Bristol, Bristol, UK, February 2007.
• Computational Biology - An Algorithmic Approach.
  Interdisciplinary Research Seminar, School of Biological Sciences, University of Liverpool, Liverpool, UK, February 2007.
• Energy Efficient Online Deadline Scheduling.
  The 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, USA, January 2007.

2006

• Dynamic Bin Packing with no Repacking.
  Lecture Series at National Tsing Hua University, Hsin Chu, Taiwan, December 2006.
• Atomic Selfish Routing in Parallel Link Network.
  Bertinoro Workshop on Adversarial Modeling and Analysis of Communication Networks, Bertinoro, Italy, November, 2006.
• Energy Efficient Online Deadline Scheduling.
  Algorithm Group Seminar, University of Bergen, Bergen, Norway, November, 2006.
• Dynamic Bin Packing with no Repacking.
  ARC Project Workshop, Kiel, Germany, August, 2006.
• Locating Conserved Genes in Whole Genome Scale.
  3rd Haifa Stringology Workshop, Haifa, Israel, May, 2006.
• New Results on Dynamic Bin Packing.
  Departmental Seminar, University of Leicester, Leicester, UK, March, 2006.

2005

• Dynamic Bin Packing of Unit Fractions Items.
  Theory Group Seminar, The Hong Kong University of Science and Technology, Hong Kong, December, 2005.
• Dynamic Bin Packing of Unit Fractions Items.
  Complexity, Theory and Algorithmics Group (CTAG) Seminar, University of Liverpool, Liverpool, UK, December, 2005.
• Algorithmic Issues on Wireless computing.
  University of Liverpool, Liverpool, UK, October, 2005.
• New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling.
  12th Workshop on Applied/Advanced Research in Combinatorial Optimization (ARCO), Lund, Sweden, September, 2005.
• Wireless Communications --- Routing in Geometric Sensor Networks.
  Departmental Seminar, University of Hong Kong, Hong Kong, July, 2005.
• Locating Conserved Genes in Whole Genome Scale.
  DIMACS Workshop on Detecting and Processing Regularities in High Throughput Biological Data, Piscataway, New Jersey, USA, June, 2005.
• Introductory talk on "Wireless Networks" .
  Invited Talk, Scientific and Management Committee Meetings, COST Action 295 DYNAMO , Paris, France, May, 2005.

2004

• On-line Windows Scheduling of Temporary Items.
  The 15th International Symposium of Algorithms and Computation (ISAAC), Hong Kong, China, December, 2004.
• Combinatorial Problems in Whole Genome Alignment.
  Departmental Seminar, University of Liverpool, Liverpool, UK, October, 2004.
• On-demand Broadcasting with Deadline via Job Scheduling with Cancellation.
  Liverpool Algorithmic Afternoon, Liverpool, UK, October, 2004.
• A Mutation-Sensitive Approach for Locating Conserved Gene Pairs between Related Species.
  IEEE 4th Symposium on Bioinformatics and Bioengineering (BIBE), TaiChung, Republic of China, May, 2004.
• Filtering of Ineffective siRNAs and Improved siRNA Design Tool.
  The 2nd Asia-Pacific Bioinformatics Conference (APBC), Dunedin, New Zealand, January, 2004.
• Aggressive Online Deadline Scheduling.
  The 10th Computing: The Australian Theory Symposium (CATS), Dunedin, New Zealand, January, 2004.

2003

• Efficient Algorithms for Optimizing Whole Genome Alignment with Noise.
  The 14th International Symposium of Algorithms and Computation (ISAAC), Kyoto, Japan, December, 2003.
• Optimization Problems in VOD Stream Merging and Whole Genome Alignment.
  The University of Liverpool, Liverpool, UK, November, 2003.

2002

• Competitive Analysis of On-line Stream Merging Algorithms.
  The 27th International Symposium on Mathematical Foundations of Computer Science (MFCS), Warsaw, Poland, August, 2002.
• A Unified Analysis of Hot Video Schedulers.
  The 34th ACM Symposium on Theory of Computing (STOC), Montreal, Canada, May, 2002.

2001 and before

• A 5-Competitive On-line Scheduler for Merging Video Streams.
  The 15th International Parallel and Distributed Processing Symposium (IPDPS), Los Angeles, California, USA, April, 2001.
• On-line Load Balancing of Temporary Tasks Revisited.
  The 10th International Symposium of Algorithms and Computation (ISAAC), Chennai, India, December, 1999.
• An Approximation Algorithm for Bounded Length Tree Linear Broadcast Routing.
  The 1996 International Conference on Algorithms (ICS), Kaohsiung, Republic of China, December, 1996.
• An Efficient Algorithm for Optimal Linear Broadcast Routing.
  The 5th Italian Conference on Theoretical Computer Science (ICTCS), Ravello, Italy, November, 1995.