Group:Theory Lunch
Title:Scheduling Problem in Wireless Sensor Network, Optimal Algorithms and Inapproxim
Speaker: Zhaoquan Gu, Zhe Yang University
Time: 2010-12-29 12:00-2010-12-29 13:30
Venue:FIT 1-222

Abstract:

Title : Scheduling Problem in Wireless Sensor Network

Abstract: Wireless Sensor Network has been more and more important and useful nowadays. As one of the main problems, scheduling has attracted many researchers' attention. In this talk, I will give the definition about the problem and show the difference that two models affect. Also I will introduce several power assignment methods and their property and show some result in solving scheduling capacity problem.

Title: Optimal Algorithms and Inapproximability Results for Every CSP?

Abstract: It's well known that MAX-CUT can be approximated by a factor of 0.878... by Goemans Williamson's algorithm. And [KKMO07] figured out that it's NP-Hard to do better than GW's algorithm by assuming Unique Games Conjecture and Majority is the stablest theorem. Later P. Raghavendra proved the similar result for general CSP problem by "Invariance Principle". I'll present its SDP rounding algorithm and the hardness reduction roughly. The detail of Invariance Principle can be find in [Mossel-ODonnell-Oleszkiewicz] at http://www.cs.cmu.edu/~odonnell/papers/invariance.pdf .