The C&O department has 36 faculty members and 60 graduate students. We are intensely research oriented and hold a strong international reputation in each of our six major areas:
- Algebraic combinatorics
- Combinatorial optimization
- Continuous optimization
- Cryptography
- Graph theory
- Quantum computing
Read more about the department's research to learn of our contributions to the world of mathematics!
News
Three C&O faculty win Outstanding Performance Awards
The awards are given each year to faculty members across the University of Waterloo who demonstrate excellence in teaching and research.
Sina Kalantarzadeh wins Governor General's Gold Medal
The Governor General’s Gold Medal is one of the highest student honours awarded by the University of Waterloo.
Two C&O faculty win Outstanding Performance Awards
The awards are given each year to faculty members across the University of Waterloo who demonstrate excellence in teaching and research.
Events
CombOpt ReadingGroup - Sina Kalantarzadeh-Minimum Bounded Degree Spanning Trees
Abstract: I will present Goemans’s beautiful, though no longer state-of-the-art, 2006 result on the Minimum Bounded-Degree Spanning Tree problem. Given a weighted graph (G=(V,E)) and degree bounds (B\to\mathbb{N}), the goal is to find a minimum-cost spanning tree (T) satisfying (d_T(v)\le B(v)) for every (v\in V). This problem is NP-hard. Fürer and Raghavachari (1992) gave a polynomial-time algorithm for the unweighted setting that produces a spanning tree satisfying (d_T(v)\le B(v)+1). For the weighted problem, Goemans designed an elegant LP-rounding algorithm that returns a tree of cost at most that of the optimal degree-bounded solution while satisfying (d_T(v)\le B(v)+2). I will explain this result and the simple yet beautiful combinatorial optimization ideas underlying it. In 2007, Singh and Lau improved the violation to (B(v)+1) using iterative relaxation, which I might give a talk about in later sessions. |
Tutte Colloquium -Kanstantsin Pashkovich-Simple and Almost Non-Adaptive 1/2-Approximation for Matroid Prophet Inequalities
| Speaker: | Kanstantsin Pashkovich |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: Prophet inequalities are a fundamental model for online decision-making under uncertainty. For matroid constraints, Kleinberg and Weinberg gave a tight 1/2-approximation, but their algorithm uses adaptive thresholds that depend on the previously accepted elements. Specifically, the mechanism of Kleinberg and Weinberg accepts an arriving element if and only if it is feasible to add with respect to the matroid constraint and the value of the arriving element passes its threshold; but this threshold depends on the elements accepted so far and on the arriving element itself. Later, Feldman, Svensson, and Zenklusen showed that one can give a 1/4-approximation for general matroids. Their algorithm is almost non-adaptive, i.e., it uses non-adaptive thresholds but changes the underlying matroid to another ``stricter'' matroid. Feldman, Svensson, and Zenklusen also showed that no constant approximation is possible in general matroids using non-adaptive thresholds if one does not change the underlying matroid.
Optimization seminar-Ting Kei Pong-A Conditional-Gradient-Based Single-Loop Augmented Lagrangian Method for Inequality Constrained Problems
| Speaker: | Ting Kei Pong |
| Affiliation: | The Hong Kong Polytechnic University |
| Location: | MC 5501 |
Abstract:We consider the problem of minimizing the sum of a Lipschitz differentiable convex function and a proper closed convex function that admits efficient linear minimization oracles, subject to multiple smooth convex inequality constraints. We adapt the classical augmented Lagrangian (AL) method for these problems: in each iteration, our algorithm consists of one step of conditional gradient (CG) method applied to the AL function, followed by an update of the dual variable as in classical AL methods with a diminishing dual stepsize. We study the convergence rate of our algorithm under two standard stepsize rules for the CG method, namely, an open-loop stepsize and the short stepsize, and obtain a rate that matches the best-known complexity for this class of problems. We also establish accelerated rates when the aforementioned proper closed convex function is the indicator function of a uniformly convex set. This is a joint work with Xiaozhou Wang and Zev Woodstock.