- You are here:
- GT Home
- Home
- News & Events

Series: ACO Seminar

We consider the problem of a search engine trying to assign a sequence of search keywords to a set of competing bidders, each with a daily spending limit. The goal is to maximize the revenue generated by these keyword sales, bearing in mind that, as some bidders may eventually exceed their budget, not all keywords should be sold to the highest bidder. We assume that the sequence of keywords (or equivalently, of bids) is revealed on-line. Our concern will be the competitive ratio for this problem versus the off-line optimum.
We extend the current literature on this problem by considering the setting where the keywords arrive in a random order. In this setting we are able to achieve a competitive ratio of 1-\epsilon under some mild, but necessary, assumptions. In contrast, it is already known that when the keywords arrive in an adversarial order, the best competitive ratio is bounded away from 1. Our algorithm is motivated by PAC learning, and proceeds in two parts: a training phase, and an exploitation phase.
Joint work with Tom Hayes, UNM.

Series: Research Horizons Seminar

In this talk, I will present an brief introdution to use partial differential equation (PDE) and variational techniques (including techniques developed in computational fluid dynamics (CFD)) into wavelet transforms and Applications in Image Processing. Two different approaches are used as examples. One is PDE and variational frameworks for image reconstruction. The other one is an adaptive ENO wavelet transform designed by using ideas from Essentially Non-Oscillatory (ENO) schemes for numerical shock capturing.

Wednesday, March 11, 2009 - 11:00 ,
Location: Skiles 255 ,
Dirk Brockmann ,
Northwestern University ,
Organizer:

Human Mobility in our globalised world has reached a complexity and volume of unprecedented degree. More than 60 million people travel billions of kilometres on more than 2 million international flights each week. Hundreds of millions of people commute on a complex web of highways and railroads most of which operate at their maximum capacity. Human mobility is responsible for the geographical spread of emergent human infectious diseases and plays a key role in human mediated bioinvasion, the dominant factor in the global biodiversity crisis. I will report on the recent discovery of scaling laws in global human traffic (obtained from online bill-tracking at www.wheresgeorge.com) and mathematical models that can account for it. I will present a complex network perspective on multi-scale human traffic networks, report on their statistical properties and show that they can be used to identify geographically coherent communities that only vaguely resemble administrative ones. The approach provides an operational segmentation of maps into a hierarchical set of effective regions and boundaries based on human behavior. I will briefly talk about European transportation networks, geocaching and trackable items.

Series: Combinatorics Seminar

Tolerance graphs were introduced in 1982 by Golumbic and Monma as a generalization of the class of interval graphs. A graph G= (V, E) is an interval graph if each vertex v \in V can be assigned a real interval I_v so that xy \in E(G) iff I_x \cap I_y \neq \emptyset. Interval graphs are important both because they arise in a variety of applications and also because some well-known recognition problems that are NP-complete for general graphs can be solved in polynomial time when restricted to the class of interval graphs. In certain applications it can be useful to allow a representation of a graph using real intervals in which there can be some overlap between the intervals assigned to non-adjacent vertices. This motivates the following definition: a graph G= (V, E) is a tolerance graph if each vertex v \in V can be assigned a real interval I_v and a positive tolerance t_v \in {\bf R} so that xy \in E(G) iff |I_x \cap I_y| \ge \min\{t_x,t_y\}. These topics can also be studied from the perspective of ordered sets, giving rise to the classes of Interval Orders and Tolerance Orders. In this talk we give an overview of work done in tolerance graphs and orders . We use hierarchy diagrams and geometric arguments as unifying themes.

Series: PDE Seminar

We consider the the following fourth order degenerate parabolic equation h_t + (hh_xxx)_x = 0. The equation arises in the lubrication approximation regime, describing the spreading of a thin film liquid with height profile h >= 0 on a plate. We consider the equation as free boundary problem, defined on its positivity set. We address existence and regularity of classical solutions in weighted Hölder and Sobolev spaces.

Series: CDSNS Colloquium

The Cohen-Gallavotti Fluctuation theorem is a result describing the behaviour of simple hyperbolic dynamical systems. It was introduced to illustrate, in a somewhat simpler context, anomalies in the second law of thermodynamics. I will describe the mathematical formulation of this Fluctuation Theorem, and some variations on it.

Monday, March 9, 2009 - 13:05 ,
Location: Skiles 255 ,
Zhi J. Wang ,
Aerospace Engineering, Iowa State University ,
Organizer: Yingjie Liu

The current breakthrough in computational fluid dynamics (CFD) is the emergence of unstructured grid based high-order (order > 2) methods. The leader is arguably the discontinuous Galerkin method, amongst several other methods including the multi-domain spectral, spectral volume (SV), and spectral difference (SD) methods. All these methods possess the following properties: k-exactness on arbitrary grids, and compactness, which is especially important for parallel computing. In this talk, recent progresses in the DG, SV, SD and a unified formulation called lifting collocation penalty will be presented. Numerical simulations with the SV and the SD methods will be presented. The talk will conclude with several remaining challenges in the research on high-order methods.

Series: Geometry Topology Seminar

Given any contact 3-manifold, Etnyre and Ozbagci defined new invariants of the contact structures in terms of open book decompositions supporting the contact structure. One of the invariants is the support genus of the contact structure which is defined as the minimal genus of a page of an open book that supports the contact structure. In a similar fashion, we define the support genus sg(L) of a Legendrian knot L in a contact manifold M as the minimal genus of a page of an open book of M supporting the contact structure such that L sits on a page and the framing given by the contact structure and by the page agree. In this talk, we will discuss the support genus of Legendrian knots in contact 3-manifolds. We will show any null-homologous loose knot has support genus zero. To prove this, we observe an interesting topological property of knots and links on the way. We observe any topological knot or link in a 3-manifold sits on a planar page (genus zero page) of an open book decomposition.

Series: Probability Working Seminar

The talk is based on the paper titled "Anosov diffeomorphisms and coupling" by Bressaud and Liverani. Existence and uniqueness of SRB invariant measure for the dynamics is established via a coupling of initial conditions introduced to dynamics by L.-S. Young.

Series: Combinatorics Seminar

This is joint work with Alex Postnikov. Imagine that you are to build a system of space stations (graph vertices), which communicate via laser beams (edges). The edge directions were already chosen, but you must place the stations so that none of the beams miss their targets. In this talk, we let the edge directions be generic and independent, a choice that constrains vertex placement the most. For K_{3} in \mathbb{R}^{2}, the edges specify a unique triangle, but its size is arbitrary --- D_{2}(K_{3})=1 degree of freedom; we say that K_{3} is rigid in \mathbb{R}^{2}. We call D_{n}(G) the degree of parallel rigidity of the graph for generic edge directions. We found an elegant combinatorial characterization of D_{n}(G) --- it is equal to the minimal number of edges in the intersection of n spanning trees of G. In this talk, I will give a linear-algebraic proof of this result, and of some other properties of D_{n}(G). The notion of parallel graph rigidity was previously studied by Whiteley and Develin-Martin-Reiner. The papers worked with the generic parallel rigidity matroid; I will briefly compare our results in terms of D_{n}(G) with the previous work.