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. Feb. 24  ECS 660  2:30pm  Aaron Williams  A solution to Wilf's sigma tau problem 
Wed. Feb. 29  ECS 660  2:30pm  Arian Khosravi  Opportunistic Routing in Intermittently Connected Wireless Mobile Social Networks 
Fri. Apr. 27  ECS 660  2:30pm  Zhivko Nedev  Lower Bound for Balanced Sets 
The symmetric group S(n) can be generated by two simple operations:
A rotation σ = (1 2 ... n), and a swap τ = (1 2).
In 1975, Herb Wilf (19312012) asked if a stronger result holds:
Can S(n) can be sequenced "so that each is obtained from its predecessor"
by σ or τ? For example,
Don Knuth rates Wilf's problem as the second most difficult open problem in his new volume of The Art of Computer Programming, and states that solutions may not be of practical value due to their complexity. In this talk we solve the sigma tau problem by constructing a cyclic solution when n is odd, and a noncyclic solution when n is even. (This is best possible, since a campanological result by Rankin and Swan proves there are no cyclic solutions when n is even.) The construction leads to a simple algorithm that creates each successive permutation in O(1) amortized time.
Shortrange communication devices have enabled the largescale dissemination of information through user mobility and contact, without the assistance of communication infrastructures. However, the intermittent connectivity, makes it challenging to determine when and how to forward a message possibly through a series of third parties to deliver it to the destination. This problem has attracted a lot of attention in the literature lately, with proposals ranging from oblivious epidemic to contextaware schemes. However most existing work assumed either independent or identical mobility characteristic across the users population. Observing most human mobility and interaction are interestdriven in the real world, in this research, we evaluate the performance of these schemes with an interestdriven mobility model. We further propose to take the user interest into account when determining routing strategies to further improve the performance of these schemes for mobile social networks. Simulation results have demonstrated the efficacy of the interestaware routing strategies.
We work with small size balanced subsets of Z_{p} when p is prime. In a balanced set S, each element x in S is a midpoint between two other elements from S, i.e. 2x=y+z (mod p), y, z in S\{x}. Denote the minimum cardinality of a balanced set modulo p by α(p). We prove a new lower bound for α(p): for every prime p > 2, α(p) >= log_{2} (p) + 1.41. Small balanced sets are needed in strategies for the family of combinatorial games analyzed in several papers by Z. Nedev and A. Quas.