The Matroid Secretary Problem is a central question in online optimization, modeling sequential decision-making under combinatorial constraints. Despite significant progress, the Matroid Secretary Conjecture — which asks whether every matroid admits a constant-competitive algorithm — remains open. In the paper Free-Order Secretary for Two-Sided Independence Systems, we introduce a bipartite graph framework that unifies and…
Finding a Steiner strongly $k$-arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set of critical nodes. Király and Lau introduced a rooted variant, called the Steiner Rooted Orientation problem, where one is given an undirected graph on $n$ vertices, a root vertex, and a set…
Narayanan and Fujishige showed the existence of the principal partition sequence of a submodular function, a structure with numerous applications in areas such as clustering, fast algorithms, and approximation algorithms. In our recent paper $\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions, motivated by two applications, we develop a theory of $\{s,t\}$-separating principal partition sequence of…
Our paper on the Interaction between skew-representability, tensor products, extension properties, and rank inequalities was accepted to SODA! The paper explores skew-representable matroids, a fundamental class connecting combinatorics and linear algebra with applications in coding theory, optimization, and geometry. Since deciding skew-representability is computationally hard, we study it through a new perspective: tensor products. This…
Our paper on splitting-off operations in hypergraphs was accepted to JCTB! In this work, we introduce a splitting-off operation in hypergraphs, prove the existence of a local connectivity-preserving complete splitting-off, and give a strongly polynomial-time algorithm to compute it in weighted hypergraphs.