In this thesis, we are concerned with competitive analysis used in various optimization problems, especially, in deadline scheduling and broadcasting. The competitive analysis provides a criterion to decide which algorithm is better. In particular, the algorithms do not have full information about the input instance in advance. A lot of algorithms face with this environment in practice. As a typical example, we may refer to online algorithms; as input data are given over time, the online algorithm makes decisions without any information about the data given in the future. In this environment, the performance of algorithms with partial information about the input instance is compared with that of the optimal algorithm with full information about the input instance. For the online algorithms, their performance is compared with that of the optimal offline algorithm, which knows all input data in advance and gives the optimal solution.
This thesis deals with problems about two different topics; deadline scheduling and broadcasting. For deadline scheduling, we study online scheduling of jobs with deadlines. The goal is to maximize the total weight of jobs completed by their deadlines. First, we consider online preemptive and non-preemptive job scheduling depending on whether preemption for each job is allowed or not, respectively. The online scheduling algorithms, Earliest Deadline First(EDF) and Earliest EXpiration Time First(EXF), are investigated in a single machine and multiple machines setting. Also we apply the resource augmentation model to the problems, where the online algorithm can use faster machines than the optimal offline algorithm. Second, we consider the problem of scheduling broadcasts in data delivering systems via broadcast. In this problem, a number of requests for a data can be simultaneously satisfied by one broadcast of a server. The clients of requests may leave the system if their requests are still unsatisfied after waiting for some time, that is, each request has a deadline. We present online algorithms achieving constant competitive ratios.
For broadcasting, we first study a variant of broadcasting; each node in a network has a predetermined ordered list of neighbors regardless of the node, called the source, from which the message is originated to be transmitted to all other nodes and it transmits a received message to neighbors in order of the list. It is called the broadcasting with universal lists. We adapt the competitive analysis to this problem and derive new broadcasting algorithms for lines, complete k-ary trees, grids, complete graphs, and hypercubes. Also we study the gossiping problem in two-dimensional meshes under one-port telephone model. The algorithm is based on very simple idea and improves on the best known result.
이 논문에서 우리는 마감시간 스케줄링과 브로드캐스팅과 같은 최적화 문제들에서의 컴페티티브 분석에 관하여 연구한다. 특별히 알고리즘들은 미리 입력 데이터에 관한 충분한 정보를 가지고 있지 않다. 실제로 많은 알고리즘들이 이러한 상황에 직면하게 된다. 전형적인 예로서, 온라인 알고리즘이 있다. 이때, 입력 데이터들은 시간이 지남에 따라 주어지고, 온라인 알고리즘은 미래에 주어질 데이터에 관한 아무런 정보 없이 결정을 내리게 된다. 이런 불충분한 정보를 가진 알고리즘들의 성능은 완전한 정보를 가진 최적 알고리즘의 성능과 비교된다.
이 논문은 두가지 다른 주제인 마감시간 스케줄링과 브로드캐스팅에 관한 문제들을 다룬다. 마감시간 스케줄링에 관해서 각 작업들은 수행을 끝내야 하는 마감시간을 가지고 우리는 마감시간안에 끝낸 작업들의 가중치 합을 최대화하는 온라인 스케줄링에 관하여 연구한다. 우리는 온라인 알고리즘들인 Earliest Deadline First(EDF)와 Earliest EXpiration Time First(EXF)에 관하여 각각 한 대의 머신과 여러 대의 머신 모델에서 연구한다. 또한 우리는 온라인 알고리즘이 최적 알고리즘보다 빠른 머신을 사용할 수 있는 모델에 관하여 연구한다. 다음으로 브로드캐스팅으로 데이터를 전달하는 시스템에서 브로드캐스팅 스케줄링에 관해서 연구한다. 이 문제에서 동일한 데이터에 대한 리퀘스트들은 한 번의 브로드캐스팅으로 만족될 수 있다. 이 때, 리퀘스트들은 일정 기간동안 만족되지 않으면 시스템을 떠날 수 있다. 다시말해, 마감시간들을 가진다. 우리는 상수 컴페티티브 비를 가지는 온라인 알고리즘들을 제안한다.
브로드캐스팅에 관해서 우리는 우선 하나의 변형을 연구한다. 네트웍의 정해진 하나의 시작노드는 다른 모든 노드들에 자신의 정보를 전달해야 하고, 각각의 노드는 시작노드에 상관없이 정보를 전달하는 일정한 순서리스트를 가진다. 우리는 이 문제에 컴페티티브 분석을 적용하고 여러 특별한 그래프들의 새로운 브로드캐스팅 알고리즘들을 제안한다. 또한, 우리는 이차원 메쉬에서의 가십핑 알고리즘에 관해서 연구한다. 이 알고리즘은 단순하면서 이전 결과보다 나은 성능을 가진다.
