The research group will present two papers at ESA! The first one, Approximating maximum-size properly colored forests deals with the problem of finding a maximum sized properly colored forest in edge colored graphs. The second, Hypergraph Connectivity Augmentation in Strongly Polynomial Time considers hypergraph network design problems where the goal is to construct a hypergraph…
As a continuation of our work on the quotient-convergence of submodular setfunctions, in the paper Cycle Matroids of Graphings: From Convergence to Duality, we study the connection between local-global convergence of graphs and quotient-convergence of their cycle matroids. We characterize the exposed points of the associated convex set, forming an analytic counterpart of matroid base-polytopes.…
In our paper Quotient-convergence of Submodular Setfunctions, we introduce the concept of quotient-convergence for sequences of submodular set functions, providing, among others, a new framework for the study of convergence of matroids through their rank functions. Extending the limit theory of bounded degree graphs, which analyzes graph sequences via neighborhood sampling, we address the challenge…
Inverse and bilevel optimization problems play a central role in both theory and applications. These two classes are known to be closely related and thus have often been discussed together In a recent paper titled On the Complexity of Inverse Bivariate Multi-unit Assignment Valuation Problems, we consider inverse problems for multi-unit assignment valuations. Multi-unit assignment…
Submodular set functions are undoubtedly among the most important building blocks of combinatorial optimization. Somewhat surprisingly, continuous counterparts of such functions have also appeared in an analytic line of research where they found applications in the theory of finitely additive measures, nonlinear integrals, and electric capacities. Recently, a number of connections between these two branches…