Author Archives: benkoczi

Optimization Seminar Series – Fri Feb 12 at 9 am

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.

CPSC 4625: Design and analysis of advanced algorithms

Course outline.

Optimization Seminar Series – Wed Dec 9 at 12:30

Title: Evolutionary Algorithmic Deployment of Radio Beacons for Indoor Positioning
Speaker: Dr. Peter Chen, Memorial University of Newfoundland by video-conference.
Location and time: B716, Wednesday Dec 9, 12:30pm – 13:30pm.

In mobile computing, the location awareness of a mobile device or its user enables numerous personalized and social services such as recommendation of products and sharing current locations on social networks. Extending positioning services to indoor environments augments the value of the mobile communication market vastly. Due to serious signal attenuation, navigation satellite are incapable, and a common approach is to use or deploy small-scale radio frequency transmitters. When deploying these radio beacons, it is crucial to use a small number of them to provide high-quality positioning service. As this turns out a difficult optimization problem, the system administrators would benefit from have a spectrum of solutions with different tradeoffs between cost and quality. This talk provides an Evolutionary Algorithm (EA) framework to fulfill this need. Using a cost-quality adjustment parameter, he EA framework is able to provide a set of solution options to meet varying requirements balancing cost and quality. This property is resulted by the parallel population-based search of EAs, and can be very useful in real-world engineering applications.

Bio: Yuanzhu Chen is an Associate Professor in the Department of Computer Science, Memorial University of Newfoundland, St. John’s, Newfoundland. He received his Ph.D. from Simon Fraser University in 2004 and B.Sc. from Peking University in 1999, both in Computer Science. He was a Visiting Professor to Dartmouth College in 2011-2012. Between 2004 and 2005, he was a post-doctoral researcher at Simon Fraser University. His research interests include wireless networking, mobile computing, optimization of graph problems, and information retrieval.

Optimization Seminar Series – Wed Oct 28 noon

Title: The Robust Weighted Vertex Coloring Problem with Uncertain Data
Speaker: Ram Dahal, PhD candidate, Optimization Research Group
Location and time: B543, Wednesday Oct 28, 12:00pm – 12:50pm.

The vertex coloring problem (VCP) is a classical problem of assigning a color to each vertex of a graph such that no two adjacent vertices have the same color. In the weighted version of classical VCP, the vertices of the graph are assigned a positive weight and the objective is to minimize the sum of the costs of the colors from a feasible coloring. The cost of a color equals the maximum vertex weight among all vertices assigned to the color. WVCP is strongly NP-hard since it generalize the classical VCP. WVCP has several applications in scheduling, timetabling, register allocation, train platforming. In addition, the problem captures the essence of scheduling data transmissions in a time division multiple access (TDMA) wireless network. In our work we consider a much more difficult setting for WVCP called robust WVCP (RWVCP). In the robust problem, the vertex weights are uncertain and only known to lie between given lower and upper bounds. Any particular assignment of values to the uncertain parameters in the allowed ranges is called a scenario. The goal is to find a solution robust to the uncertainty that is, a solution X for which the difference between the cost of X under the worst possible scenario and the cost of the optimal solution for that scenario is minimized. RWVCP is completely open at present. In this talk, we investigate the strength of linear and integer programming techniques in solving robust WVCP. In our apporach, we use Benders decomposition to generate the scenarios of interest but our master problem is a linear program with an exponential number of variables
and it is solved by column generation.

Optimization Seminar Series – Wed Sep 30 @ 1 pm

Title: Design Structure Matrix : Models, Applications and Data Exchange Format
Speaker: Rumana Quashem, MSc candidate, Optimization Research Group
Location and time: B660, Wednesday Sept 30, 1 pm

Abstract: A Design Structure Matrix(DSM) is much more than an adjacency matrix representation of a network. The design and analysis of complex engineered systems can be greatly aided by tools that can capture, organize and represent interactions among systems’ elements. It is a tool that can be used to represent a system’s design structure in a visually appealing manner. The DSM research over the last 3 decades have produced important analysis techniques that have been applied to a variety of projects. Many real world examples of DSM matrices remain scattered in the literature. Recently, the book by Eppinger and Browning has compiled 44 DSM examples from diverse areas; and we have discovered that most of these examples are not in easily retrievable digital form.
Thus, we proposed a new exchange format “Design Structure Matrix Data Exchange(DSMDE)” as a common file format to promote reliable and efficient exchange of Design Structure Model (DSM) and MDM (Multi-domain Model) data. It is an extension of the widely used “Matrix Market(MM)” file format (for the exchange of sparse and dense matrices data). At present there does not exist a common standard for sharing DSM/MDM data. We believe that a standardized exchange format will greatly facilitate research and development of DSM modelling techniques by making data widely available than currently possible. Thus, the DSMDE is expected to be a standard way to share DSM/MDM data among researchers, practitioners, and on different computing environments. 

Everyone is welcome. Graduate students are encouraged to attend.

Optimization Seminar Series – Mon Sep 28 @ 1 pm

Title: Ranking Components of Scientific Software using Spectral Methods
Speaker: Soma Khan, MSc candidate, Optimization Research Group.
Location and time: D630, Monday Sept 28, 1 pm.

Abstract: Our main objective is to determine the importance or centrality of the components of a scientific software which will be helpful in understanding the design architecture of the scientific software. We explore the centrality rankings of functions in call graphs of scientific software using spectral methods. We employ a set of quantitative measures to identify important design elements in scientific software by analyzing the interactions between them. The notion of centrality of software components extended beyond nodal degree. Hub and authority scores are computed using the HITS algorithm and Benzi’s method. The results will be compared to see the accuracy.
Everyone is welcome. Graduate students are encouraged to attend.

Optimization Seminar Series – Wed Sep 16 @ noon in B543

Title: Combinatorial Optimizations of Some Graph  Problems using Evolutionary Algorithms
Speaker: Dr. Mozammel H. A. Khan, Visiting Researcher
Location & time: B543, Wed. Sept. 16, 2015, 12:00pm – 12:50pm

Many classical graph problems such as maximum clique problem (MCP), graph coloring problem (GCP), and degree-constrained minimum spanning tree (d-MST) are NP-hard problems and combinatorial in nature. Meta-heuristic algorithms such as evolutionary algorithms (EA) are found to be very effective in global optimization of combinatorial problems in general. We have solved MCP using quantum-inspired evolutionary algorithm (QEA), GCP using both memetic algorithm and QEA, and d-MST using QEA. In all the cases, the experimental results establish that our methods outperform the previous methods.
The talk is based on the published papers of Professor Khan with his students. The talk is intended for senior undergraduate students, graduate students, and faculty members interested in collaborating in solving combinatorial graph problems and other combinatorial problems using EA.

Dr. Khan is a Professor in the Department of Computer Science and Engineering at East West University, Dhaka, Bangladesh and currently a Visiting Researcher in the Department of Mathematics and Computer Science at University of Lethbridge, AB, Canada. Prof. Khan is a Senior Member of the Institution of Electrical and Electronics Engineers (IEEE). He has obtained B. Sc. Engg. degree in Electrical and Electronic Engineering, M. Sc. Engg. degree in Computer Engineering, and Ph. D. degree in Computer Science and Engineering form  Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh in 1984, 1986, and 1998, respectively. He has served as Head of the Department of Computer Science and Engineering, Head of the Department of Electronics and Communications Engineering, and Dean of the School of Science, Engineering and Technology at Khulna University, Khulna, Bangladesh. He has also served as Chairperson of the Department of Computer Science and Engineering, Chairperson of the Department of Electrical and Electronic Engineering, and Dean of the Faculty of Science and Engineering at East West University, Dhaka, Bangladesh. Prof. Khan’s research interests include Logic Synthesis, Quantum Computing, Evolutionary Algorithms, and Nano-Electronics. He has published 88 papers in journals, book chapters, and conferences. More about him can be found at

CPSC 3780: Data Communications and Networking

The course materials are available on moodle to registered students.
Course outline

  • Main text: Computer Networking, Principles, Protocols and Practice 2nd Ed, by Bonaventure, available online here.
  • Supplementary texts: Computer Networks 5th Ed, by Tanenbaum and Wetherall; Computer Networking: A Top-Down Approach (7th Edition) by Kurose and Ross.

Optimization Seminar Series – Fri. Sept. 11, 2015 in B543

Title: Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line
(extended version of Mark’s upcoming talk at ALGOSENSORS in Patras, Greece)
Speaker: Mark Thom, PhD student, Optimization Research Group
Location & time: B543, Fri. Sept. 11, 2015, 12:00pm – 12:50pm

Abstract: Barrier coverage is a cost effective approach to intruder detection
applications. It consists of monitoring the perimeter, or barrier, of
an area by placing sensors at appropriate locations on the barrier. In
this talk, we consider a restricted version of the barrier coverage
problem in which the area of coverage is a line segment and the
sensors are points with varying detection ranges that lie in initial
positions disjoint to the line segment. Sensors are moved along the
line containing the line segment to their final positions in the
coverage, and the distances moved by each sensor are summed,
determining the cost of the coverage. The objective is to find the
coverage of least cost.  We sketch a proof of the NP-hardness of the
restricted problem and outline a polynomial-time approximation scheme
that produces barrier coverages of cost arbitrarily close to that of
an optimal solution. Everyone is welcome, no prior knowledge of
approximation algorithms or NP-hardness is assumed.

CPSC 1820: Discrete Structures

The course materials are available on moodle to registered students.
Discrete Mathematics and Its Applications – 7th Ed, by Rosen (older
editions OK).
Book of Proof – 2nd Ed, by Hammack, available at http://www.
(CC Licence).

An older offering of the course is accessible