Title: Analysis of Greedy Approximation with Non-submodular Potential

Speaker: My Thai

Time: 3:00PM - 4:00 PM, Sep. 29, 2006

Place: CSE 404

ABSTRACT:

"Greedy" is a simple and popular strategy to design approximation algorithms. There are many greedy algorithms in literature but not many of them have approximation analysis. A greedy algorithm with theoretical analysis usually has a submodular potential function. In this talk, I will present a technique to analyze the greedy algorithms with non-submodular potential functions.