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-negat...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.展开更多
基金Supported by US National Science Foundation (Nos. CCF-0915681 and CCF-1146578)DARPA’s Mission-Resilient Clouds Program under Contract 1FA8650-11-C-7190
文摘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.
