Speaker: John Hooker, Professor of Operations Research
Title: Duality in Optimization and Constraint Satisfaction
Date: Friday, October 13, 2006
Time: 1:30 to 3:00 pm
Place: Room 384 Posner Hall
In this talk I attempt to unify the various duals that have been developed in optimization and constraint satisfaction. I show that they can be classified as inference duals, relaxation duals, or both. They include linear programming, surrogate, Lagrangean, superadditive, and constraint duals, as well as duals defined by resolution and filtering algorithms. Inference duals give rise to nogood-based search methods (such as Benders decomposition) and sensitivity analysis, while relaxation duals provide bounds. This analysis shows that duals may be more closely related than they appear, as are surrogate and Lagrangean duals. It also reveals common structure between solution methods, such as Benders decomposition and Davis-Putnam-Loveland methods with clause learning. It provides a framework for devising new duals and solution methods.
Friday, October 13th, 2006
WEH 7220, 3:30pm
Dispersion of Mass and the Complexity of Randomized Algorithms
Santosh Vempala
Faculty, Georgia Tech
How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in $\R^n$ (the current best algorithm has complexity roughly $n^4$, conjectured to be $n^3$). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing.
This is joint work with Luis Rademacher.
SPEAKER: Viswanath Nagarajan
TIME: Wednesday 12-1pm, October 11, 2006
PLACE: NSH 1507
TITLE: Approximating the Dial-a-Ride problem
ABSTRACT:
The Dial-a-Ride problem is the following: given an $n$ vertex metric space, $m$ objects each specified by a source-destination pair, and a vehicle of capacity $k$, find the minimum length tour that moves each object from its source to destination such that there are at most $k$ objects in the vehicle at any point in the tour. The tour is said to be non-preemptive if each object, once picked up at its source is dropped only at its destination. The tour is said to be preemptive if each object can be dropped at intermediate vertices before being delivered at its destination.
We give an approximation algorithm for the non-preemptive Dial-a-Ride problem which achieves a guarantee of $\tilde{O}(min{\sqrt{n},\sqrt{k}})$. When the capacity $k$ is large, this is an improvement over the previous best approximation ratio of $\tilde{O}(\sqrt{k})$ due to Charikar & Raghavachari ‘98. We also show that there is always a tour that preempts each object at most once, and has a cost $O(\log2 n)$ times the optimal (many) preemptive tour.
Joint work with Anupam Gupta, M.T. Hajiaghayi, and R. Ravi.
