Approximation algorithms – Lectures

Posted on September 5, 2013 by benkoczi| Leave a comment
Sep 5 – 19
Read Chapter 1 – Introduction and Appendix A – Linear programing.
Sep 19 – 26
Read Chapter 2 (greedy and local search): The k-center + scheduling with deadlines on a single machine + scheduling on parallel identical machines.
Oct 1-3
Chapter 2: TSP + Max float
Oct 8-10
Chapter 2: edge colouring, Chapter 3 (rounding data and PTAS): a PTAS for the knapsack problem
Oct 15-17
Chapter 3: PTAS for scheduling on identical parallel machines
Oct 22-24
Chapter 3: scheduling on identical parallel machines, bin packing
Oct 29-Nov 14
Chapter 4 (deterministic rounding): sections 4.1 – 4.5 (job scheduling to minimize weighted sum of completion times, the ellipsoid algorithm, prize collecting Steiner tree and UFL)
Nov 19-28
Student presentations (shortest super-string, Canadian traveller in double valued graphs, PTAS for max-colouring in trees, minimum knapsack greedy and primal-dual (Section 7.5), asymmetric TSP, and partial set cover).

Dec 3-5
Chapter 7 (primal-dual): 7.2, 7.6 (feedback vertex set, UFL)

→ Leave a comment

Posted in approx-course

CPSC 4110/5110 – Advanced Algorithms (Approximations)

Posted on September 5, 2013 by benkoczi| Leave a comment

This course is about designing approximation algorithms for difficult
optimization problems for which no optimal algorithms with running
time polynomial in the problem size are known. Approximation
algorithms find feasible solutions that may not be optimal but are not
too far from the optimal one.

We overview various interesting
algorithm design techniques that may prove extremely useful to
graduate students tackling research questions in various fields and to
undergraduates who may encounter interesting problems in their future
projects in the industry.

[course wbpage]

→ Leave a comment

Posted in course archive

Optimization Seminar – Thr. Apr. 11, 2013

Posted on March 28, 2013 by benkoczi| Leave a comment

Thursday April 11, from 12:15-13:05
Room E-575
Speaker: Daya Gaur.
Abstract:
Given a fleet of vehicles and a set of customers, the objective in capaciated vehicle routing problems is to minimize the total distance traveled and serve the customers subject to vehicle capacity constraints. We will examine existing approximation algorithms for deterministic and stochastic versions of capaciated vehicle routing problems.
This talk is open to everyone. Graduate students are encouraged to attend. Light refreshments will be served.

→ Leave a comment

Posted in news

Optimization Seminar – Thr. Mar 21, 2013

Posted on March 20, 2013 by benkoczi| Leave a comment

Thursday Mar 21 from 12:15-13:05
Room E-575
Speaker: Ram Dahal
Ram will talk about the weighted colouring problem in a graph and its connection to routing and scheduling in wireless networks.
Everyone is welcome. All graduate students are encouraged to attend. Light refreshments will be served.

→ Leave a comment

Posted in news

Poster presentation: Ram Dahal

Posted on March 18, 2013 by benkoczi| Leave a comment

Saturday May 16 2013:
Ram Dahal presented a poster about his research at the Meeting of the Minds conference at the University of Lethbridge. The conference is organized by the graduate students’ association and is the main event where students showcase their work to the community, establish new contacts, exchange ideas, and have a good time.

→ Leave a comment

Posted in news

Optimization Seminar – Feb 28

Posted on February 26, 2013 by benkoczi| Leave a comment

Thursday Feb 28 from 12:15-13:05
Room E-575
Speaker: Ram Dahal
Ram will talk about a paper on joint routing and scheduling in wireless networks by Mahmoud and Elmallah, “An algorithm for incremental joint routing and scheduling in wireless mesh networks”, WCNC 2010.
Everyone is welcome. All graduate students are encouraged to attend. Light refreshments will be served.

→ Leave a comment

Posted in news

Optimization Seminar – Feb 14, 2013

Posted on February 8, 2013 by benkoczi| Leave a comment

Thursday Feb 14 from 12:15-13:05
Room E-575
Speaker: Mark Thom
Mark will talk about another dynamic programming algorithm used to solve several facility location problems on the real line. The results appear in a 1996 paper of Tamir and Megiddo.
Everyone is welcome. All graduate students are encouraged to attend. Light refreshments will be served.

→ Leave a comment

Posted in news

Optimization Seminar – Feb 7, 2013

Posted on January 31, 2013 by benkoczi| Leave a comment

DATE CHANGE: Thursday Feb 7 from 12:15-13:05
Speaker: Mark Thom
Theme: Mark will talk about covering facility location problems on the real line. He will talk about his result on the customer constrained maximum covering, then about a paper by Tamir & Megiddo on facility constrained covering on the real line.

Room: E575
Thursdays, 12:15 – 13:05
Everyone is welcome. Graduate students are encouraged to participate. Light refreshments will be served.

→ Leave a comment

Posted in news

Optimization Seminar – Jan 29, 2013

Posted on January 26, 2013 by benkoczi| Leave a comment

ROOM CHANGE: E575
Title: “Algorithmic aspects of capacity in wireless networks”, Kumar et.al.
Speaker: Ram Dahal
Theme: we continue the topic of routing and interference as generalizations of max flow problems begun last week. The paper precedes Alicherry et.al. presented last week and the paper is simpler as channel assignment is not considered.

Room: E575
12:15 – 13:05
(everyone is welcome – grad students are encouraged to participate)

→ Leave a comment

Posted in news

Optimization Seminar – Jan 22, 2013

Posted on January 17, 2013 by benkoczi| Leave a comment

Our Optimization Research Group Seminar starts this semester on Tuesday Jan 23 at noon with Ram Dahal’s presentation of Alicherry et al. “Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks”. The theme of the paper is a generalization of the Maximum Flow Problem to account for interference and channel assignment in wireless networks. Everyone is welcome. Graduate students are encouraged to attend.

Location: Optimization Lab, C553
Time: 12:10 – 13:00

→ Leave a comment

Posted in news