Poster: Sparsity-enhanced Lagrangian Relaxation (SeLR) for Computation Offloading at the Edge

Abstract

This paper proposes an efficient approach to joint task offloading and routing for real-time sensor data analytics at the network edge, enabling applications such as video surveillance and environmental monitoring. This problem can be formulated as a mixed-integer program (MIP) with the objective of utility maximization subject to the constraints of network topology, limited link capacity, and diverse task profiles. To efficiently approximate this NP-hard problem, we propose SeLR, a combination of primal-dual optimization and reweighted 𝐿1-norm regularization, which iteratively solves the convex relaxation while penalizing constraint violations and encouraging sparsity. Compared to greedy heuristics, SeLR provides a better accuracy–latency trade-off and better scalability to larger problems. Moreover, it reduces scheduling runtime by up to 9.17× over optimal solvers in networks with 300 nodes and 100 tasks.

• ACM https://dl.acm.org/doi/pdf/10.1145/3704413.3765321
• Full-length Preprint https://arxiv.org/pdf/2505.00848
• Source code available soon