research
∙
07/17/2023
Hypergraph Splitting-off and Covering Skew-Supermodular Functions in Strongly Polynomial Time
We consider hypergraph network design problems where the goal is to cons...
share
research
∙
09/29/2022
Matroid Intersection under Restricted Oracles
Matroid intersection is one of the most powerful frameworks of matroid t...
research
∙
09/06/2022
Solving the Maximum Popular Matching Problem with Matroid Constraints
We consider the problem of finding a maximum popular matching in a many-...
research
∙
08/20/2022
Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching
The Stable Marriage problem (SM), solved by the famous deferred acceptan...
research
∙
06/23/2022
On the complexity of packing rainbow spanning trees
One of the most important questions in matroid optimization is to find d...
research
∙
04/28/2022
Manipulating the outcome of stable matching and roommates problems
The stable marriage and stable roommates problems have been extensively ...
research
∙
02/09/2022
Hypergraph characterization of split matroids
We provide a combinatorial study of split matroids, a class that was mot...
research
∙
10/21/2021
The popular assignment problem: when cardinality is more important than popularity
We consider a matching problem in a bipartite graph G=(A∪ B,E) where eac...
research
∙
07/21/2021
Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems
We study how good a lexicographically maximal solution is in the weighte...
research
∙
12/04/2019
Popular Branchings and Their Dual Certificates
Let G be a digraph where every node has preferences over its incoming ed...
research
∙
11/26/2019
Scheduling with Non-Renewable Resources: Minimizing the Sum of Completion Times
The paper considers single-machine scheduling problems with a non-renewa...
research
∙
11/19/2018
Equitable Partitions into Matchings and Coverings in Mixed Graphs
Matchings and coverings are central topics in graph theory. The close re...
research
∙
07/25/2018