Covering the Edges of Bipartite Graphs Using K2,2 Graphs
We consider an optimization problem arising in the design of optical networks. We are given a bipartite graph G = (L,R,E) over the node set L ∪ R where the edge set is E ⊆ { [u,v]: u ∈ L, v ∈ R}, and implicitly a collection of all four-nodes cycles in the
- PDF / 526,028 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 111 Downloads / 269 Views
Department of Industrial Engineering and Operations Research and Walter A. Haas School of Business, University of California, Berkeley [email protected] 2 Department of Statistics, The Hebrew University, Jerusalem, Israel [email protected]
Abstract. We consider an optimization problem arising in the design of optical networks. We are given a bipartite graph G = (L, R, E) over the node set L ∪ R where the edge set is E ⊆ {[u, v] : u ∈ L, v ∈ R}, and implicitly a collection of all four-nodes cycles in the complete graph over V . The goal is to find a minimum size sub-collection of graphs G1 , G2 , . . . , Gp where for each i Gi is isomorphic to a cycle over four nodes, and such that the edge set E is contained in the union (over all i) of the edge sets of Gi . Noting that every four edge cycle can be a part of the solution, this covering problem is a special case of the unweighted 4-set cover problem. This specialization allows us to obtain an improved approximation guarantee. Whereas the currently best known approximation algorithm for the general unweighted 4-set cover problem has an ≈ 1.58077 (where Hp denotes the p-th approximation ratio of H4 − 196 390 harmonic number), we show that for every > 0 there is a polynomial + )-approximation algorithm for our problem. Our analysis of time ( 13 10 the greedy algorithm shows that when applied to covering a bipartite graph using copies of Kq,q bicliques, it returns a feasible solution whose cost is at most (Hq2 − Hq + 1)OP T + 1 where OP T denotes the optimal cost, thus improving the approximation bound by a factor of almost 2. Keywords: Approximation algorithms, network design, set cover.
1
Introduction
In the area of designing optical networks, one of the issues is how to pack the demands on each link into optical channels. At each node there are digital routers limited in their capabilities and they can only pack demands on a link together if they arrive from up to q different directions, or go to up to q different directions. For edge e = [u, v] the demands going through this edge are described in terms of the paths they follow through the edge, such as {a, e, c} or {b, e, d}, as in Figure 1. Due to technical limitations of the optical routers this value of q is typically 2 or 3. The problem is to route all demands through an edge with minimum number of optical routers.
Research supported in part by NSF award No. DMI-0620677 and CBET-0736232.
C. Kaklamanis and M. Skutella (Eds.): WAOA 2007, LNCS 4927, pp. 116–127, 2008. c Springer-Verlag Berlin Heidelberg 2008
Covering the Edges of Bipartite Graphs Using K2,2 Graphs
117
Fig. 1. A demonstration of a valid packing of demands on one edge in the optical network design problem with q = 2
Consider an abstraction of this problem for an edge e = [u, v] with a bipartite graph, B = (V1 ∪V2 , E) that has the set of nodes V1 each representing all the edges incoming (adjacent) to u except for edge e, and the set of nodes V2 representing all the edges adjacent to v except for edge e. Each demand going
Data Loading...
