CSI5165 - Project Talks - Nov 30,2005 - CBY A605 - 11:30-2:30 ============================================================= 11:30-11:50 Dominique Roy "Projective plane of order 10: part of its non-existence proof" 12:00-12:20 Benjamin Feng "Meeting Probability of Buffer Overflow Requirement: A Heuristic Search base Approach" 12:25-12:45 Shai Mor "Generating langford sequences by backtracking and hillclimbing" ----------------------------------------------------------------- 12:50-1:00 Break ----------------------------------------------------------------- 1:00-1:20 Joe Burpee "Constructing Covering Arrays using Tabu Search" 1:25-1:45 Sadrul Chowdhury "Solving the Embedding Covering Array Problem via Greedy Method" 1:50-2:10 Jason Lobb "A Mixed Radix Gray Code with Constant Sum" ----------------------------------------------------------------- ABSTRACTS: -------------- Benjamin Feng, "Meeting Probability of Buffer Overflow Requirement A Heuristic Search base Approach" Abstract: Data loss in a network causes performance degradation. Since data loss usually is due to buffer overflow in the network nodes, it is desirable to keep the probability of buffer overflow at a certain level. The easiest implementation is to use traffic shaping to control the amount of traffic entering the network. Most traffic shaping approach uses the leaky bucket approach, in which the mean rates of the ingress traffic streams are reduced. It is hard to determine which traffic source's mean rate should be reduced and equally hard to determine how much mean rate should be reduced using analytical approaches in a large complex network. Building a simulated network does help, but it may be very time consuming in many cases. My research has developed an approach called FISTE, which can predict the probability of buffer overflow given the amount of reductions in each traffic source. However, since the goal is to find the reductions which it will meet the overflow requirement, there are a lot of combinations of the reductions to try, since each reduction is a positive real number. Simulation Annealing and Tabu search approach is used to find a near optimal solution for this problem. -------------- Shai Mor,"Generating langford sequences by backtracking and hillclimbing" There are many Langford sequences already at not so high orders. Since there is no closed formula for the exact number of a given order we can use statistical methods to approximate their number with a fairly random sampling set. To get the exact number requires to generate all such sequences. This is a task the becomes unfeasible alrady for not-too-high orders. A sequences is merely a linear representation of a partition of a position set into disjoint pairs of unique differences. To generate these by backtracking we assign each differences to a pair of positions. if no such assignment possibility exists we backtrack to try other previous assignment possibilities that where postpone for later. we generate by trying all assignment possibilities in a deterministic and fix order process. To generate these by hillclimbing we use a non decreasing function, number of differences sucessfully assigned so far, to iteratively buildup on any partial solution only we get a complete seqeunce. we buildup is done by a uniformly random process of choosing a difference and an assignment. this process is not determonistic and the order by which sequences are generated is irregular and unpredictable. The number of such (Skolem)sequences are known till order 23, and is already at the thousand of billions. see http://www.lclark.edu/~miller/langford.html for current enumeration results. By generating a large enough random sample of these sequences (and sometimes, for some of them, their duplicates) we can give a statistical approximation to their number. ---------------- Joe Burpee, "Constructing Covering Arrays using Tabu Search" A covering array CA(N,k,g) is a kxN array A of symbols from the alphabet G={0,1,...,g-1} such that for any pair of rows i,j and any pair of numbers x,y in G, there exists at least one column c such that a[i,c]=x and a[j,c]=y. We want to search for covering arrays with as small N as possible. Typically, greedy strategies vary N until a covering is achieved (with N unlikely to be minimized), while tabu search involves choosing a reasonably small fixed N and attempting (not necessarily successfully) to construct a covering array by changing a pair in one column at a time. The objective here is to combine aspects of these two strategies to construct some covering arrays of smaller size than those previously recorded. A key issue is the specification of an appropriate objective function incorporating the two criteria to be minimized: N and the number of uncovered pairs. ---------------- Sadrul Chowdhury, "Solving the Embedding Covering Array Problem via Greedy Method" A covering array of size N, degree k, order v and strength t is a k x N array CAx(N; t, k, v) with entries from a set of v symbols such that in any t x N subarray every t x 1 column occurs at least x times. One of the natural generalizations of the covering array problem discussed by Hartmen et al. is the problem of Embedding covering arrays. The problem is to construct a covering array of smallest size from a given partial array. A Greedy algorithm as explained by Colbourn et al., which keps adding a single test to the given set of tests until all the tuples are covered, will be used to solve this embeded covering array problem. ---------------- Jason Lobb, A Mixed Radix Gray Code with Constant Sum A mixed radix Gray Code is a Gray code on $n$-tuple $(x_1, x_2, \cdots ,x_t)$with each position having its own alphabet. Let $C(k:n_1,n_2,\cdots,n_t)$ be the n-tuples such that the sum of the $n_i$'s is k. Using an existing mixed radix reflected Gray code ordering, the $n$-tuples of $C(k:n_1,n_2,\cdots,n_t)$ will be found. This order of these $n$-tuples is also minimal change ordering of $C(k:n_1,n_2,\cdots,n_t)$, in that successive elements differ in only two positions and these positions differ in value from the successor by 1. ----------------