Abstract:

Given a weighted complete graph G_K(V,E_K), we study a network design problem to find an edge set E⊆ E_K such that the graph G(V,E) is connected. The power of a vertex u in G is equivalent to the maximum of the weights of the edges in E incident with u. Minimizing the maximum vertex power is known to be polynomial time solvable. In this talk, for any fixed ε>0 we present a (3/2+ε)-approximation algorithm for minimizing the number of vertices with the minimized maximum vertex power (critical vertices), whose decision version is NP-complete. Our result yields an improvement over the previously best approximation ratio of 5/3. Our worst case analysis is based on construction of the augmented instances. We show that any solution E delivered by our approximation algorithm for an arbitrary instance is also a solution by our approximation algorithm for an augmented instance, which enables us to find better lower bounds for the optimal solution of the original instance. We develop integer programs with nonlinear objectives covering all possible instances, whose solutions provide the improved approximation ratio. We also show that our result is tight.