The following is the schedule of upcoming department seminars. Seminars will be added to the schedule throughout the year. All seminars are free of charge and are open to all members, affiliates, and colleagues of the university community. Seminars are typically held on Tuesday or Thursday at 1:00 pm. If you would like additional information or if you might be interested in presenting a seminar, please contact Helen Cameron or the Department of Computer Science.
Departmental Seminar - Leszek GasieniecWhen: January 24, 2017 @ 1:00pm
Where: EITC E2-160
Speaker: Leszek Gasieniec, University of Liverpool
Title: Bamboo Garden Trimming Problem (Perpetual maintenance of machines with different attendance urgency factors)
A garden G is populated by n > 1 bamboos b_1, b_2, ..., b_n with the respective daily growth rates h_1, h_2, ... h_n. It is assumed that the initial heights of bamboos are zero. The robotic gardener or simply a robot maintaining the bamboo garden is attending bamboos and trimming them to height zero according to some schedule.
The Bamboo Garden Trimming Problem, or simply BGT, is to design a perpetual schedule of cuts to maintain the elevation of bamboo garden as low as possible. The bamboo garden is a metaphor for a collection of machines which have to be serviced with different frequencies, by a robot which can service only one machine during a visit. The objective is to design a perpetual schedule of servicing the machines which minimizes the maximum (weighted) waiting time for servicing. We consider two variants of BGT.
In discrete BGT the robot is allowed to trim only one bamboo at the end of each day. In continuous BGT the bamboos can be cut at any time, however, the robot needs time to move from one bamboo to the next one and this time is defined by a weighted network of connections.
For discrete BGT, we show a simple 4-approximation algorithm and, by exploiting relationship between BGT and the classical Pinwheel Scheduling Problem, we obtain also a 2-approximation and even a closer approximation for more balanced growth rates. For continuous BGT, we propose approximation
algorithms which achieve approximation ratios O(log(h_1/h_n)) and O(log n).
This is a joint work with R. Klasing, Ch. Levcopoulos, A. Lingas, J. Min, and T. Radzik.
Departmental seminar - Charles LoewenWhen: January 26, 2017 @ 1:30pm
Where: EITC E2-320
Speaker: Charles (Chuck) Loewen, Chairman, President and CEO, Founder of Online Business Systems, a leading business and IT consulting firm.
Abstract:Charles (Chuck) Loewen, is Chairman, President and CEO, Founder of Online Business Systems, a leading business and IT consulting firm. It was named one of Canada’s best places to work for 10 consecutive years and one of the best workplaces for women for 5 consecutive years. Mr. Loewen is the recipient of the 2017 Exceptional Achievement in Computer Science award of the University of Manitoba Faculty of Science.Mr. Loewen will talk about his path to success and the company that he founded. He will also give some advice to the students who want to be successful in the IT business or become entrepreneurs. The talk will be followed by a Q&A session, so please bring your questions!
Departmental seminar - Ji Hyun KoWhen: March 02, 2017 @ 1:00pm