5 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…
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…