Algorithms & Theory Meeting

Term: Fall 2009
Time: Fri 10:00am - 11:30am
Location: HEC102
Date Topics Notes
#1
10/09
Pawel Wocjan
Game Tree Evaluation
Analysis of a randomized algorithm for evaluating binary uniform AND-OR trees
Section 2.1 in Randomized Algorithms by Motwani and Raghavan
#2
10/16
Pawel Wocjan
The Minimax Principle
Game theory; von Neumann's Minimax Theorem; Loomis' Theorem
Sections 2.1 - 2.2.1 in Randomized Algorithms by Motwani and Raghavan
#3
10/23
Raymond Yiu Yu Ho
Introduction to Online Algorithms
Deterministic online paging algorithms
Chapter 1 & 3 in Online Computation and Competitive Analysis by Borodin and EL-Yaniv
#4
10/30
Stephen Fulwider
Introduction to Online Algorithms
Randomized online paging algorithms
Chapter 4 in Online Computation and Competitive Analysis by Borodin and EL-Yaniv
11/06 No Lecture

#5
11/13
Paul Wiegand
Introduction to randomized algorithm analysis of evolutionary computation

References:
 
#6
11/20
Paul Wiegand
Introduction to randomized algorithm analysis of evolutionary computation
 
11/27 No Lecture (Thanksigiving Holidays)

#7
12/04
Pawel Wocjan
The Minimax Principle
Yao's Minimax Principle; Lower bound on game tree evaluation
Sections 2.2.2 - 2.2.3 in Randomized Algorithms by Motwani and Raghavan
#8
12/11
Stephen Fulwider
Approximation Algorithms via Linear Programming Relaxation
 
#9
12/18
Pawel Wocjan | Raymond Yiu Yu Ho
Presentation of the article AdWords and Generalized On-line Matching
Abstract: How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1-1/e for this problem.