Title of article :
Online Learning Approaches in Maximizing Weighted Throughput in an Unreliable Channel
Author/Authors :
Zhang, Zhi George Mason University - Department of Computer Science, USA , Li, Fei George Mason University - Department of Computer Science, USA
From page :
567
To page :
574
Abstract :
We design online algorithms to schedule unit-length packets with values and deadlines through an unreliable communication channel. In this model, time is discrete. Packets arrive over time; each packet has a non-negative value and an integer deadline. In each time step, at most one packet can be sent. The ratio of successfully delivering a packet depends on the channel’s quality of reliability. The objective is to maximize the total value gained by delivering packets no later than their respective deadlines. In this paper, we conduct theoretical and empirical studies of online learning approaches for this model and a few of its variants. These online learning algorithms are analyzed in terms of external regret. We conclude that no online learning algorithms have constant regrets. Our online learning algorithms outperform online competitive algorithms in terms of algorithmic simplicity and running complexity. In general, these online learning algorithms work no worse than the best known competitive online algorithm for maximizing weighted throughput in practice.
Keywords :
online learning algorithm , unreliable communication channel , competitive online algorithm
Journal title :
Tsinghua Science and Technology
Journal title :
Tsinghua Science and Technology
Record number :
2535497
Link To Document :
بازگشت