# Service Placement with Provable Guarantees in Heterogeneous Edge Computing Systems

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2019.

## Built on by (most cited first, 6 of 6)

- [SplitLLM: Collaborative Inference of LLMs for Model Placement and Throughput Optimization](https://mlsanity.com/paper/2410.10759/) (2024)
- [Adaptive Compression-Aware Split Learning and Inference for Enhanced Network Efficiency](https://mlsanity.com/paper/2311.05739/) (2023)
- [Learning Augmented Index Policy for Optimal Service Placement at the Network Edge](https://mlsanity.com/paper/2101.03641/) (2021)
- [Digital Twin-Empowered Network Planning for Multi-Tier Computing](https://mlsanity.com/paper/2210.02616/) (2022)
- [Tailored Learning-Based Scheduling for Kubernetes-Oriented Edge-Cloud System](https://mlsanity.com/paper/2101.06582/) (2021)
- [On the Regret of Online Edge Service Hosting](https://mlsanity.com/paper/2303.06851/) (2023)

## Abstract (arXiv)

Mobile edge computing (MEC) is a promising technique for providing low-latency access to services at the network edge. The services are hosted at various types of edge nodes with both computation and communication capabilities. Due to the heterogeneity of edge node characteristics and user locations, the performance of MEC varies depending on where the service is hosted. In this paper, we consider such a heterogeneous MEC system, and focus on the problem of placing multiple services in the system to maximize the total reward. We show that the problem is NP-hard via reduction from the set cover problem, and propose a deterministic approximation algorithm to solve the problem, which has an approximation ratio that is not worse than left(1-e-1right)/4. The proposed algorithm is based on two sub-routines that are suitable for small and arbitrarily sized services, respectively. The algorithm is designed using a novel way of partitioning each edge node into multiple slots, where each slot contains one service. The approximation guarantee is obtained via a specialization of the method of conditional expectations, which uses a randomized procedure as an intermediate step. In addition to theoretical guarantees, simulation results also show that the proposed algorithm outperforms other state-of-the-art approaches.