讨论组:研究生会议
标题:Learning Submodular Function,Quadratic Algorithm for Finding the Maximum Area Pa
演讲人: 胡巍,金恺
时间: 2011-03-17 12:00-2011-03-17 14:00
地点:FIT 1-222

内容:

Title: Learning submodular function

Abstract: Let f:2^A->R be a function from sets to real number. If for any S,T\subset A, f(S\cup T) + f(S\cap T) >= f(S) + F(T), f is a submodular function. Submodular function can be viewed as the second moment of monoton function. In the lunch meeting, I will introduce the submodular function

Title: Quadratic Algorithm for Finding the Maximum Area Parallelogram

Abstract: We consider the problem of finding the maximum area parallelogram (MAP) inside a convex polygon. We give an algorithm for computing the MAP in an n-sided polygon in time O(n^2), a considerable improvement over the straightforward algorithm which runs in time O(n^4). We achieve our results by proving new structural properties of the MAP, and combining them with a rotating technique introduced by Toussaint [Tou83].

Last time in theory lunch I've gave a proof that the area of the MAP is always at least 2/ times the area of the maximum area centrally-symmetric convex body(MACC) inside it. Thus, our algorithm for finding the MAP yields a 2/ -approximation algorithm for finding the MACC inside a convex polygon. This time I'll mainly talk about the techniques using in our algorithm that improve the running time from O(n^4) to O(n^2).