Events

Cones, Polytopes and Ellipsoids a result by F. John

Abstract:

Cones, polytopes and ellipsoids are all objects of interest in optimization. In this talk, I will discuss some of their interesting relations and a theorem on minimum volume ellipsoid for sets in Euclidean space.

Combinatorical algorithms for submodular function minimization and related problems

Abstract:

The submodular function minimization problem generalizes the classical minimum cut problem and contains a number of other well-known combinatorial optimization problems as special cases.

Finding a shortest circuit

Abstract:

Vardy proved that the problem of finding a shortest circuit in binary matroid is NP-hard.

Interlacing families: a new technique for controlling eigenvalues

Abstract:

Matrices are one of the most fundamental structures in
mathematics, and it is well known that the behavior of a matrix is

Cyclicity of a random subgraph

Abstract:

Let $G$ be a simple graph of average degree $d$, and let $H$ be a spanning subgraph of $G$ chosen by including each edge of $G$ independently with fixed probability $p$.

Local algorithms: a bridge between probabilistic and deterministic results about graphs

Abstract:

We shall report on properties of regular graphs with large girth that may be derived from the analysis of a class of randomised algorithms.

Title: Weighted matching on general graphs: faster and simpler