Events

Title: Stochastic Knapsack Problem

Abstract: The classical NP-hard Knapsack problem takes as input a set of items with some fixed values and weights. The goal is to compute a subset of items of maximum total value, subject to the constraint that the total weight of these elements is less than or equal to a given limit. In this talk we will review a paper by Dean, Goemans and Vondrák, in which an stochastic variation of this problem is considered. 

Title: Equiangular lines and eigenvalue multiplicities

Abstract: Solving a longstanding problem on equiangular lines, we determine, for each given fixed angle and in all sufficiently large dimensions, the maximum number of lines pairwise separated by the given angle.

Title: Conditional Value-at-Risk

Abstract: The mean and variance of a probability distribution may not reflect what one wants from a scenario involving uncertainty.In particular, such measures fall short of expressing risk in a way suitable for financial and similar applications.

Title: On sesqui-regular graphs with fixed smallest eigenvalue

Abstract: Let λ ≥ 2 be an integer. For strongly regular graphs with parameters (v, k, a, c) and fixed smallest eigenvalue −λ, Neumaier gave two bounds on c by using algebraic property of strongly regular graphs. Subsequently, we studied a new class of regular graphs called sesqui-regular graphs, which contains strongly regular graphs as a subclass, and proved that for a given sesqui-regular graph with parameters (v, k, c) and smallest eigenvalue −λ, if k is very large, then either c ≤ λ² (λ − 1) or v − k − 1 ≤ (λ−1)²/4 + 1. This is joint work with Jack Koolen, Brhane Gebremichel and Jae Young Yang

Title: Stochastic Probing with Applications

Abstract:  We will explore a stochastic probing problem. Given a set of elements which have weights and independent probabilities of being "active," the goal is to construct a subset of active elements of maximum weight. To form such a set, we must "probe" elements sequentially to determine whether they are active.

Title: Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues

Abstract:

The classical Cheeger's inequality relates the edge conductance $\phi$ of a graph and the second smallest eigenvalue $\lambda_2$ of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality $\psi^2 / \log |V| \lesssim \lambda_2^* \lesssim \psi$ connecting the vertex expansion $\psi$ of a graph $G=(V,E)$ and the maximum reweighted second smallest eigenvalue $\lambda_2^*$ of the Laplacian matrix. In this work, we first improve their result to $\psi^2 / \log d \lesssim \lambda_2^* \lesssim \psi$ where $d$ is the maximum degree in $G$, which is optimal assuming the small-set expansion conjecture. Also, the improved result holds for weighted vertex expansion, answering an open question by Olesker-Taylor and Zanetti. 

Title: Essential Covers of the Cube by Hyperplanes

Abstract:  An essential cover of the vertices of the n-cube $\{0,1\}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant, and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with $\lceil \frac{n}{2} \rceil + 1$ hyperplanes and showed that $\Omega(\sqrt{n})$ hyperplanes are required.

Title: Graphical Designs and Gale Duality

Title: On the Adaptivity Gap of Stochastic Orienteering

Abstract: This talk highlights the stochastic orienteering problem, in which we are given a budget B and a graph G=(V,E) with edge distances d(u,v) and a starting vertex x. Each vertex v represents a job with a deterministic reward and a random processing time, drawn from a known distribution.

TItle: A perfect graph, a sparse, symmetric matrix and a homogeneous cone walk into a bar … together??

Abstract:  The talk title above sounds like the beginning of a corny joke; however, in this talk, we will indeed utilize results from a very large number of research areas. Many of these research areas are directly within Combinatorics and Optimization and some are from other areas covered in the rest of the Faculty of Mathematics.