[6-3]Short courses on Approximation Algorithms

Date:2008-05-28

Speaker：Prof Ding-Zhu  Du

Venue：Lecture room, level three,
Time：16:00 -- 18:00pm, June, 3

          16:00 -- 18:00pm, June, 4

Abstract：

Advances in Analysis and Design of Approximation Algorithms

(4 lectures, each for one hour)

(1) Virtual Bachbone in Wireless Sensor Networks:  connected dominating set in unit disk graph

Ding-Zhu Du    (Xi’an Jiaotong University and Univ. of Texas at Dallas)

The virtual backbone plays an important role in wireless sensor networks. While a wireless sense network is formulated as a unit disk graph, its virtual backbone is a connected dominating set, which has been studied extensively in the literature. Most of
  existing distributed approximation algorithms are in two stages. In this talk, we introduce updated results in this research  direction. 
  

(2)  Double Partition: (6+\varepsilon)-approximation     for minimum weight dominating set  in unit disk graph

Ding-Zhu Du   (Xi’an Jiaotong University and Univ. of Texas at Dallas)

It was long-standing open problem whether the minimum weight dominating set in unit disk graph has a polynomial-time approximation with  constant performance ratio. Recently, this problem was solved by  Amb\"{u}hl et al. who gave a 72-approximation. In this talk, we introduce a new technique, double partition. With this technique, we obtain a (6 + \varepsilon)-approximation for any \varepsilon > 0.

(3) Analysis of Greedy Approximation with Nonpotential Functions: minimum connected dominating set in graphs and hypergraphs

Ding-Zhu Du  (Xi’an Jiaotong University and Univ. of Texas at Dallas)

Greedy approximations for the minimum connected dominating set in graphs  and hypergraphs have a non-submodular potential functions, which induces a problem: how to analyse greedy approximation with non-submodular potential functions? In fact, there exist many greedy algorithms in the literature. But, not many of them can be successfully analysed. Although  there are many methods to analyse greedy algorithms, most of them are  suitable only for those greedy algorithms with submodular potential functions. In a recent work of our research group, we introduce a new  method which can analyze a large class of greedy approximations with nonsubmodular potential functions, including the minimum connected dominating set in graphs and
  hypergraphs

  
(4) Spider Decomposition: the minimum strongly-connected dominating  set in directed graphs

Ding-Zhu Du   (Xi’an Jiaotong University and Univ. of Texas at Dallas)

Spider decomposition was proposed by Ravi (CMU) to design approximations for node-weighted Steiner tree. Recently, our research group designed (2+3\ln n)-approximation for the minimum strongly-connected dominating set in directed graphs with this approach. In this talk, I’m going to introduce this work.