Thursday, December 1, 3:00PM
NSH 1507
Benoit Hudson
How to mesh when the ground is moving
Traditionally, finite element simulations have assumed the geometry of the domain is fixed — after all, in a weather simulation, the mountains do not move. However, in many problems the geometry does, in fact, change — very notably so in solid deformation problems (bending a steel bar, for instance) and in fluid-solid interaction problems (blood cells flowing through a capillary). Even when the geometry is fixed, it can be helpful to write the equations in a Lagrangian frame of reference, which requires that we allow mesh elements to move and deform over time. I will survey various methods to deal with moving boundaries and moving mesh elements. As a geometer, I will naturally bias towards techniques that leave the mathematics quite simple at the cost of making the geometry difficult. We will see that while the state of the art has progressed to the point of making pretty pictures, the field is still wide open.
Speaker: Virginia Vassilevska
Time: Wednesday 12-1pm
Location: NSH 1507
Title: Models of Greedy Algorithms
Abstract:
In an attempt to define an abstract model that captures what we call greedy algorithms, Borodin et al. define so called priority algorithms, in the context of scheduling problems. Davis and Impagliazzo further apply the framework to graph problems. A lot of approximation lower bounds have been proven in this model. For example, weighted vertex cover cannot be approximated by a better factor than 2 using an algorithm fitting the framework. Furthermore, most greedy algorithms seem to fit the framework - e.g. the greedy weighted vertex cover algorithm.
The goal of the talk is to provide a brief survey on the research done on priority algorithms.
TITLE:Stopping Rules and Time Reversal for Random Walks on Graphs
SPEAKER: Andrew Beveridge
WHEN: December 1, 4-5:30pm
WHERE: PPB 300
ABSTRACT: Consider a directed graph $G$ and a random walk on it. Looking at such a walk in reverse gives a random walk on a related directed graph $\hat{G}$. When $G$ is an undirected graph, we have $G=\hat{G}$. One can use and intelligent stopping rule that “looks where it is going” to halt a random walk so that the distribution of the final state is a desired distribution $\tau$. This leads to a number of exact mixing measures that are related to the classical mixing measures (such as the relaxation time). We discuss the effect of time reversal on stopping rules by considering families of rules from singletons to a specified target distribution. We describe a duality between stopping rules on $G$ and stopping rules on $\hat{G}$. In particular, we give a natural proof that the “average mixing time” of a random walk on $G$ is equal to the time it takes for a random walk on $\hat{G}$ to “forget where it started,” which was originally proved by Lovasz and Winkler via linear programming.
Joint work with Laszlo Lovasz.
