Combinatorial Online Selection with Minimal Priors

In online selection problems, like online (combinatorial) auctions, a number of elements is presented one-by-one, and one has to pick a subset (respecting given constraints) of the elements optimizing some function over the chosen set.

Achieving reasonable competitive ratios is only possible under additional assumptions, like knowing the distributions of the elements' valuations. Recently, a line of work shows that it suffices for many scenarios if instead of full distributions, only some samples are known from each of them. Focusing on the extreme (and in a sense, minimal) case of having only one such sample, we give an overview of a very general technique for obtaining constant-factor approximations, and various scenarios where this is possible.

Optimal structures in random graphs

Subgraphs contain important information about network structures and their functions. But where can we find these subgraphs in random graphs? Interestingly, this question leads to mixed integer optimization problems on random graphs that identify the dominant structure of any given subgraph. The optimizer describes the degrees and the spatial locations of the vertices that together create the most likely subgraph. On the popular hyperbolic random graph model, our optimization problem shows the trade-off between geometry and popularity: some subgraphs are most likely formed by vertices that are close by, whereas others are most likely formed by vertices of high degree. This insight makes it possible to create optimal statistics that detect the presence of an underlying spatial structure.

Flip Graphs and Matroids

The term “flip graph” has originally been used for studying flips in triangulations, but has since been defined for a variety of combinatorial structures, where a flip can be defined as an elementary, local, reversible operation. Flip graphs are defined on sets of combinatorial structures (typically all structures of a given fixed size n), and two vertices are adjacent whenever they differ by exactly one flip.

In order to contribute to a unified theory of flip graphs and the associated combinatorial and computational problems, we will adopt the viewpoint of matroid theory. Matroids are well-studied set systems that obey axioms capturing an abstract notion of independence, that generalize linear independence. There are many fruitful connections to be established between polytopal flip graphs described in the algebraic combinatorics literature (Postnikov) and matroid structures developed decades ago in the context of combinatorial optimization (Edmonds). Through these connections, we can cast several fundamental computational issues related to geodesics, diameters, and Hamiltonian walks on flip graphs in a larger context, and formulate new ones.