Welcome to the resource topic for 2022/1173
Title:
Secure Maximum Weight Matching Approximation on General Graphs
Authors: Andreas Brüggemann, Malte Breuer, Andreas Klinger, Thomas Schneider, Ulrike Meyer
Abstract:Privacy-preserving protocols for matchings on general graphs can be used for applications such as online dating, bartering, or kidney donor exchange. In addition, they can act as a building blocks for more complex protocols. While privacy preserving protocols for matchings on bipartite graphs are a well-researched topic, the case of general graphs has experienced significantly less attention so far. We address this gap by providing the first privacy-preserving protocol for maximum weight matching on general graphs. We present two protocol variants, which both compute an $1/2-$approximation instead of an optimal solution in favor of scalability. For N nodes, the first variant requires \mathcal{O}(N \log^2 N) rounds and \mathcal{O}(N^3\log N) communication, and the second variant requires only \mathcal{O}(N \log N) rounds and \mathcal{O}(N^3) communication. We implement both variants and find that the first variant runs in 14.9 minutes for N=300 nodes, while the second variant requires only 5.1 minutes for N=300, and 12.5~minutes for N=400.
ePrint: https://eprint.iacr.org/2022/1173
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .