Welcome to Combinatorics and Optimization

Title: Operahedron Lattices

 Abstract: Two classical lattices are the Tamari lattice on bracketings of a word and the weak order on permutations. The Hasse diagram of each of these lattices is the oriented 1-skeleton of a polytope, theassociahedron and the permutohedron respectively. We examine a poset on bracketings of rooted trees whose Hasse diagram is the oriented 1-skeleton of a polytope called th operahedron. We show this poset is a lattice which answers question of Laplante-Anfossi. These lattices provide an extremelynatural generalization of both the Tamari lattice and the weak order.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title:What is New in Join-Aggregate Query Processing?

Abstract: : In this talk, we will address the maximum-likelihood (ML) formulation and a least-squares (LS) formulation of the time-of-arrival (TOA)-based source localization problem. Although both formulations are generally non-convex, we will show that they both possess benign optimization landscape. First, we consider the ML formulation of the TOA-based source localization problem. Under standard assumptions on the TOA measurement model, we will show a bound on the distance between an optimal solution and the true target position and establish the local strong convexity of the ML function at its global minima. Second, we consider the LS formulation of the TOA-based source localization problem. We will show that the LS formulation is globally strongly convex under certain condition on the geometric configuration of the anchors and the source and on the measurement noise. We will then derive a characterization of the critical points of the LS formulation, which leads to a bound on the maximum number of critical points under a very mild assumption on the measurement noise and a sufficient condition for the critical points of the LS formulation to be isolated. The said characterization also leads to an algorithm that can find a global optimum of the LS formulation by searching through all critical points. Lastly, we will discuss some possible future directions.

Title: Sequential Contracts on Matroids

Abstract: First, I will talk about the well-known pandora’s box problem, and then I will introduce the generalization of pandora’s box to matroids. We call this problem “sequential contracts on matroids” and we will discuss some recent results about this problem. In particular, we will look at complexity results of the problem. This is joint work with Kanstantsin Pashkovich and Jacob Skitsko for my URA project in Spring 2024.