Welcome to the Workshop on Matroids and Applications taking place on Tuesday (21 November, 2023) 14:00-18:00.
This workshop is a collaboration between the Research Center for Operations Management and the Department of Mathematics at KU Leuven. We welcome and encourage your participation. Feel free to join us!
Organisers: Jannik Matuschke and Fatemeh Mohammadi
Place: DV3 01.10 (Tiensestraat 41, 3000 Leuven)
Schedule:
14:00-14:45 Jannik Matuschke (Research Center for Operations Management, KU Leuven)
Title: A Constant-Factor Approximation for Generalized Malleable Scheduling under M♮-Concave Processing Speeds
Abstract: In generalized malleable scheduling, jobs can be allocated and processed simultaneously on multiple machines so as to reduce the overall makespan of the schedule. The required processing time for each job is determined by the joint processing speed of the allocated machines. We study the case that processing speeds are job-dependent M♮-concave functions and provide a constant-factor approximation for this setting, significantly expanding the realm of functions for which such an approximation is possible. Further, we explore the connection between malleable scheduling and the problem of fairly allocating items to a set of agents with distinct utility functions, devising a black-box reduction that allows to obtain resource-augmented approximation algorithms for the latter. This is joint work with Dimitris Fotakis and Orestis Papadigenopoulos.
15:00-15:45 Kristóf Bérczi (Department of Operations Research, Eötvös Loránd University)
Title: Dynamic pricing schemes in combinatorial markets
Abstract: A combinatorial market consists of a set of indivisible items and a set of agents, where each agent has a valuation function that specifies for each subset of items its value for the given agent. From an optimization point of view, the goal is usually to determine a pair of pricing and allocation of the items that provides an efficient distribution of the resources, i.e., maximizes the social welfare, or is as profitable as possible for the seller, i.e., maximizes the revenue. Dynamic pricing schemes were introduced as an alternative to posted-price mechanisms. In contrast to static models, the dynamic setting allows to update the prices between agent-arrivals based on the remaining sets of items and agents, and so it is capable of maximizing social welfare without the need for a central coordinator. In this talk, we overview recent results on the existence of optimal dynamic prices, with particular emphasis on the case of matroid rank valuations. For the case of two agents with matroid rank valuations, we give polynomial-time algorithms that always find such prices when one of the matroids is a partition matroid or both matroids are strongly base orderable, thus partially answering a question raised by Dütting and Végh. For multi-demand valuations, we propose an approach that is based on computing an optimal dual solution of the maximum social welfare problem with distinguished structural properties. By relying on an optimal dual solution, we show the existence of optimal dynamic prices in unit-demand markets, multi-demand markets with up to three agents, and bi-demand valuations with an arbitrary number of agents. Finally, we study the existence of optimal dynamic prices under fairness constraints in unit-demand markets. We propose four possible notions of envy-freeness depending on the time period over which agents compare themselves to others: the entire time horizon, only the past, only the future, or only the present.
15:45-16:15 Coffee break
16:15-17:00 Fatemeh Mohammadi (Departments of Mathematics and Computer Science, KU Leuven)
Title: Identifiability of points and rigidity of hypergraphs under algebraic constraints
Abstract: I will talk about the connection between graph rigidity theory and tensor completions. Graph rigidity theory studies the rigidity or flexibility of bar-joint linkages in Euclidean space. In other words, rigidity theory of bar and joint frameworks studies uniqueness of point configurations given some of the pairwise distances. Replacing the distance measurement with a general polynomial function, the rigidity of frameworks relates to the unique identifiability of certain tensor completions. In this talk I will present algebraic and geometric problems emerged through such a formulation, and the connection to the classical secant varieties. This is based on a joint work with James Cruickshank (National University of Ireland Galway, Ireland), Anthony Nixon (Lancaster University, UK) and Shin-ichi Tanigawa (Tokyo University, Japan).
17:15-17:30 Emiliano Liwski (Department of Mathematics KU Leuven)
Title: Defining equations of realization spaces of matroids
Abstract: I will introduce the realization space of a matroid and focus on the polynomials that vanish in all the elements of the realization space. I will present some of these polynomials for some particular examples of point-line configurations and explain how they are constructed. I will also introduce some questions and results about the irreducible decomposition of the corresponding varieties of these matroid.
17:30-17:45 Francesca Zaffalon (Department of Mathematics KU Leuven)
Title: Combinatorics of positroids
Abstract: Positroids are a family of realizable matroids with many nice combinatorial and geometric properties. In this talk I will give a brief introduction to these objects and their classical combinatorial characterization, together with a new description particularly useful in the study of the space of matrices associated with the given positroid.
17:45-18:00 Sebastian Seemann (Department of Mathematics KU Leuven)
Title: The amplituhedron and its cell decompositions
Abstract: The Amplituhedron is a novel object at the intersection of math and physics. It is defined as the projection of the positive Grassmannian via a totally positive matrix and has deep connections to quantum physics, in particular to scattering amplitudes. To establish these connections the Amplituhedron is conjectured to have a special differential form. The quest for finding this canonical differential form leads to a study of the cohomology of the Grassmannian and positroid varieties, and thus to the study of amplituhedron cells and Stanley affine symmetric functions.