Events

Title: Alternating Direction Method of Multipliers for the SDP Relaxation of the Quadratic Assignment Problem

Abstract:

The semidefinite programming (SDP) relaxation has proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem (QAP), arguably one of the hardest NP-hard discrete optimization problems.

Title: Sum-of-Squares Proofs in Optimization

Abstract:

The old concept of sum-of-squares found its way into optimization and even machine learning. I will talk about this quickly evolving research area known as convex algebraic geometry.

Title: Orientations, Pseudoforests, Flows, and the Densest Subgraph
 

Abstract:

Given an undirected graph, consider the problem of finding an orientation such that the max-imum indegree is minimized. The Gabow-Westermann algorithm can solve it by exploiting the matroid structure of pseudoforests.

Title: Ramsey theory for biased graphs

Abstract:

We discuss the unavoidable subgraphs of biased graphs whose underlying graph is a clique.

Title: Nash-Williams

Abstract:

Crispin Nash-Williams was one of the founding professors of C&O. The talk will cover a small sample of his mathematical work, and also his association with C&O.

Title: Efficient First-Order Methods for Linear Programming and Semidefinite Programming 

Abstract:

We will be discussing the paper (bearing the same title) of James Reneger.  We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable.

Title: Fragility and circuit-hyperplane relaxation

Abstract:

I will briefly discuss the problem of trying to determine the excluded minors for the class of GF(5)-representable matroids, highlighting the roles of N-fragility and of circuit-hyperplane relaxations.

Title: Asymmetric Latin squares, Steiner triple systems, and 1-factorizations

Abstract:

We outline how the Van der Waerden permanent theorem can be used to show that almost all Latin squares, Steiner triple systems, and 1-factorizations of the complete graph admit only trivial automorphisms. 

Title: Turan problems for matroids

Abstract:

Given a fixed simple binary matroid N, what is the maximum size of a simple rank-r binary matroid that does not contain N a restriction?

Title: Signal Recovery by Proximal Forward-Backward Splitting

Abstract:

We will be discussing the paper (bearing the same title) of Patrick Combettes and Valérie Wajs.  We show that various inverse problems in signal recovery can be formulated as the generic problem of minimizing the sum of two convex functions with certain regularity properties.