Schedule

Abstract: We will discuss two different models of matching markets. In the first part, we consider a natural ascending auctions for finding Walrasian equilibria in markets with indivisible items and gross substitutes valuation functions. Each price increase step in the auction requires finding an inclusion-wise minimal maximal overdemanded set at the current prices, which is a submodular function minimization problem. We observe that this problem reduces to a polymatroid sum problem, and using this viewpoint, we give a fast and simple push-relabel algorithm for finding the minimal maximal overdemanded set, which improves on the previously best running time of Murota, Shioura and Yang (ISAAC 2013).

In the second part of the talk, we give a simpler analysis of the ascending auction of Bikhchandani, de Vries, Schummer, and Vohra (SODA 2008) to sell a welfare-maximizing base of a matroid at Vickrey prices.The new proofs for economic efficiency and the charge of Vickrey prices only require a few matroid folklore theorems, therefore shortening the analysis of the design goals of the auction significantly.

The talk is based on joint work with Katharina Eickhoff, Niklas Rieken, Laura Vargas Koch, and Laci Végh.

Abstract: Suppose we are given m (poly-)matroids with weights over the same elements. Our goal is to select one base from each of the matroids such that the loads (sum of weights) across the elements are balanced, measured by maximizing the minimum load. While the unweighted variant is easily solvable using classic results, the weighted case is NP-hard. In fact, it generalizes a variant of the Santa Claus problem and of Parallel Machine Scheduling. We give a constant approximation algorithm for this problem based on a non-trivial min-max relation.

This is joint work with Bamas, Lindermayr, Megow, and Schlöter.

Abstract: Min Cut is a canonical example of Submodular Function Minimization (SFM).  Many SFM algorithms are based on Cunningham's LP duality result, where a dual optimal vectors on the elements proves the optimality of the primal subset.  So a natural question is what these dual optimal SFM vectors look like for Min Cut.  We give a complete characterization of such vectors as being the deficit vectors of certain pseudoflows.

Abstract: Several notions of relaxed or "weak" submodularity have been introduced to explain the performance of greedy algorithms for optimisation problems with non-submodular objectives, including sparse linear regression, Bayesian A-optimal design, and column selection problems. In the cardinality constrained setting, these notions of weak submodularity lead to tight performance guarantees that are analogous to known results for submodular functions. However, for matroid constrained optimization problem the most permissive notions of approximate submodularity are not strong enough to enable the analysis of more sophisticated algorithms, while the most restrictive are so strong that they do not hold in many of the concrete applications highlighted above.  In this talk, I will discuss a natural relaxation of submodularity that enables us to obtain stronger guarantees that are applicable to these problems under general matroid constraints.  As in existing results for the cardinality constrained case, our results approach the state of the art guarantees for submodular functions as the objective becomes "closer" to submodular. I will discuss how our weakening of submodularity relates to prior definitions and highlight some of the difficulties in applying prior definitions to the setting of general matroid constraints. 

This talk is based on joint work with Theophile Thiery.

Abstract: The talk will focus on matroidal generalizations of two-sided matching problems with preferences. In particular, we consider the maximum matroid kernel problem and the maximum popular matching problem with matroid constraints. For the former, we present a 1.5-approximation algorithm for interval order preferences. For the latter, a polynomial-time algorithm is obtained when the preferences are linear orders. In both cases, the extension of previous algorithms to matroids is made possible by new observations on basis exchanges.

Joint work with Gergely Csáji and Yu Yokoi.

Abstract: Given a digraph D, a dicut is (the set of arcs of) a cut where all the arcs cross in the same direction, and a dijoin is an arc subset whose contraction makes the digraph strongly connected. It has been conjectured by Woodall (1978) that the minimum size of a dicut is equal to the maximum number of pairwise disjoint dijoins. This conjecture is an instantiation of packing common bases in two matroids, as was shown by Frank and Tardos (1984) and differently by Cornuejols, Zlatin and the speaker (2023). I will speak about recent advances towards this conjecture.

Based on joint works with Gerard Cornuejols, Siyue Liu, Olha Silinha, Giacomo Zambelli, and Michael Zlatin.

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.

Abstract: It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant Delta in absolute value, can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix.

Our approach focuses on the case where A arises from M after removing k rows only, where k is a constant. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory. First, we derive a strong proximity result for the case where A is a general totally unimodular matrix: Given an optimal solution of the linear programming relaxation, an optimal solution to the IP can be obtained by finding a constant number of augmentations by circuits of A. Second, for the case where A is transpose of a network matrix, we reformulate the problem as a maximum constrained integer potential problem on a graph G. We observe that if G is 2-connected, then it has no rooted K_{2,t}-minor for t > 4k\Delta. We leverage this to obtain a tree-decomposition of G into highly structured graphs for which we can solve the problem locally. This allows us to solve the global problem via dynamic programming.

This is joint work with Manuel Aprile (U Padova), Gwenaël Joret (ULB), Stefan Kober (ULB), Michał Seweryn (ULB), Stefan Weltge (TU Munich) and Yelena Yuditsky (ULB).

Abstract: We characterize a rich class of valuated matroids, called R-minor valuated matroids that includes the indicator functions of matroids, and is closed under operations such as taking minors, duality, and induction by network. We exhibit a family of valuated matroids that are not R-minor based on sparse paving matroids. Valuated matroids are inherently related to gross substitute valuations in mathematical economics. By the same token we refute the Matroid Based Valuation Conjecture by Ostrovsky and Paes Leme (Theoretical Economics 2015) asserting that every gross substitute valuation arises from weighted matroid rank functions by repeated applications of merge and endowment operations.

This is joint work with Ben Smith, Edin Husić and László Végh.

Abstract: The difference set of an outcome in an auction is the set of types that the auction mechanism maps to the outcome.We give a complete characterization of the geometry of the difference sets that can appear for a dominant strategy incentive compatible multi-unit auction showing that they correspond to regular subdivisions of the unit cube. We further show that the difference sets are generalized permutahedra, a generalization of matroid polytopes. In a similar way, we describe the geometry for affine maximizers for n players and m items, showing that they correspond to regular subdivisions of the m-fold product of (n-1)-dimensional simplices. These observations are then used to construct mechanisms that are robust in the sense that the sets of items allocated to the players do change only slightly when the players' reported types are changed slightly.

Abstract: In this talk, we will see that Rado matroids can be a very useful tool in approximation algorithms for matroid center problems, specifically in robust matroid center and colorful matroid center. 

Clustering problems are well-studied optimization problems.  In the classical k-center problem one gets points in a metric space together with a radius r and the goal is to select up to k centers such that all points have at most distance r to one of the selected centers.

One variant of this is the matroid center problem, a matroid-constrained optimization problem, where the set of centers that can be selected is restricted to form an independent set within a given matroid while one aims to optimize the radius.

In this talk, we will see how a simple greedy selection algorithm can achieve a 5-approximation on the radius in the robust matroid center problem by utilizing Rado matroids. Although the best-known approximation algorithm for this problem is a 3-approximation, this is significant since before no greedy procedure was known for the robust matroid center problem. Moreover, the utility of Rado matroids extends to colorful matroid center problems. Here, we provide the first constant factor approximation algorithm for the colorful matroid center problem on linear matroids, again by exploiting a Rado matroid.

The talk is based on joint work with Georg Anegg and Rico Zenklusen.

Abstract: Both the classic knapsack problem and maximum matroid independent set appear in a wide range of applications. In some cases, both a matroid and a knapsack constraint appear together, as in Multiple-Choice Knapsack and Knapsack with Cardinality Constraint. The talk will focus on the budgeted matroid independent set problem which adds a matroid independence constraint to the classic knapsack problem. The input is a ground set of elements, where each element has a cost and a profit, along with a matroid over the elements and a budget. The goal is to select a maximum profit independent set of the matroid whose total cost is bounded by the budget.

I will show how to attain an Efficient Polynomial Time Approximation Scheme (EPTAS) for the problem, improving upon the previous Polynomial Time Approximation Schemes (PTAS) [Grandoni and Zenklusen 10', Berger,  Bonifaci, Grandoni and Schäfer, 08']. The speed-up is attained via efficient enumeration which relies on the combinatorial structure of the matroid and replaces the naive enumeration used by previous algorithms. The algorithmic result will be complemented by a lower bound showing the problem does not admit a Fully Polynomial Time Approximation Scheme (FPTAS), indicating the algorithm cannot be improved for general matroids and motivating future research to focus on restricted families of matroids.

Abstract: The correlation gap of a set function measures the ratio between two natural extensions. It has has been identified as the performance guarantee in a range of approximation algorithms and mechanism design settings. It is known that the correlation gap of a monotone submodular function is 1−1/e, and this is tight even for simple matroid rank functions.

We initiate a fine-grained study of correlation gaps of matroid rank functions. In particular, we present improved lower bounds on the correlation gap as parametrized by the rank and the girth of the matroid. We also show that the worst correlation gap of a weighted matroid rank function is achieved under uniform weights.

This is joint work with Edin Husić, Zhuan Khye Koh, and Georg Loho.