COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2011

Experimentally measured contact traces, such as those obtained in a conference setting by using short range wireless sensors, are usually limited with respect to the practical number of sensors that can be deployed as well as available human volunteers. Moreover, most previous experiments in this field are partial since not everyone participating in the experiment is expected to carry a sensor device. Previously collected contact traces have significantly contributed to development of more realistic human mobility models. This in turn has influenced proposed routing algorithms for Delay Tolerant Networks where human contacts play a vital role in message delivery. By exploiting time-spatial properties of contact graphs as well as popularity and social information of mobile nodes, we propose a novel method to reconstruct the missing parts of contact graphs where only a subset of nodes are able to sense human contacts.

This is joint work with Dr. Valerie King and Dr. Ali Shoja.

Many performance metrics in wireless networks are ultimately nonlinear functions of the distances between transmitters, receivers and interferers. For a given network coverage and a distribution of random users within the network, how to characterize the distances among these users becomes a challenge and a prerequisite to accurate system modeling and analysis. This talk presents some recent results in Geometrical Probability for random distances associated with rhombuses (e.g., sectorized cells with directional antennas) and hexagons (e.g., cellular systems), shows their applications in wireless communication networks, and compares them with some existing, state-of-the-art approximation approaches.

This is joint work with Dr. Jianping Pan, and most of the work above is still our work-in-progress.

A Latin square of order n is a n by n array of n symbols such that each symbol appears exactly once in each row and exactly once in each column. Two Latin squares of order n are orthogonal if when superimposed, each ordered pair of symbols occurs exactly once. One of the big unsolved problems in design theory is to determine if it is possible to find three or more pairwise orthogonal Latin squares of order 10. This talk describes both theoretical and computational attempts at resolving this question. The talk will conclude with some suggestions for promising areas for continued search.

The research presented in this talk was done in collaboration with Russell Campbell, Erin Delisle, Mark Ellingham, Leah Howard, Nikolay Korovaiko, Brendan McKay, Alison Meynert, and Ian Wanless.

We consider the following class of problems. We are given a graph G=(V,E) with per-unit costs c(e) for reserving capacity on edges e. We are also given a polytope P of demand matrices [D_ij] which our network should support. What is the cheapest cost network if we must use an oblivious routing strategy? If P consists of a single matrix - it's trivial (just route on shortest paths). On the other hand, we can show there are P's for which it is hard to estimate the cost up to logarithmic factors. There are several interesting natural choices for P. We show that if P is the class of hose matrices (roughly equals the set of demands induced by matchings), then the optimal solution is induced by a tree (which can be found in polytime). There are some interesting questions that remain open which we also discuss.

This is joint work with Navin Goyal and Neil Olver.

Today's microblogging services such as Twitter have long outgrown their initial designs as SMS-based social networks. Instead, a massive and steadily-growing user population of more than 100 million is using Twitter for everything from capturing the mood of the country to detecting earthquakes and Internet service failures. It is unsurprising that the traditional centralized client-server architecture has not scaled with user demand, leading to server overload and significant loss of availability.

In this work, we argue that the divergence in usage models of microblogging services can best be addressed using complementary mechanisms, one that provides reliable messages between friends, and another that delivers events from popular celebrities and media outlets to their millions of followers. We present Cuckoo, a new microblogging system that offloads processing and bandwidth costs away from a small centralized server base while ensuring reliable message delivery. We use a 20-day Twitter availability measurement to guide our design, and trace-driven emulation of 30,000 Twitter users to evaluate our Cuckoo prototype. Compared to a centralized approach, Cuckoo achieves 30-50% server bandwidth savings and 50-60% CPU load reduction, while guaranteeing reliable message delivery.