Almost sure asymptotic optimality for online routing and machine scheduling problems

✍ Scribed by Patrick Jaillet; Michael R. Wagner

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 157 KB
• Volume: 55
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.20309

✦ Synopsis

Abstract

In this article, we study algorithms for online routing and machine scheduling problems. The problems are “online” because the problem instances are revealed incrementally. We first study algorithms for the online Traveling Repairman Problem (TRP), where a single server is to visit a set of locations in a network with the objective of minimizing the sum of weighted completion times. We then analyze well‐known online algorithms for a variety of machine scheduling problems, which are appropriate models for many network optimization problems; in the scheduling notation of Graham et al. 18, we consider 1|r~j~,p____m____t____n|∑~j~w~j~C~j~, 1|r~j~|∑~j~w~j~C~j~, Q|r~j~,p____m____t____n|∑~j~C~j~, P|r~j~|∑~j~C~j~, Q|r~j~,p____m____t____n|∑~j~w~j~C~j~ and Q|r~j~|∑~j~w~j~C~j~. We introduce general probabilistic assumptions about the problem data as a tool to study the online algorithms for these online combinatorial problems. The algorithms do not utilize the underlying probabilistic assumptions in any way. We prove that these online algorithms are almost surely asymptotically optimal. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010