Dutch Day on Optimization
The main purpose of the event is to bring together the Dutch Optimization community across the areas of operations research, computer science and discrete mathematics. The event will highlight the research of both national and international speakers. Participants from outside the Netherlands are of course also welcome!
The Dutch Day on Optimization is the second in-person event associated with the on-line Dutch Seminar on Optimization (see website). This is the second incarnation of the in-person event: in 2022 it was at CWI in Amsterdam. This year we are delighted to host it at Maastricht University.
Registration is free. The registration deadline is 01 November, but please register as early as possible to help us with planning and catering. Only register if you plan to attend the event in person.
You can use the registration form to indicate your potential interest in presenting a lightning talk, and to indicate any dietary restrictions. Lunch, coffee breaks and drinks/snacks will be provided.
|11:00||Word of welcome|
|11:05||Rebecca Reiffenhäuser (UvA) - Combinatorial Online Selection with Minimal Priors|
|14:15||Clara Stegehuis - Optimal structures in random graphs|
|15:40||Jean Cardinal (Brussels) - Flip Graphs and Matroids|
|16:35||Drinks and snacks|
- Steven Kelk (Department of Advanced Computing Sciences, Faculty of Science and Engineering, UM) – local organizer
- Tjark Vredeveld (Quantitive Economics, School of Business and Economics, UM) – local organizer
- Daniel Dadush (CWI)
Feel free to contact the local organizers about any logistical issues.
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.
The event takes place in Room F0.019 of the building Tapijnkazerne 11, 6211 ME Maastricht. This is a newly renovated building of the School of Business and Economics. It is approximately a 25-30 minute walk from the train station in Maastricht – here is a suggested walking route - or a 5-10 minute cycle.
The room F0.019 is on the ground floor of the building. However, the main entrance to the building is below ground level (i.e. at level minus one), via the sunken ampitheatre in front of the building. After you enter the below-level glass doors that face the main road, you will need to go one floor up.
We kindly acknowledge financial support from Mathematics Centre Maastricht (MCM), University Fund Limburg/SWOL and the support of the two organizing faculties at UM: the School of Business and Economics (SBE) and the Faculty of Science and Engineering (FSE).