research
∙
05/12/2023
Reconfiguration of Time-Respecting Arborescences
An arborescence, which is a directed analogue of a spanning tree in an u...
share
research
∙
05/03/2023
Algorithmic Theory of Qubit Routing
The qubit routing problem, also known as the swap minimization problem, ...
research
∙
04/28/2023
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
We prove that the computation of a combinatorial shortest path between t...
research
∙
10/18/2022
A Note on Robust Subsets of Transversal Matroids
Robust subsets of matroids were introduced by Huang and Sellier to propo...
research
∙
09/21/2022
On Reachable Assignments under Dichotomous Preferences
We consider the problem of determining whether a target item assignment ...
research
∙
08/24/2022
Strongly Stable Matchings under Matroid Constraints
We consider a many-to-one variant of the stable matching problem. More c...
research
∙
07/06/2022
Reforming an Envy-Free Matching
We consider the problem of reforming an envy-free matching when each age...
research
∙
07/04/2022
On Finding Pure Nash Equilibria of Discrete Preference Games and Network Coordination Games
This paper deals with the complexity of the problem of computing a pure ...
research
∙
05/06/2022
NP-hardness of Computing Uniform Nash Equilibria on Planar Bimatrix Games
We study the complexity of computing a uniform Nash equilibrium on a bim...
research
∙
10/22/2021
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
We initiate the study of k-edge-connected orientations of undirected gra...
research
∙
06/13/2021
On the Complexity of Fair House Allocation
We study fairness in house allocation, where m houses are to be allocate...
research
∙
03/31/2021
Optimal class assignment problem: a case study at Gunma University
In this study, we consider the real-world problem of assigning students ...
research
∙
10/08/2020
A Matroid Generalization of the Super-Stable Matching Problem
A super-stable matching, which was introduced by Irving, is a solution c...
research
∙
06/08/2020
Envy-free Relaxations for Goods, Chores, and Mixed Items
In fair division problems, we are given a set S of m items and a set N o...
research
∙
07/03/2019
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Motivated by adjacency in perfect matching polytopes, we study the short...
research
∙
02/07/2018