Title: Greedy Heuristic for Maximizing Submodular Set FunctionsSpeaker: Ishan Bansal Affiliation: University of Waterloo Room: MC 5417
Several hard combinatorial optimization problems can be posed in the following framework: maximize a submodular function over its domain subject to a cardinality constraint.
Title: Extending drawings of K(n) to pseudolines and pseudocirclesSpeaker: Bruce Richter Affiliation: University of Waterloo Room: MC 5501
In the early part of the 21st century, it was shown that the number of crossings in a straight-line drawing of K(n) is at least the number H(n), which is conjectured to be the crossing number of K(n). In fact, it is now known that, for n at least 10, the inequality is strict.