ECE Seminar Series: Rethinking Competitive-Ratio: Two Case Studies, I-Hong Hou, TAMU (698/699) , March 21, 2017, 4:00 PM - 5:00 PM
Electrical and Computer Engineering
Network applications in highly mobile systems need to employ online algorithms that do not rely on precise predictions about future events. In order to meet hard performance guarantees in the presence of unknown future events, common practice is to add redundancy to the systems. In this paper, we define a new competitive ratio that reflects the amount of redundancy needed to ensure some given performance guarantees. We study two special applications, namely, online job allocations in cloud computing and online scheduling in delayed mobile offloading, and propose online algorithms for each of them. We prove that our algorithms are optimal. By comparing our algorithms with commonly used other policies, we also show that our policies need much less redundancy than those commonly used policies to provide the same degree of performance guarantees.
I-Hong Hou is an assistant professor in the ECE Department of the Texas A&M University. He received his Ph.D. from the Computer Science Department of the University of Illinois at Urbana-Champaign. His research interests include wireless networks, real-time systems, and cloud computing. He received the C.W. Gear Outstanding Graduate Student Award from the University of Illinois at Urbana-Champaign, and the Silver Prize in the Asian Pacific Mathematics Olympiad.