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).