讨论组:研究生会议
标题:Approximation algorithm and Bounds for General Art Gallery Problems and related
演讲人: 郝霄虹,刘可
时间: 2011-04-14 12:00-2011-04-14 14:00
地点:FIT 1-222

内容:

Title: Approximation algorithm and Bounds for General Art Gallery Problems and related problems in Wirless Sensor Networks

 

Abstract: We study the problem of covering a two-dimensional spatial region P, cluttered with occluders, by sensors. A sensor placed at a location p covers a point x in P if x lies within sensing radius r from p and x is visible from p, i.e., the segment px does not intersect any occluder. The goal is to compute a placement of the minimum number of sensors that cover P. We propose landmark-based approach for covering P. Suppose P has $\tau$ holes, and it can be covered by h guards. Given a parameter $\epsilon>0$, let $\lambda:= \lambda(h,\epsilon)=(h/\epsilon)log  \tau$. We prove that one can compute a set L of $O(\lambda log^{2}\lambda)$ landmarks so that if a set S of sensors covers L, then S covers at least $(1 - \epsilon)$-fraction of P. It is surprising that so few landmarks are needed, and that the number does not depend on the number of vertices in P. We then present efficient randomized algorithms, based on the greedy approach, that, with high probability, compute $O(\tilde{h} log\lambda)$ sensor locations to cover L; here $\tilde{h} \leq h$ is the number sensors needed to cover L. We propose various extensions of our approach, including:? (i) a weight function over P is given and S should cover at least $(1 - \epsilon)$ of the weighted area of P?ii) each point of P is covered by at least t guards, for a given parameter t=1.

 

Title: Polarization-Entangled Photon Pair Generation

 

Abstract: Polarization-entangled photon pair generation based on two scalar scattering processes of the vector four photon scattering has been demonstrated experimentally in high nonlinear microstructure fiber with birefringence. By controlling the pump polarization state, polarization-entangled Bell states can be realized. It is provides a simple way to realizeefficient and compact fiber based polarization-entangled photon pair sources. In this talk, I will introduce how to produce a fiber-based source of polarization-entangled photon pairs that is well suited for quantum communication applications in the 1.5m band of standard telecommunication fiber.