Events

Title: New algorithms for maximum disjoint paths based on tree-likeness

Abstract:

We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph.

Title: Maximum Independent Sets in Erdos-Ko-Rado Combinatorics

Abstract:  We discuss a general algebraic method for characterizing maximum independent sets in graphs that arise in Erdos-Ko-Rado combinatorics, provided the graphs are large enough. 

Title: Some problems on the size Ramsey numbers

Abstract: For given simple graphs $G_1$ and $G_2$, the size Ramsey number $\hat{R}(G_1,G_2)$ is the smallest positive integer $m$,

Title:Local Search Guarantees on Facility Location Problems

Abstract: We will show that guarantees can be given on algorithms for the k-median problem based on local search heuristics.

Title: Vertex Minors

Abstract:

I will give an introduction to vertex-minors of graphs. At first sight vertex minors are a bit peculiar but they are closely related to graph minors and possibly even easier to work with.

Title: Razborov's flag algebras: Ten years on

Abstract:

Many of the classical results in extremal combinatorics were obtained by ingenious application of elementary techniques, such as induction and Cauchy-Schwarz inequality.

Title: Hamiltonian Descent Methods

Abstract: In this talk, I will present a paper on the Hamiltonian descent methods

Title:  2-universality of random graphs.

Abstract: For a family of graphs F, a graph G is F-universal if G contains every graph in F as a (not necessarily induced) subgraph.

Title: Approximate Clustering without the Approximation

Abstract: Previously in this CombOpt Reading Group series, we have discussed improving approximation factors for particular distance-based objective functions in clustering problems.

Title: Approximation Algorithms for Distributionally Robust Stochastic Optimization

Abstract:

Two-stage stochastic optimization is a widely-used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: we make first-stage decisions knowing only the underlying distribution and before a scenario is realized, and may take additional second-stage recourse actions after a scenario is realized.