The Approximate Algorithm Of Hypergraph Embedding Problem

In fiber-optic communication, wavelength-division multiplexing (WDM) is a technology which multiplexes multiple optical carrier signals on a single optical fiber by using different wavelengths of last light to carry different signals. WDM technology plays an important role in the telecommunication world. We model the communication network as a graph. For each request of the communication, where a request is defined by a pair of network nodes, a source and a destination, we need to choose a communication path to serve this request. A routing for a set of communication requests is such a collection of paths. But in general, each communication request contains more than two nodes of the network. So we model these requests as a hypergraph, each request is a hyperedge of the hypergraph. We want to find a routing algorithm to realize the communication requests, in other words, we want to find a routing path in the network to con-nect the nodes in each hyperedge. The most important issue in designing the routing algorithm is to minimize the maximal congestion-the number of paths passing through any single link in the network. This problem is called a Rout-ing Wavelength Assignment (RWA) problem. If we restrict the network on a ring network, we will get a kind of problem which called Minimum Congestion Hypergraph Embedding in a Cycle (MCHEC). This problem is widely used in practice and it have been well studied. The weighted version of MCHEC problem is totally a new one. For example, we give every hyperedge or every edge of the cycle a weight. This kind of problem is more common, and much more difficult obviously. We advance the problem of Minimum Congestion Hypergraph Em-bedding in a Weighted Cycle (MCHEWC) for the first time. And in practice, the hyperedge may be have a direction, so we also study this directed vision of hypergraph embedding problem. All these problems are NP-complete, so we want to design polynomial time approximation scheme to these problem. In this dissertation, we study several general problems of MCHEC. We split the disser-tation into five chapters. In Chapter 1, we introduce the background of MCHEC problem, some basic definitions of algorithm, the related optimization problems of MCHEC and the development of this kind of problem. In Chapter 2, we pro-pose the problem of Minimum Congestion Hypergrph Embedding in a Weighted Cycle, and present two kind of simple and very efficient 2-approximation algo-rithm for the MCHEWC problem. At first, we formulated it as an integer linear program(NILP*) and a 2-approximation solution can be obtained by using LP-relation and rounding heuristic. Then we develop a linear time approximation algorithm which is also provide a solution with the same worst case approxima-tion bounds as LP-approximation.Theorem 0.0.1.The maximum congestion of the NILP*-based rounding algorithm is at most two times the optimum for the MCHEC, MCGEWC(graph embedding in a weighted cycle) and MCHEWC problems.Theorem 0.0.2.The maximum congestion of the weightest-edge-removing algorithm is at most two times the optimum for the MCHEC, MCGEWC and MCHEWC problems.In Chapter 3, we study MCHEWC problem deeply, and resolve it com-pletely. We present a Polynomial Time Approximation Scheme (PTAS) for the MCFEWC problem. In the process of the PTAS, we partition the hyperedges and the edges of the cycle into two parts separately. By using LP relaxation, derandomization techniques and other artifice. We obtain the following lemma and theorem.Lemma 0.0.3.Let X1,X2,...,Xn be n independent random 0-1 variables, where Xi takes 1 with probability pu 0< Pi< 1. Let X=?i=1niXi,0<ai< 1, and?=E[X]. Then for any 0<?<1/2, Pr(X>/?+?n)< exp{-1/3n?2}.Theorem 0.0.4.There is a PTAS to the MCHEWC problem. In Chapter 4, we work with the problem of embedding a directed hypergraph in a tree of ring (DHETR). Such problem is NP-complete and we present a PTAS for the problem.Theorem 0.0.5.There is a PTAS for the DHETR problem.In Chapter 5, we propose the problem of Minimum Congestion Weighted Hypergraph Embedding in a Weighted Cycle (MCWHEWC). This is the most general version of MCHEC problem and the most difficult problem. We give a reasonable restriction on the weight of the hyperedge and present a PTAS to it. Every Chapter of this dissertation is novelty and is a innovation of the MCHEC problem. We solve the series of MCHEC problems completely in some degree.