CAG Schedule of Talks: Spring 2012

# COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2012

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

## Schedule for Talks:

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

# A solution to Wilf's sigma tau problem Aaron Williams Department of Mathematics and Statistics, McGill University Friday Feb. 24, 2:30-3:30pm, ECS 660

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 (1931-2012) asked if a stronger result holds: Can S(n) can be sequenced "so that each is obtained from its predecessor" by σ or τ? For example,

321, 231, 312, 123, 213, 132

is a solution for n=3 since successive permutations are obtained by applying τ, σ, σ, τ, and σ, respectively. This solution is cyclic since one more σ takes the last permutation 132 to the first 321.

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 non-cyclic 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.

# Opportunistic Routing in Intermittently Connected Wireless Mobile Social Networks Arian Khosravi Wednesday Feb. 29, 2:30-3:30pm, ECS 660

Short-range communication devices have enabled the large-scale 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 context-aware schemes. However most existing work assumed either independent or identical mobility characteristic across the users population. Observing most human mobility and interaction are interest-driven in the real world, in this research, we evaluate the performance of these schemes with an interest-driven 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 interest-aware routing strategies.

# Lower Bound for Balanced Sets Zhivko Nedev Friday Apr. 27, 2:30-3:30pm, ECS 660

We work with small size balanced subsets of Zp 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) >= log2 (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.

CAG Schedule of Talks: Spring 2012 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised June 5, 2012