Events

Filters
Export this event to calendar
iCal
RSS
RSS
Close X

Filter by:

Limit to events where the title matches:
Limit to events where the first date of the event:
Date range
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Friday, January 6, 2012 3:30 pm - 3:30 pm EST (GMT -05:00)

Tutte seminar - U.S.R. Murty

On minimal non-Pfaffian graphs

Speaker: U.S.R. Murty
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Let $G$ be a graph. An even cycle in $G$ is alternating if its edges belong alternately to two different perfect matchings of $G$.

Friday, January 13, 2012 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte seminar - Osman Ozaltin

Two-Stage Quadratic Integer Programs with Stochastic Right-Hand Sides

Speaker: Osman Ozaltin
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. A two-phase solution approach is proposed.

Friday, January 27, 2012 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte seminar - Helene Gehrmann

Graphical Gaussian Models with Symmetries and algebraic combinatorics

Speaker: Levent Tunçel
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Graphical Gaussian models with symmetries are statistical models which combine statistical independence relations with equality constraints on model parameters, and can be compactly represented by vertex and edge colored graph

Friday, February 3, 2012 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte seminar - Dominique Orban

Degeneracy in Continuous Optimization

Speaker: Dominique Orban
Affiliation: GERAD and Ecole Polytechnique de Montreal
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Over the past two decades, interior-point methods for smooth problems have emerged in the optimization community as the de-facto standard for the efficient solution of large-scale linear, convex, and nonconvex optimization problems.

Friday, February 10, 2012 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte seminar - Ashwin Nayak

The Quantum Substate Theorem

Speaker: Ashwin Nayak
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Consider quantum states ρ, σ in the same finite dimensional Hilbert space. We say that ρ is a c-substate of σ if ρ &le 2c σ, where &le represents the Lowner partial order.

Friday, February 17, 2012 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte seminar - Thomas RothvoB

Some 0/1 Polytopes need exponential size extended formulations

Speaker: Thomas RothvoB
Affiliation: MIT
Room: Mathematics & Computer Building (MC) 5158

Abstract:

We prove that there are 0/1 polytopes P that do not admit a compact LP formulation. More precisely we show that for every n there is a set X ⊆ {0,1}n such that conv(X) must have extension complexity at least 2{n/2 * (1-o(1))}.

Friday, March 2, 2012 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte seminar - Jochen Koenemann

Solving Structured Set Cover Instances via Geometric Sampling

Speaker: Jochen Koenemann
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

The minimum-weight set cover problem is widely known to be O(log n)-approximable, with no improvement possible in the general case.

Friday, March 9, 2012 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte seminar - Jim Geelen

An extermal problem in finite geometry

Speaker: Jim Geelen
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

For a given restriction $H$ of PG$(m-1,q)$ and any $n>m$, we consider the maximum number of points in PG$(n-1,q)$ not containing a copy of $H$. We prove a striking analogue of the Erdös-Stone Theorem.

Friday, March 16, 2012 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte seminar - Hyung-Chan An

Improving Christofides' Algorithm for the s-t Path TSP

Speaker: Hyung-Chan An
Affiliation: Cornell University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

We present a deterministic (1+ √ 5  )/2-approximation algorithm for the s-t path TSP for an arbitrary metric.

Friday, March 23, 2012 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte seminar - Per Austin

Better balance by being biased: a 0.8776-algorithm for Max Bisection

Speaker: Per Austrin
Affiliation: University of Toronto
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Recently Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm algorithm for the Max Bisection problem. We improve their algorithm to a 0.8776-approximation.