Events

Approximation algorithms for min-cost (S,T) connectivity

Abstract:

One of the well-known problems in network design is to find a minimum-cost strongly-connected spanning subgraph of a directed network.

Date: September 22 - 23, 2010
Time: 4:00 - 5:00 PM
Location: Davis Centre (DC) 1304

Speaker: Dr. Vijay Vazirani, College of Computing, Georgia Tech

The Invisible Hand of the Market: Algorithmic Ratification and the Digital Economy

Abstract:

It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard for their own interest.

State Transfer on Graphs

Abstract:

If A is the adjacency matrix of a graph X, then the matrix

Graph Sparsifiers

Abstract:

Can a dense graph be approximated by a sparse graph? Surprisingly, yes. A "sparsifier" of a graph is a weighted subgraph that approximates the weight of every cut, up to a factor (1+eps).

Growth Rates in Minor-Closed Classes of Matroids

Abstract:

A result of Mader states that in a proper minor-closed class of graphs, the number of edges of a graph in the class is at most linear in its number of vertices - this result gives the first glimpse of a rich structural theory of minor-closed

The combinatorics of solving linear equations

Abstract:

A major branch of modern combinatorics, usually called Ramsey theory, studies properties of structures which are preserved under partitions.

The Index function and the space complexity of Dyck languages

Abstract:

Streaming algorithms access the input sequentially, one symbol at a time, a small number of times, while attempting to solve some information processing task.

From 3-colorings to 3-flows

Abstract:

Every loopless planar graph that is triangle-free has a vertex 3-colouring. This is Grötzsch's Theorem, put forward in 1958.

Entanglement assisted zero error coding