Approximation algorithms for scheduling problems with multi-type contentions and related problems

Scheduling problem is a fundamental and versatile problem in theoretical computer science. It has been extensively studied in many different variations. Most of existing scheduling models only deal with one type of resources, i.e., the machines. However, in many applications, besides the machines, there are other types of critical resources that the jobs may compete for. Different types of resources cause different types of contentions, and the contentions could interfere with each other, which complicate the problem dramatically. In this dissertation, we study the scheduling problems with multi-type contentions and several related problems.; The first problem we study is the job interval selection with multi-type contentions (JISMC), which is an interesting generalization of the classic JIS problem. In JISMC, each job is represented by a set of intervals and may compete for a set of critical resources. We present a family of approximation algorithms for solving several variants of the problem by using a generic algorithmic framework. Our algorithms achieve a constant approximation ratio (i.e., 3) when there is only one type of resources or certain dependency relation exists among multiple types of resources. When the r resources are unrelated, the approximation ratio of our algorithm becomes k+2, where k < r is a constant depending on the problem instance. As an application, we also show that our techniques can be easily applied to optical burst switching (OBS) networks to design more efficient wavelength scheduling algorithms.; The second problem we study is the interference aware broadcast problem in multihop wireless networks. To design a broadcast protocol in such a network, two key issues are radio collision and interference. Previous works only consider the case that the interference range of a node is same as its transmission range, we study the more general model in which the interference range of a node is larger than its transmission range. We develop a simple and yet efficient collision-free and interference-free algorithm to achieve a constant approximation for the case that the interference range is twice the transmission range. For the more general case that the ratio between the interference range and the transmission range is an arbitrary constant alpha, the approximation ratio becomes O(alpha2). Based on the single source single message scheduling algorithm, we propose two algorithms to the single source multiple messages and multiple sources multiple messages scheduling problems. Experimental results show that our algorithms perform better than previous approaches under both the ideal unit disk graph model and the more realistic radio irregularity model.; The third problem we study is the determination of robustness of k-gon Voronoi diagram construction. As an important tool, Voronoi diagram has been frequently used in the designing of efficient routing and scheduling algorithms in wireless networks and many other applications. We present a plane sweep algorithm for constructing the Voronoi diagram of a set of non-crossing line segments in 2-D space using a distance metric induced by a regular k-gon and study the robustness of the algorithm. Following the algorithmic degree model, we show that the Voronoi diagram of a set of arbitrarily oriented segments can be constructed with degree 14 for certain k-gon metrics (e.g. k = 6, 8, 12), which dramatically improve the previous result of degree 40 under the Euclidean metric. For slightly restricted inputs, the degree further reduces to 2.