Optimization and Approximation under Partial Information
Sudipto Guha, UPenn
October 26, 2007, 3:30PM, Wean 7220
Abstract:
If you had to bet on a race — and you have ten minutes before the race begins, which contestants would you chat to for information? Would you decide on the sequence of contestants you would talk to upfront or choose adaptively? Coincidentally, this same problem and its variants appear in several applications such as databases, planning, and sensor networks, where parameters such as selectivity, load, or sensed values are known only with some associated uncertainty. The performance of such a system, as captured by some objective function over the parameters, is significantly improved if some of these parameters can be probed or observed. In a resource constrained situation, deciding which parameters to observe in order to optimize system performance itself becomes an interesting and important optimization problem. This problem and its variants are the focus of this talk where we will consider them through the lens of approximation algorithms.
Title: The Directed Orienteering Problem
Speaker: Viswanath Nagarajan
When: October 25, 16:30-17:30
Where: Wean Hall 5302
Abstract:
We consider the orienteering problem on asymmetric metrics: given a directed metric (V,d), a starting vertex s, an ending vertex t, and a length bound D, find an s-t path having length at most D that maximizes the number of vertices covered. We give an approximation algorithm for this problem achieving a guarantee of O(log^2 n). The previously best known result was an O(log n)-approximation algorithm that runs in quasi-polynomial time (Chekuri & Pal ‘05). For the undirected special case of this problem, a 3-approximation algorithm was known (Bansal et al. ‘04). Our result answers positively the question of poly-logarithmic approximability of the directed orienteering problem (Blum et al. ‘03). This is joint work with R. Ravi.
Who: Maverick Woo
Where: NSH 1507
When: Noon, 2007-10-24
Title: Having Fun with Inverse Ackermann Functions
Abstract:
In this talk we will familiarize ourselves with the inverse Ackermann functions through examples other than the classic Union-Find data structure. We will focus on intuition and also attempt to pick up interesting nuggets from the vast literature using/concerning these functions. No tedious computation will ensue.
