{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreihb3cax2v2webk6ej7nrapkkaymtjgxbuqfqjryhkur2mo5vyoziu",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mefmjdgefzy2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.06693v1",
  "publishedAt": "2026-02-09T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Robert Ganian",
    "Fionn Mc Inerney",
    "Dimitra Tsigkari"
  ],
  "textContent": "**Authors:** Robert Ganian, Fionn Mc Inerney, Dimitra Tsigkari\n\nSplit learning recently emerged as a solution for distributed machine learning with heterogeneous IoT devices, where clients can offload part of their training to computationally-powerful helpers. The core challenge in split learning is to minimize the training time by jointly devising the client-helper assignment and the schedule of tasks at the helpers. We first study the model where each helper has a memory cardinality constraint on how many clients it may be assigned, which represents the case of homogeneous tasks. Through complexity theory, we rule out exact polynomial-time algorithms and approximation schemes even for highly restricted instances of this problem. We complement these negative results with a non-trivial polynomial-time 5-approximation algorithm. Building on this, we then focus on the more general heterogeneous task setting considered by Tirana et al. [INFOCOM 2024], where helpers have memory capacity constraints and clients have variable memory costs. In this case, we prove that, unless P=NP, the problem cannot admit a polynomial-time approximation algorithm for any approximation factor. However, by adapting our aforementioned 5-approximation algorithm, we develop a novel heuristic for the heterogeneous task setting and show that it outperforms heuristics from prior works through extensive experiments.",
  "title": "Makespan Minimization in Split Learning: From Theory to Practice"
}