6 papers
On the Stability of Minimum-Weight Perfect Matching on the Line
Mark de Berg, Ulrike Schmidt-Kraepelin, Andree-Ovidiu Stef
Computing a minimum-weight perfect matching for a point set in Euclidean space is a classic geometric optimization problem. We consider the problem in a dynamic setting, where…
Condorcet Dimension and Pareto Optimality for Matchings and Beyond
Telikepalli Kavitha, Jannik Matuschke, Ulrike Schmidt-Kraepelin
We study matching problems in which agents form one side of a bipartite graph and have preferences over objects on the other side. A central solution concept in this setting is pop…
New Combinatorial Insights for Monotone Apportionment
Javier Cembrano, José Correa, Ulrike Schmidt-Kraepelin +2
The apportionment problem constitutes a fundamental problem in democratic societies: How to distribute a fixed number of seats among a set of states in proportion to the states' po…
The popular assignment problem: when cardinality is more important than popularity
Telikepalli Kavitha, Tamás Király, Jannik Matuschke +2
We consider a matching problem in a bipartite graph where nodes in are agents having preferences in partial order over their neighbors, while nodes in are o…
Popular Branchings and Their Dual Certificates
Telikepalli Kavitha, Tamás Király, Jannik Matuschke +2
Let be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a…
Maintaining Perfect Matchings at Low Cost
Jannik Matuschke, Ulrike Schmidt-Kraepelin, José Verschae
The min-cost matching problem suffers from being very sensitive to small changes of the input. Even in a simple setting, e.g., when the costs come from the metric on the line, addi…