1 citations · 2 across the 5 of their papers we have counts for
5 papers
Matching Markets with Chores
Jugal Garg, Thorben Tröbst, Vijay V. Vazirani
The fair division of chores, as well as mixed manna (goods and chores), has received substantial recent attention in the fair division literature; however, ours is the first paper…
Almost Tight Bounds for Online Hypergraph Matching
Thorben Tröbst, Rajan Udwani
In the online hypergraph matching problem, hyperedges of size over a common ground set arrive online in adversarial order. The goal is to obtain a maximum matching (disjoint se…
Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient Computability
Thorben Tröbst, Vijay V. Vazirani
Unlike ordinal-utility matching markets, which are well-developed from the viewpoint of both theory and practice, recent insights from a computer science perspective have left card…
Online Matching with High Probability
Milena Mihail, Thorben Tröbst
We study the classical, randomized Ranking algorithm which is known to be -competitive in expectation for the Online Bipartite Matching Problem. We give a tail i…
A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings
Thorben Tröbst, Vijay V. Vazirani
In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph $G \sub…