COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@csc.uvic.ca). To get email notification of our seminars and other events, you can subscribe to the CAG email list at http://mailman.csc.uvic.ca/mailman/listinfo/cag
Date  Place  Time  Speaker  Abbreviated Title 

Fri. Sept 16  ECS 660  2:00pm  Kazem Jahanbakhsh  Predicting Missing Contacts in Mobile Social Networks 
Fri. Sept 30  ECS 660  2:30pm  Yanyan Zhuang  Geometrical Probability and Wireless Networks 
Fri. Oct. 7  ECS 660  2:30pm  Wendy Myrvold  Searching for a Maximum Set of Mutually Orthogonal Latin Squares of Order 10 
Fri. Oct. 14  ECS 660  2:30pm  Bruce Shepherd  The Robust Network Design Problem 
Fri. Oct. 21  ECS 660  11:30am  Xiaoming Fu  Scaling Microblogging Services with Divergent Traffic Demands 
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 timespatial 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, stateoftheart approximation approaches.
This is joint work with Dr. Jianping Pan, and most of the work above is still our workinprogress.
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 perunit 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 SMSbased social networks. Instead, a massive and steadilygrowing 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 clientserver 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 20day Twitter availability measurement to guide our design, and tracedriven emulation of 30,000 Twitter users to evaluate our Cuckoo prototype. Compared to a centralized approach, Cuckoo achieves 3050% server bandwidth savings and 5060% CPU load reduction, while guaranteeing reliable message delivery.