Abstract
解線上問題的線上演算法是近年來相當重要的研究主題。線上演算法的資料是一筆一筆地進來，每當一筆資料進來後就必須在不影響以前所作的決策的條件下馬上處理該筆資料，而且此種演算法對未到達資料毫無所悉。如此，因為無法掌握所有資料完整的資訊，線上演算法得到的解答往往不是離線最佳解。在此吾人關心的是線上演算法得到的解答有多好。競爭分析法是目前最常用來評估線上演算法的最差效益。此分析法是在找出線上演算法所花的成本和離線最佳解的成本之最差比值。本論文還將介紹能達到良好競爭性的典型的線上演算法設計方法 -- 貪婪法、平衡法、補償法、中庸法、消去法。論文中將以演算法實例說明各設計方法的精神，也將介紹這些演算法實例的分析計巧。許多的線上應用問題（如即時系統）要求當資料到達後的處理時間要越短越好，所以解這些線上問題的線上演算法應要在每一決策步驟花短的時間及用少的記憶空間。根據此要求，在每一決策步驟採用隨機方法能符合花短的時間及用少的記憶空間的需求。因此本論文以隨機線上演算法為研究重點。雖然在目前的文獻中大多以最差效益（競爭分析法）來評估線上演算法的效益，但是這些所找出的極端最差的資料在許多的應用中是很少出現的。因此對實際的應用問題，線上演算法的平均效益會是很重要的效益指標。在論文中，吾人將以平均效益來衡量線上演算法的效益，亦即在資料是依某機率分佈所產生的情形下找出線上演算法所花的成本和離線最佳解的成本之最差比值。首先吾人提出一解線上擴展樹問題於平面上n 個點的隨機線上演算法R(m)，其中1<= m<=n-1 。當一新的點進來後，此演算法需要O(m)時間來決定此新點與某點相連接。吾人將證明當m 是常數時，演算法R(m)的競爭比值是Θ(n)。 再者，吾人於所有n個點是均勻地且獨立地分佈在一個單位圓內的假設下，導出一個此線上演算法所造出的樹的成本和離線最佳樹的成本之最差比值。另外，吾人也提出一解線上最小兩堆配對問題於平面上2n個點的隨機線上演算法RM(m)，其中每堆有n個點， 1<=m<=n 。吾人將證明演算法RM(m)不是競爭的線上演算法，但是於所有2n個點是均勻地且獨立地分佈在一個單位圓內的假設下，吾人證明此線上演算法所花的配對成本和離線最佳的配對成本之最差比值是O(n)。An on-line algorithm accepts data in an on-line manner,processes the current data immediately without changing theprevious decisions and has no future knowledge about unarrivingdata. In such a circumstance, it is hard for an on-linealgorithm to obtain the off-line optimal solution, because ofthe incomplete information of data. We here are interested inthe solutions resulted by on-line algorithms. The competitiveanalysis has been widely used to evaluate the worst caseperformance of an on-line algorithm, which is to find the worstratio between the cost incurred by the on-line algorithm andthe off-line optimal cost for all data instances. In thisdissertation, we propose a randomized algorithm $R(m)$ for theon-line spanning tree problem on $n$ points in the Euclideanplane, where $1\le m \le n-1$. When a point arrives, thealgorithm runs $O(m)$ time to decide which point to be linkedto the new point. We shall prove that Algorithm $R(m)$ isi$\Theta(n)$-competitive for $m$ is a constant. Moreover, weshall present a function of $m$ and $n$ for the upper bound ofthe ratio between the length of the tree constructed byAlgorithm $R(m)$ and the length of a minimum spanning tree,under the assumption that the $n$ points are given uniformlyand independently in a unit disk. Next, we shall propose arandomized algorithm, Algorithm $RM(m)$, for the on-lineminimum bipartite matching problem on $2n$ points in theEuclidean space, where each bipartition has $n$ points. Weshall prove that Algorithm $RM(m)$ is not competitive for $1\lem \le n$, but we shall show that the length of a matchingproduced by Algorithm $RM(m)$ is bounded by $O(n)$ times thelength of the minimum matching, under the assumption that the$2n$ points are given uniformly and independently in a unitdisk.