{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiaxqt3phi4cvpfvk55gflaauabdvvhfu6peg6kp75tzjj5eooosp4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkrratanedm2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.27983v1",
  "publishedAt": "2026-05-01T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Tijn de Vos",
    "Leo Wennmann",
    "Malte Baumecker",
    "Yannic Maus",
    "Florian Schager"
  ],
  "textContent": "**Authors:** Tijn de Vos, Leo Wennmann, Malte Baumecker, Yannic Maus, Florian Schager\n\nIn this paper, we consider the Santa Claus problem in the CONGEST model. This NP-hard problem can be modeled as a bipartite graph of children and gifts where an edge indicates that a child desires a gift. Notably, each gift can have a different value. The goal is to assign the gifts to the children such that the least happy child is as happy as possible. Even though this is a well-studied problem in the sequential setting, we obtain the first results the distributed setting. In particular, we show that the complexity of computing an $\\mathcal{O}(\\log n/\\log \\log n)$-approximation is $\\hat Θ(\\sqrt n+D)$ rounds, where our $\\widetildeΩ(\\sqrt n+D)$-round lower bound is even stronger and holds for any approximation.",
  "title": "Distributed Santa Claus via Global Rounding"
}