# Makespan Minimization in Split Learning: From Theory to Practice

arXiv: https://arxiv.org/abs/2602.06693 · HTML: https://mlsanity.com/paper/2602.06693/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 48 references that are in the map.
- First posted on arXiv 6 Feb 2026.

## Builds on (most cited first, 21 of 21)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Split learning for health: Distributed deep learning without sharing raw patient data](https://mlsanity.com/paper/1812.00564/) (2018)
- [SplitFed: When Federated Learning Meets Split Learning](https://mlsanity.com/paper/2004.12088/) (2020)
- [Distributed learning of deep neural network over multiple agents](https://mlsanity.com/paper/1810.06060/) (2018)
- [Unleashing the Tiger: Inference Attacks on Split Learning](https://mlsanity.com/paper/2012.02670/) (2020)
- [Efficient Parallel Split Learning over Resource-constrained Wireless Edge Networks](https://mlsanity.com/paper/2303.15991/) (2023)
- [Split Learning over Wireless Networks: Parallel Design and Resource Management](https://mlsanity.com/paper/2204.08119/) (2022)
- [Split Learning in 6G Edge Networks](https://mlsanity.com/paper/2306.12194/) (2023)
- [Hierarchical Split Federated Learning: Convergence Analysis and System Optimization](https://mlsanity.com/paper/2412.07197/) (2024)
- [The SCIP Optimization Suite 9.0](https://mlsanity.com/paper/2402.17702/) (2024)
- [A Bargaining Game for Personalized, Energy Efficient Split Learning over Wireless Networks](https://mlsanity.com/paper/2212.06107/) (2022)
- [Privacy and Efficiency of Communications in Federated Split Learning](https://mlsanity.com/paper/2301.01824/) (2023)
- [Evaluation and Optimization of Distributed Machine Learning Techniques for Internet of Things](https://mlsanity.com/paper/2103.02762/) (2021)
- [MergeSFL: Split Federated Learning with Feature Merging and Batch Size Regulation](https://mlsanity.com/paper/2311.13348/) (2023)
- [Split Federated Learning for 6G Enabled-Networks: Requirements, Challenges and Future Directions](https://mlsanity.com/paper/2309.09086/) (2023)
- [Workflow Optimization for Parallel Split Learning](https://mlsanity.com/paper/2402.10092/) (2024)
- [Santa Claus meets Makespan and Matroids: Algorithms and Reductions](https://mlsanity.com/paper/2307.08453/) (2023)
- [Data Heterogeneity and Forgotten Labels in Split Federated Learning](https://mlsanity.com/paper/2511.09736/) (2025)
- [Scheduling meets n-fold Integer Programming](https://mlsanity.com/paper/1603.02611/) (2016)

## Abstract (arXiv)

Split 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.