The course materials are available on moodle to registered students.
There is no textbook for this course. Readings from academic articles will be available on the moodle page of the course. A list of classical papers in facility location is available from Trevor Hale’s bibliography.
The course is available on Moodle.
Title: Parameterized Query Complexity of Quantum Computation
Speaker: Parijat Purohit, MSc candidate, Optimization Research Group
Abstract: Our proposal is to analyze the query complexity of a problem as a function of some parameter. This extends the parameterized complexity studies in the classical setting. We illustrate the applicability of this methodology on two seemingly unrelated problems. We parameterize the degree of imbalance for an arbitrary function whether it is balanced or not. We consider the same parameterization for the self-duality of a function.
Joint work with Saurya Das (Physics), Daya Gaur, Shahadat Hossain, and Robert Benkoczi.
Work accepted for presentation as a poster at the 20th Annual Conference on Quantum Information Processing, Seattle, WA.
Title: Algorithms for Barrier Coverage with Wireless Sensors
Speaker: Dr. Xiao Zhang, City University of Hong-Kong
Abstract: Barrier coverage is a critical problem in wireless sensor networks. In the area, we study the barrier coverage problem from two perspectives, i.e., static sensors with adjustable sensing ranges and mobile sensors with fixed sensing ranges. Specifically, in the first topic, we consider the barrier coverage problem for a line interval, in which we are given a set of sensors and the goal is to determine a range assignment with the lowest possible cost. In the second topic, we consider the problem of covering a line interval by mobile sensors such that the maximum of moving cost is minimized.
Bio: Xiao Zhang received his PhD degree from Department of Computer Science in City University of Hong Kong, Hong Kong, 2016. He was a visiting scholar with the Department of Computer Science in Utah State University, Logan, Utah, USA, in 2015. His research interests include algorithms design and analysis, wireless sensor networks.
Topics: Fourier transforms, the sampling theorem, Shannon formula for the capacity of a communication channel.
Lectures for the week: Sep 13-15.
Topic: an introduction to classes.
Text: Chapter 7 in Skansholm.
Notes available here (updated Sept 18).
Source code including homework available at cloud9 or as a zip file (updated Sept 18).
Title: Local Search Algorithms for Data Placement Problem
Speaker: Anamay Sarkar, NIT Rourkela, MITACS Globalink Fellow in the Optimization Research Group
Abstract: I will talk about Local Search based Approximation Algorithms for the data placement problem. One of the local search operators is based on the assignment problem and the second one is based on the operators for the Un-capacitated facility location problem. I will report some experimental results on the data set obtained from the OR library. This work was done as part of Mitacs Globalink internship.
Bio: Anamay Sarkar is pursuing B. Tech in Computer Science and Engineering and is currently in his final year at NIT Rourkela. His past internship was at “IIT Delhi” in the area of Approximation Algorithms under Prof Naveen Garg. He is currently the branch topper after 3rd year.
Title: A Comparison of Rotation Parameterisations for Bundle Adjustment.
Speaker: Nurgul Aimati, MSc candidate, UofL Optimization Research Group.
Time & Location: Wednesday, March 23, 2016 in room D633
Bundle Adjustment is an iterative process where 3D information is estimated from 2D image measurements. Typically, the position of object points are estimated simultaneously with the position and orientation of the cameras. While the object points and camera positions have a straightforward “natural” parameterisation, several possibilities exist for the rotation. In this thesis, seven parameterisation of the rotation were investigated; Euler angles (two variants), the Rodriguez representation, the axis-and-angle representation, unit quaternions, and two variants of the direction cosine matrix (DCM).
Title: Cellular Automaton Based Algorithms in Wireless Communication
Speaker: Dr. Salimur Choudhury, Mathematics and Computer Science, Algoma University, Sault Ste. Marie, ON
Location and time: 1 pm, Room B756
Abstract: The cellular automaton is a bioinspired model used to model different physical systems including wireless communication. One of the main advantages of using cellular automaton based algorithms is that they need very little local information to compute a solution. In this talk, several optimization problems in wireless sensor networks and RFID (radio frequency identification) networks along with the corresponding cellular automaton based algorithms will be presented. The problems include sleep-awake scheduling of sensors, mobile sensors dispersion, and elimination of redundant readers in RFID system.
Bio: Dr. Salimur Choudhury is an assistant professor in the department of Mathematics and Computer Science at Algoma University, Sault Ste. Marie, ON. He is also an adjunct assistant professor in the school of computing at Queen’s University, Kingston, ON. His research interests include designing algorithms for wireless communication systems including sensor networks, RFID networks, device to device communication systems, etc. Dr. Choudhury completed PhD from School of Computing, Queen’s University in 2012 and Masters from the Department of Mathematics and Computer Science, University of Lethbridge in 2008. He has experience teaching at several other universities in USA and Bangladesh. He also worked at IBM Canada Software Lab in Markham, ON.
Title: Approximation Algorithms for Cumulative VRP with Stochastic Demands
Speaker: Rishi Ranjan Singh, Department of Information Technology, Indian Institute of Information Technology Allahabad (IIT – Allahabad), India.
Location and time: B716, Friday Feb 12, 9 am
Abstract: In this talk we describe randomized approximation algorithms for metric stochastic cumulative VRP for split and unsplit deliveries. The approximation ratios are \(2(1 + \alpha)\) and 7 respectively, where \(\alpha\) is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees and paths. We use and extend the results in [Technical note - approximation algorithms for VRP with stochastic demands. Operations Research, 2012] and [Routing vehicles to minimize fuel consumption. Operations Research Letters, 2013].
This work, to appear in the proceedings of CALDAM 2016, is jointly with D.R. Gaur and A. Mudgal.
Bio: Mr. Singh is a Visiting Faculty in the Department of Information Technology at IIIT Allahabd, India. He submitted his PhD in the Department of Computer Science and Engineering at IIT Ropar, India in 2015. He received his B. Tech (Hons.) in Computer Science and Engineering from UPTU Lucknow, India in 2011. He is interested in approximation algorithms for vehicle routing problems, social and complex network analysis, discrete optimization.