Author Archives: benkoczi

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 – 8th Ed, by Rosen (older
editions OK).
Book of Proof – 2nd Ed, by Hammack, available at http://www.
(CC Licence).
Course outline.

An older offering of the course is accessible

Optimization Seminar Series – Feb 18, 2015 (Cancelled)

Due to an emergency, the following talk has been cancelled.
Title: Multi-Hop Wireless Networking: Issues and Opportunities
Speaker: Dr. Yuanzhu Chen, Associate Professor, Department of Computer Science, Memorial University.
A multi-hop wireless network is a wireless communication network, where nodes that are not within direct transmission range of each other will require other nodes to forward data. It can operate without existing infrastructure, supports mobile users, and sometimes take the form of mobile ad hoc networks, wireless sensor networks, delay-tolerant networks, and so forth. Such a networking paradigm originated from the needs in battlefield communications, emergence operations, search and rescue, and disaster relief operations. Later, it found civilian applications such as community networks. Compared to the TCP/IP based Internet, such a networking paradigm has a number of salient features, such as broadcast medium, fast network topology change, and frequent and extended disruption. In this talk, I will present some of our research projects to address the issues inherent to this networking technology in an effort to advance the state of the art of the area.
Yuanzhu Chen is an Associate Professor and Deputy Head of Undergraduate Studies 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 – Feb 17, 2015 (Cancelled)

Due to an emergency, the following talk has been cancelled.
Title: Robustness and Evolvability in Evolutionary Computation
Speaker: Dr. Ting Hu, Assistant Professor, Department of Computer Science, Memorial University.
Robustness, the maintenance of a phenotypic character in the presence of genotypic changes, is the result of a redundant mapping between genotype and phenotype, where many mutational variants of a genotype produce an identical phenotype. Such robustness, at first glance, seems to hinder the capability of innovating, i.e. evolvability. However, empirical evidences have been reported on living organisms that robustness can facilitate evolvability since it allows genetic variants to expand in neutral spaces that provide a staging ground for future adaptive innovations. Redundant genotype to phenotype mapping is common in Evolutionary Computation. We use genotype networks to characterize the mutational connectivity of an Evolutionary Computation system, and to further quantify robustness and evolvability at the genotype, phenotype, and fitness levels. We show that robustness and evolvability correlate very differently at these three levels, and their interplay crucially depends on how the mutational connections are distributed among phenotypes.
Dr. Ting Hu is an Assistant Professor at the Department of Computer Science, Memorial University of Newfoundland. She was a postdoctoral researcher at Computational Genetics Laboratory, Dartmouth College. She obtained her PhD in Computer Science from Memorial University, MSc in Computer Science and BSc in Applied Mathematics from Wuhan University. Dr. Hu’s research interests include bio-inspired computing and bioinformatics.

Optimization Seminar Series – Wednesday Jan 28, 9 am D511

Title: Cumulative Vehicle Routing Problem: A Column Generation Approach
Speaker: Rishi Ranjan Singh, Department of Computer Sc. and Engg., Indian Institute of Technology Ropar (IIT – Ropar), India.
Time & location: Wednesday Jan 28, 2015, 9 am in D511. This talk is presented by video conference.

In this talk, aimed at senior undergraduate and graduate students, we describe a computational approach for constructing approximate solutions to cumulative vehicle routing problems based on rounding solutions to a linear program. The linear program is based on the set cover formulation, and is solved using column generation. The pricing sub-problem is solved using dynamic programming. Simulation results show that the simple scalable strategy computes solutions with cost close to the lower bound given by the linear programming relaxation. We also give theoretical bounds on the integrality gap of the set cover formulation. This work, to appear in the proceedings of CALDAM 2015, is jointly with D. Gaur.

Bio: Mr. Singh is a PhD Scholar in the Department of Computer Science and Engineering at IIT Ropar. 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, network analysis and operations research.

CPSC 2620: Fundamentals of programming II

All course resources are available on moodle to registered students.
Open Data Structures by Pat Morin.
C++ Primer, 5th Ed, Lippman, Lajoie, Moo.
Course outline

Optimization SeminarSeries – Monday Nov 10, 2014 @ 2pm

Regret-Bounded Vehicle Routing
Professor Zachary Friggstad, Canada Research Chair Tier-II in Combinatorial Optimization, Department of Computing Science, University of Alberta.
Room: C674, University Hall

A typical vehicle routing problem involves deploying a fleet of vehicles to serve some clients. Many well-studied models are concerned mostly with the distance travelled by the vehicles. However, this objective does not differentiate between clients that are located at different distances from the depot. For example, a client closer to the depot may incur a larger delay than a client that is further away in a minimum-length TSP tour. This can be a source of client dissatisfaction.
This leads us to consider the notion of regret of a client: the time a client waits to be served in excess of its shortest-path distance from the depot. I will discuss old and new approximation algorithms for client-centric vehicle routing models and their applications to more classical models. In particular, I will present the first constant-factor approximation for the problem of deploying the fewest vehicles to ensure each client is served with regret at most some given bound B.
Students are encouraged to attend.

Professor Friggstad’s main research interests lie in designing approximation algorithms and, more specifically, in investigating the effectiveness of mathematical programming based techniques in the design of such algorithms. His research has been applied to problems in vehicle routing, facility location, resource allocation, network design, and lift-and-project techniques. Professor Friggstad is a University of Lethbridge alumnis (2005) and, as a student, he has competed twice in the ACM Programming Contest World Finals obtaining one Bronze Medal in 2006.

Optimization Seminar Series – Friday Oct 24, 2014 @ 11 am

The Impact of Social Network Influences on the Cost of Capacity Reservation
Professor Mozart Menezes, Haskayne School of Business, University of Calgary
Room: D634, University Hall

In a connected world where information moves fast and has long reach, mostly through social networks, the disclosure of personal preferences influences consumer behaviour and affects probability distribution of demand in ways that seem hard to predict. Going beyond just taking into account the intrinsic individuals’ preferences, in this paper we attempt to model for the first time the impact that social inner-circles and product market share have on (forecasted) probability distribution of demand. We find that both inner-circles’ influence and market share information may substantially increase demand variability of a product with a consequent substantial impact on costs for matching supply and demand.

Application deadline January 31, 2014

Applications from outstanding candidates are invited for a postdoctoral fellowship in algorithm design and optimization at the University of Lethbridge. The research will broadly target the development of advanced algorithms to solve challenging problems in communication networks, facility location and discrete optimization. The position is for one year, but may be extended for up to a second year, subject to the availability of funds. The preferred start date for the fellowship is on or before April 1, 2014.

The fellow will join the Optimization Research Group in the Mathematics and Computer Science Department. The group consists of faculty and graduate students at the masters and PhD level whose research areas include telecommunication, transportation and logistics, scientific computation, and bioinformatics. The group members work in a relaxed and collegial atmosphere and maintain strong research collaborations within the group, across Canada and internationally.

Lethbridge is located in Southern Alberta, close to the border with British Columbia. It is only 1.5 hours drive from the Rockies and the Waterton Lakes National Park, a UNESCO World Heritage site. The city has excellent schools providing French immersion, francophone and international baccalaureate programs, and there are numerous opportunities for extra-curricular activities at the university and the newly built arts centre. Lethbridge has hosted several high profile events including live performances from the Cirque du Soleil and Elton John.

Applicants should have a PhD degree in Computer Science or a related field, obtained in the last five years. Extensions are considered in case of maternity leave or other special circumstances. Proof of degree completion must be provided prior to the start date of the fellowship. To apply, please submit a letter of intention, a CV, a research statement, the contact information for three referees, and a sample of your publications, to the e-mail address below. Please use the subject “PDF application” in your e-mail. Applications are accepted until the position is filled. Applications received by January 31, 2014 will receive full consideration.

Robert Benkoczi, PhD,
Assistant Professor of Computer Science
University of Lethbridge
4401 University Dr
Lethbridge AB T1K3M4, Canada

Tel +1-403.329.2298

Final take home exam

Duration: 24 hours.

  • Pickup the questions on Wed. Dec 11, 9am – 10am, in my office at C556.
  • Drop off the answers on Thr. Dec 12, 9am – 10am, in my office at C556.

I recommend you stay at school for the first hour or so to read and to think about all questions. In case you need clarifications, you can see me in my office until noon on Dec 11. I do not guarantee that I will answer promptly any questions that you might send me by e-mail after Dec 11 at noon.
Attempt all questions.

Topics: everything covered in the course, including the topics from the student presentations. To prepare, attempt the relevant exercises from the textbook.