Title : Turan problems on the hypercube
Speaker : David Offner
When : 4:30-5:30pm, March 29th
Where : PPB 300
Abstract: Turan’s theorem gives the number of edges possible in an n-vertex graph with no k-clique. Since this result was proved in 1941, numerous generalizatons and variations have been studied. In this talk, we survey some conjectures, problems and results on Turan-type problems where the base graph is a hypercube.
In particular, we define c_d to be the minimum proportion of the edges which must be removed from any hypercube so that it does not contain a d-dimensional subcube as a subgraph, and p_d to be the maximum number of colors with which one can color the edges of any hypercube such that any d-dimensional subcube contains every color. Note c_d < 1/p_d.
We prove the exact value of p_d for every d, and present some observations about c_d.
Includes joint work with Oleg Pikhurko.
Friday, March 30th, 2007
3:30pm
WEH 7220
TITLE:
An O(n log n) algorithm for maximum st-flow in a directed planar graph
Glencora Borradaile
Brown University
ABSTRACT:
We give the first correct O(n log n) algorithm for finding a maximum single-source, single-sink maximum st-flow in a directed planar graph. After a preprocessing step that consists of finding single-source shortest path distances in the dual, the algorithms consists of repeatedly saturating the leftmost residual s-to-t path. While the algorithm is very simple, the analysis is more complicated.
I also will overview other planar graph algorithms that we are working on.
SPEAKER: Adam Wierman
TIME: Wednesday 12-1pm, March 28, 2007
PLACE: NSH 1507
TITLE: Fairness in queues
ABSTRACT:
The growing trend in computer systems towards using scheduling policies that prioritize jobs with small service requirements has resulted in a new focus on the fairness of such policies. In particular, researchers have been interested in whether biasing towards small job sizes results in large jobs being treated “unfairly.” However, unfairness is an amorphous concept and thus difficult to define and study. In this talk, I will present some recent attempts to define and study the concept of fairness in single server queueing settings. Rather than providing the unique, correct definition of fairness for queues, my goal in this talk is to illustrate, compare, and contrast, the range of fairness measures that have been suggested and to summarize what interesting open questions remain for each.
