Date	Speaker	Title and Abstract
March 29th	Yuriy Zinchenko Department of Mathematics and Statistics University of Calgary	Polytopes and Arrangements: Diameter and Curvature Abstract: We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature, and a continuous analogue of a d-step equivalence result for the diameter of a polytope. Potential extensions of this work will be highlighted. Based in part on joint work with Antoine Deza (McMaster) and Tamas Terlaky (Lehigh).
February 23rd	Roger Yu Department of Mathematics and Statistics Thompson Rivers University	Scheduling Pilot Training Problem Abstract: In this talk, we will report on an Engage Grant Project "Scheduling Pilot Training Problem" conducted with three TRU students. This is joint project with Pelesys Learning System Inc., a Richmond company. The project is to build a system to assist in the scheduling of training/re-certificating for airline pilots. After building multiple mathematical models for this purpose, we created Recurrent Training Model 5, a model that is capable of assigning pilots, instructors, rooms, and time slots to the courses involved in the training. This model has been implemented in the optimization software called AIMMS, and in addition to simply providing a schedule for training also allows data to be imported from a database for ease of data entry and utilizes search heuristic (e.g., tabu) to assist in generating a good schedule, with all its features easily accessible from a user-friendly GUI.
February 9th	Daniel Karapetyan Department of Mathematics Simon Fraser University	Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem Abstract: The Generalized Traveling Salesman Problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once. While the GTSP is a very important combinatorial optimization problem and is well studied in many aspects, the local search algorithms used in the literature are mostly basic adaptations of simple TSP heuristics. Hence, a thorough and deep research of the neighborhoods and local search algorithms specific to the GTSP is required. We formalize the procedure of adaptation of a TSP neighborhood for the GTSP and classify all other existing and some new GTSP neighborhoods. For every neighborhood, we provide efficient exploration algorithms that are often significantly faster than the ones known from the literature. Finally, we compare different local search implementations empirically. This is joint work with Gregory Gutin.
January 26th	Joe Qranfal Department of Mathematics Simon Fraser University	A Fast Computational Algorithm for Segmentation of Noisy Medical Images Abstract: We show here that the implementation a Markov random fields image segmentation algorithm works well for the purpose of denoising and segmenting medical images. One of the main contributions here is the ability for a user to manipulate online the image so as to achieve clear delineation of objects of interest in the image. This is made possible by the efficiency of the implementation. Results are presented for images that are generated by Single Photon Emission Computed Tomography and Magnetic Resonance Imaging. The results show that the method presented is effective at denoising medical images as well as segmenting tissue types, organs, lesions, and other features within medical images. We advocate that this method should be considered as part of the medical imaging toolbox.
January 20th *Friday, 2:30 p.m.* *SUR 3120*	Michael Monagan Department of Mathematics Simon Fraser University	Computing Tutte polynomials Abstract: The Tutte polynomial from graph theory is the most general graph invariant that can be computed by edge deletion and contraction. Because it includes the Chromatic polyomial as a special case, it is NP-hard to compute, and a straight-forward implementation of the edge deletion and contraction algorithm, like the one in Mathematica, takes O( 1.6^(n+m) ) time where n=|V| and m=|E|. In recent work, Haggard, Pearce and Royle studied edge selection heuristics and used the graph normal form in Brendan McKay's "nauty" package to speed up the edge deletion contraction algorithm. They succeeded in computing the Tutte polyomial of the truncated icosahedron graph, a graph with 32 vertices and 90 edges, in one week on 150 computers. [ See here. ] In this talk we will present a new edge selection heuristic which we have implemented in vanilla Maple. It dramatically improves the computation time and surprisingly, computes the Tutte polynomial of some generalized Petersen graphs in polynomial time. We will present also the connection of the Tutte polynomial with the reliability polynomial from network theory which is what motivated us to consider computing Tutte polynomials and we comment about what facilities in Maple aided the implementation. Our examples are presented using Maple's GraphTheory package which a group of students and faculty at SFU developed. No prior knowledge of Tutte polynomials is assumed.
December 6th *1:30 p.m.*	Timothy Yusun Department of Mathematics Simon Fraser University	Dedekind Numbers and Related Sequences M.Sc. thesis defence Abstract: This thesis considers Dedekind numbers, where the nth Dedekind number D(n) is defined as the number of monotone Boolean functions (MBFs) on n variables, and R(n), which counts non-equivalent MBFs. The values of D(n) and R(n) are known for up to n = 8 and n = 6, respectively; in this thesis we propose a strategy to compute R(7) by considering profile vectors of monotone Boolean functions. The profile of an MBF is a vector that encodes the number of minimal terms it has with 1;2; : : : ;n elements. The computation is accomplished by first generating all profile vectors of 7-variable MBFs, and then counting the functions that satisfy each one by building up from scratch and taking disjunctions one by one. As a consequence of this result, we will be able to extend some sequences on the Online Encyclopedia of Integer Sequences, notably R(n) up to n = 7, using only modest computational resources.
December 6th *11:00 a.m.*	Sara Taghipour Department of Mathematics Simon Fraser University	Quadratic Balanced Optimization Problems M.Sc. thesis defence Abstract: We introduce the Quadratic Balanced Optimization Problem (QBOP) and study its complexity. QBOP is NP-hard even for very special cases such as Quadratic Balanced Knapsack Problem (QBKP) and Quadratic Balanced Assignment Problem (QBAP). Several general purpose algorithms are proposed and tested on the special cases of QBKP and QBAP. Polynomial solvable special cases are also identified.
November 24th *12:30 p.m.*	Mehrnoush Malekesmaeili Department of Mathematics Simon Fraser University	On Certificates that a Matrix does not have the Consecutive Ones Property M.Sc. thesis defence Abstract: A binary matrix has the consecutive ones property (C1P) if there exists a permutation of its columns which makes the 1s consecutive in every row. The C1P has many applications which range from computational biology to optimization. We give an overview of the C1P and its connections to other related problems. The main contribution of this thesis is about certificates of non-C1Pness. The notion of incompatibility graph of a binary matrix was introduced in [McConnell, SODA 2004] where it is shown that odd cycles of this graph provide a certificate for a non-C1P matrix. A bound of k+2 was claimed for the smallest odd cycle of a non-C1P matrix with k columns. We show that this result can be obtained directly via Tucker patterns, and that the correct bound is k + 2 when k is even, but k + 3 when k is odd. Furthermore we empirically study the minimal conflicting set certificate on synthetic data.
November 3rd	Piyashat Sripratak Department of Mathematics Simon Fraser University	Facets of the Boolean Quadric Polytope Abstract: In this talk, we introduce a linearization of the unconstrained quadratic zero-one program in n variables. We denote the convex hull of solutions the Boolean quadratic polytope. Based on Manfred Padberg's work; The Boolean Quadric Polytope: some Characteristics, Facets and Relatives, we show all trivial facets and three families of facets of the polytope. There are O(3n) facets in these four types. At the end of the talk, we give some special cases and a generalization that are polynomially solvable or all facets are describable.
October 20th *1:30 p.m.*	Annie Zhang Department of Mathematics Simon Fraser University	Quadratic Bottleneck Problems: Algorithms, Complexity and Related Topics Ph.D. thesis defence Abstract: In this thesis we study the quadratic bottleneck combinatorial optimization problem (QBCOP) which generalizes the well-known class of bottleneck problems. The solvability of QBCOP is linked to that of the linear combinatorial optimization problems with conflict constraints. Various properties and algorithms for these classes of problems are developed and special cases of spanning trees, knapsack type problems, and assignment variations are explored. These problems are shown to be strongly NP-hard even on very special graphs. We then identify polynomially solvable special cases and also develop heuristics algorithms. Experimental results are reported for all the heuristics we developed. As a by-product our work, we have an approximation algorithm for the maximum edge clique partitioning problem, improving the best known performance ratio for the problem.