A fundamental variant of the classical traveling salesman problem (TSP) is the so-called multiple TSP (mTSP), where a set of salesmen jointly visit all cities from a set of cities. The mTSP models many important real-life applications, in particular for vehicle routing problems. In our paper titled Many-visits multiple traveling salesman problems that was recently…
Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds’ fundamental theorem provides a min-max characterization for the unweighted setting, while Frank’s weight-splitting theorem provides one for the weighted case. Several efficient algorithms were developed for these problems, all relying on the usage of one…
While the problem of packing common bases in the intersection of two matroids was shown to be hard in general by Bérczi and Schwarcz, identifying tractable special cases remained an interesting problem. In particular, when one of the matroids is a partition matroid and the other is the graphic matroid of an undirected graph, then…
Baker and Norine initiated the study of graph divisors as a graph-theoretic analogue of the Riemann-Roch theory for Riemann surfaces. One of the key concepts of graph divisor theory is the rank of a divisor on a graph. Kiss and Tóthmérész reformulated the problem using chip-firing games, and showed that computing the rank of a…
In stable marriage and stable roommates problems, it might happen that no stable solution exists, or stable solutions do not meet certain requirements. In such cases, one might be interested in modifying the instance so that the existence of a stable outcome with the desired properties is ensured. In a recent manuscript titled Manipulating the…