Author Archives: benkoczi

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.
Abstract:
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.
Bio:
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.

Abstract:
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.
Texts:
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

robert.benkoczi@uleth.ca
http://www.cs.uleth.ca/~benkoczi

Final take home exam

Duration: 24 hours.
Dates:

  • 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.

Assignment 3

Due: Thr, Dec 5, in class

Undergraduate students can work in teams of two students and can submit a single paper per team.
Any notation that is not explained is standard notation. Search google for the definition. 10 pts are assigned for each problem. Answers from undergraduate students are marked out of 30 points. Answers from graduate students are marked out of 50 points.

Problem 1: (Based on Problem 3.3 in the textbook) There are $n$ jobs to be scheduled on a single machine, where each job $j$ has a processing time $p_j$, a weight $w_j$, and a due date $d_j$, $j = 1, \ldots, n$. The objective is to schedule the jobs so as to maximize the total weight of the jobs that complete by their due date.

  1. First prove that there always exists an optimal schedule in which all on-time jobs complete before all late jobs, and the on-time jobs complete in an earliest due date order.
  2. Next, give a polynomial time algorithm that finds the optimal solution to the scheduling problem for the case when all weights are one, $w_j = 1$ for all $j = 1, \ldots, n$. Justify the time complexity of your algorithm.

Problem 2: Consider the scheduling problem with arbitrary weights from Problem 1. Show how to solve this problem using dynamic programming in $O(nW )$ time, where $W = \sum_{j=1}^n w_j$. Use this result to derive a fully polynomial-time approximation scheme for the problem.

Problem 3: (Problem 4.2 in the textbook) Consider the scheduling problem from Section 4.2 in the textbook but without release times. We must schedule jobs non-preemptively on a single machine to minimize the weighted sum of completion times $\sum_{j=1}^n w_j C_j$. Suppose that the jobs are indexed such that $\frac{w_1}{p_1} \ge \frac{w_2}{p_2}
\ge \ldots \ge \frac{w_n}{p_n}$. Then show it is optimal to schedule job 1 first, job 2 second, and so on. This scheduling rule is called Smith’s rule.

Problem 4: Consider the Integer Programming formulation for the minimum cost complete matching problem in a bipartite graph from Exercise 4.6 in the text.

  1. Give an example of a bipartite graph for which there is no feasible solution to the integer programming formulation.
  2. Answer Question 4.6 a.

Problem 5: Answer Question 4.6 b.

Schedule for presentations

Farshad Barahimi: Tue Nov 19, 1:40 PM: Shortest superstring problem.
A. Golovnev, A.S. Kulikov, and I. Mihajlin, Approximating Shortest Superstring Problem Using de Bruijn Graphs. In CPM 2013, Lect. Notes Comput. Sci. 7922:120–129, 2013.
[paper]
[presentation]

Regular lecture: Tue Nov 19, 2:20 PM.

Mark Thom: Thr Nov 21, 1:40 PM : Canadian traveller problem.
Liao, Chung-Shou, and Yamming Huang. “Generalized Canadian traveller problems.” Journal of Combinatorial Optimization (2013): 1-12.
[paper]

Jayati Law: Thr Nov 21, 2:20 PM : A PTAS for the max-colouring problem in trees.
Pemmaraju, Sriram V., and Rajiv Raman. “Approximation algorithms for the max-coloring problem.” Automata, languages and programming. Springer Berlin Heidelberg, 2005. 1064-1075.
[paper]
[presentation]

Farnoush Davoodi: Tue Nov 26, 1:40 PM : Greedy algorithms for the minimum knapsack problem.
J. Csirik, J. B. G. Frenk, M. Labbe, and S. Zhang. Heuristics for the 0-1 min-knapsack ´ problem. Acta Cybernetica, 10(1-2):15-20, 1991.
[paper]
[presentation]

Jahan Kawsar: Tue Nov 26, 2:20 PM : Primal-dual algorithm for the minimum knapsack problem.
Section 7.5 in the text.

Mohammad Akbari: Thr Nov 28, 1:40 PM : Asymmetric TSP.
“Frieze, A.M., Galbiati, G., and Maffioli, F. [1982]: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12 (1982), 23–39″.
[paper]

Sina Golestanirad: Tue Nov 28, 2:20 PM: Partial set cover.
Covering Analysis of the Greedy Algorithm for Partial Cover, Tapio Elomaa and Jussi Kujala, LNCS 6060, pp. 102-113, 2010.
[paper]

Solutions to midterm and assignments

Midterm questions:
http://www.cs.uleth.ca/~benkoczi/files/approx/midterm.pdf

Midterm solutions:
http://www.cs.uleth.ca/~benkoczi/files/approx/midterm-sol.pdf

Assignment 2 questions:
http://www.cs.uleth.ca/~benkoczi/wordpress/?page_id=317

Assignment 2 solutions:
http://www.cs.uleth.ca/~benkoczi/files/approx/a2-sol.pdf

Assignment 3 questions:
http://www.cs.uleth.ca/~benkoczi/wordpress/?p=370

Assignment 3 solutions:
http://www.cs.uleth.ca/~benkoczi/files/approx/a3-sol.pdf