Source-linked AI summary
Service Placement with Provable Guarantees in Heterogeneous Edge Computing Systems
Stephen Pasteris, Shiqiang Wang, Mark Herbster, Ting He
TL;DR
The paper addresses how to place multiple services in heterogeneous MEC systems to maximize total reward under capacity and placement constraints. It proves the problem is NP-hard and develops deterministic approximation algorithms based on slot partitioning and conditional expectations. The final algorithm has an approximation ratio of (1 − e^−1)/4 and performs close to optimal and better than the compared baselines in simulations.
Problem
The paper asks how to maximize total reward when placing services across heterogeneous edge nodes serving users with different requirements and rewards.
Method
The paper converts GSP to the equivalent SPSC formulation and uses slot-based approximation algorithms with conditional expectations.
Results
(1 − e^−1)/4 is the approximation ratio of the final general-case algorithm, which performs close to optimal and better than greedy and LP-rounding baselines in simulations.
Takeaways & Limitations
The proposed approach provides a constant-factor approximation for heterogeneous service placement and empirically achieves near-optimal performance.
Abstract
from arXiv · showhide
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^{-1}\right)/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.
I. INTRODUCTION
The paper studies service placement in heterogeneous MEC systems, where node, service, and user differences complicate maximizing reward under capacity constraints. It formulates equivalent optimization problems, proves NP-hardness, and develops approximation algorithms with theoretical and empirical guarantees.
- Problem setting: MEC service placement assigns services to heterogeneous edge nodes to satisfy user demand while accounting for node, service, and user differences.These differences include communication latency, resource consumption, hardware compatibility, and strict node capacities.
- Algorithmic approach: The proposed algorithms use a novel partition of each edge node into multiple slots and a specialized application of conditional expectations.Each slot represents capacity for one service, while the conditional-expectations method supports the approximation guarantee.
- Problem formulation: The paper formulates the general service placement problem and converts it to the equivalent service placement with set constraints problem.The transformed problem is intended to be easier to approximate while preserving feasible placements.
- Complexity: Both GSP and SPSC are NP-hard, via a reduction from the decision version of set cover.The result establishes computational difficulty for both formulations.
C. Converting GSP to SPSC
The paper converts GSP into an equivalent SPSC formulation, preserving feasible placements and rewards while enabling approximation algorithms. It then formulates an LP-based approach that serves as the foundation for slot-allocation algorithms.
- Problem transformation: GSP is NP-hard, so the paper transforms it into an equivalent SPSC problem that is easier to approximate.The conversion preserves feasibility and reward for every feasible service placement.
- Equivalence construction: The GSP-to-SPSC construction orders nodes by user reward and creates restricted users whose satisfaction thresholds reproduce the original placement reward.The equivalence proof identifies the first selected node in the ordering and shows that all corresponding restricted users are satisfied exactly from that threshold onward.
- Equivalence construction: Both GSP and SPSC retain the same services, nodes, service sizes, node capacities, and feasible service placements.The conversion changes the user representation and reward structure, not the underlying placement feasibility constraints.
- LP relaxation: The approximation framework begins by solving a linear program whose variables represent service placements and user satisfaction, with infeasible service-node assignments forced to zero.The LP optimum provides an upper-bound benchmark used by the subsequent algorithms.
A. Slots Allocations
The slot-allocation framework partitions edge-node capacity into service-bearing slots and maps slot assignments back to feasible service placements. Its analysis uses a randomized distribution, while conditional expectations yields a deterministic allocation with a reward guarantee.
- Slot model: A slot is a capacity-limited space on an edge node that holds one service permitted for that slot.Slots are indexed by node and slot type, and their capacities are chosen from node capacity parameters.
- Slot model: A slot allocation assigns each slot a service from its admissible set, while a partial allocation may leave slots empty.The admissibility condition ensures that an assigned service fits within the slot capacity.
- Placement mapping: A slot allocation induces a service placement by placing service i on node j whenever some slot on j contains i.This mapping allows the slot representation to encode the original placement decision.
- Feasibility: Any slot allocation produces a feasible service placement.The feasibility theorem follows from slot admissibility and the bound on the number of slots created for each node and slot type.
- Deterministic construction: The analysis samples services independently for slots according to LP-derived probabilities, then uses conditional expectations to obtain a deterministic allocation.The randomized procedure is only an analysis device; the implemented algorithm computes expected values and makes deterministic choices.
- Reward analysis: The randomized slot distribution achieves expected total reward at least (1 −e−δ)R, which is transferred to the deterministic algorithm through the expectation analysis.The guarantee relies on independently filled slots and the probability that each user is served at an appropriate node.
C. Placing Services
The placing-services procedure fixes slot assignments one at a time by choosing the service with the largest conditional expected reward. This preserves the expectation guarantee and outputs a feasible placement with a provable reward bound.
- Guarantee preservation: The conditional-expectation invariant ensures that the final deterministic allocation retains at least the initial randomized expected reward.The proof partitions completions of the partial allocation by the service assigned to the current slot and selects the best part.
- Greedy conditional choice: The algorithm selects an empty slot and evaluates every admissible service assignment through its conditional expected reward.For each candidate service, it forms a partial allocation and computes the corresponding expectation.
- Greedy conditional choice: At each step, the algorithm assigns the service maximizing the conditional expectation and updates the partial slot allocation.Repeating this process eventually fills every slot and produces the final allocation ψ.
- Guarantee preservation: The resulting placement Xψ is feasible and has total reward at least (1 −e−δ)R.Feasibility follows from the slot-allocation theorem, while the reward guarantee follows from the preceding expectation results.
- Expectation computation: Algorithm 4 computes the conditional expectation used to compare candidate assignments during the placement procedure.Its correctness follows by considering whether a user is already guaranteed service or remains dependent on independently filled slots.
V. SECOND SLOT ALLOCATION ALGORITHM (SA2)
SA2 extends slot allocation to services of arbitrary size by labeling each node and creating different slot structures. Its analysis proves feasibility and an approximation guarantee for this general case.
- SA2 scope and guarantee: SA2 handles arbitrarily large services by fixing β = 1/4, which gives γ = 1/2 and δ = 1/4.Its stated approximation ratio is 1 −e−1 /4.
- Slot construction: SA2 differs from SA1 mainly in how it creates slots for each edge node.The subsequent placement procedure remains based on the slot-allocation framework used for SA1.
- Slot construction: A construction map labels every node 1, 2, or 3, and each label determines the node’s associated slot structure.Label 1 creates one ⊕ slot, label 2 creates two ⊖ slots, and label 3 creates capacity-indexed slots.
- Probabilistic analysis: The theoretical analysis samples node labels independently and then samples slot allocations using the SA1-style distribution.The deterministic algorithm uses conditional expectations to guide the construction rather than retaining the random sampling step.
- Feasibility: Every slot allocation with non-zero probability under SA2 induces a feasible service placement.This establishes feasibility for the randomized constructions used in the approximation analysis.
C. Creating Slots
The slot-creation procedure labels nodes by choosing the construction that maximizes D(ζ), then builds the associated slots for service placement. The resulting algorithms combine adaptive slot allocation with repeated reuse of remaining capacity while preserving feasibility and approximation guarantees.
- Slot construction: Each unlabelled node receives the label a′ ∈ {1, 2, 3} that maximizes D(ζ*) among the three partial construction maps.The procedure repeats until all nodes are labelled.
- Slot construction: Algorithm 5 creates the slot set Λ from the completed construction map, which Algorithm 3 then uses to compute service placement.Theorem 13 analyzes this placement when slot creation follows Algorithm 5.
- Guarantee: Theorem 13 guarantees total reward of at least (1 −e−1)δR for the placement computed with Algorithm 5 slot creation.The theorem states this guarantee for service placement Xψ computed by Algorithm 3.
- Combined allocation: CSA chooses between SA1 and SA2 using the minimum β satisfying maxi∈S si ≤β(minj∈V cj), selecting SA2 when β ≥ 1 or the displayed threshold condition holds, and SA1 otherwise.CSA is presented as a combined slot allocation algorithm with better empirical performance than SA1 and SA2 alone.
- Repeated allocation: RSA repeatedly runs CSA on remaining users and node capacity, adding newly placed services until the combined placement no longer changes.Because SA1 and SA2 guarantee feasibility, CSA and RSA also guarantee feasibility; repetition can only increase reward without worsening the approximation ratio.
B. Computational Complexity
The computational analysis identifies the LP as the bottleneck and derives the complexity of the proposed algorithms, while simulations compare RSA with optimal and baseline methods. The experiments report performance close to optimal and better than greedy and LP-rounding approaches.
- Complexity: The LP step is the bottleneck in SA1, SA2, and CSA, and RSA performs at most |U| CSA iterations.Each RSA call increases the number of served users by at least one.
- Complexity: The conversion from GSP to SPSC multiplies the number of users by |V| before solving the resulting SPSC instance with RSA.
- Baseline behavior: The greedy algorithm can have an arbitrarily bad approximation ratio in the heterogeneous setting.In the example, greedy obtains reward 2 while the optimum obtains reward n, so the ratio approaches zero as n grows.
- Simulation design: RSA simulations use Zipf-distributed service demands, heterogeneous service sizes and node capacities, platform dependencies, and reward variation.The evaluation compares RSA with an exponential-time optimum, greedy placement, and randomized LP rounding.
- Simulation results: Across parameter settings, RSA’s total reward and satisfied-user percentage perform close to optimal and better than the greedy and LP-rounding baselines.
- Comparison: The proposed method is deterministic and achieves an approximation ratio of at least (1 − e^-1)/4, improving on a randomized (1 − e^-1)/7.25 guarantee.
APPENDIX A PROOF OF THEOREM 1 (NP-HARDNESS)
NP-hardness is established by reducing decision Set Cover to SPSC and then observing that SPSC is a special case of GSP. The construction makes feasible service placements correspond to set covers.
- Reduction: The reduction starts from decision Set Cover, which asks whether at most c subsets cover the universe Z.
- Construction: The constructed SPSC instance uses one special service, services for the remaining sets, unit service sizes, unit node capacities, and unit user rewards.
- Forward direction: A set cover B yields a feasible SPSC placement in which the special service is placed on the nodes corresponding to B and all users are satisfied.
- Reverse direction: A feasible SPSC placement satisfying every user yields a set B of at most c nodes whose corresponding subsets cover Z.
- Conclusion: Therefore, SPSC is NP-hard, and GSP is NP-hard because SPSC is an instance of GSP.
- Supporting lemmas: The appendix also develops probability lemmas that lower-bound the chance of an event occurring across independent draws.
APPENDIX C PROOF OF THEOREM 9
The proof verifies feasibility for each possible node label by bounding the sizes of the services assigned to its resulting slots. The three label cases cover one-slot, two-slot, and bounded-size multi-slot constructions.
- Feasibility cases: For label 1, the node receives one slot whose service belongs to the class of services fitting within the node capacity.
- Feasibility cases: For label 2, two slots are created, each service has size at most half the node capacity, and their total size therefore fits.
- Feasibility cases: For label 3, feasibility follows from Theorem 4 after restricting services to those whose sizes are at most β times the node capacity.
APPENDIX D PROOF OF THEOREM 10
The proof bounds service-placement probabilities and combines these bounds to establish a lower bound on expected total reward. It then invokes Theorem 3 to conclude the result.
- Expected reward: With δ = β = 1/4, the resulting expected-reward expression incorporates services satisfying si > βcj before Theorem 3 supplies the final conclusion.The proof explicitly states that Theorem 3 gives the result.
- Case analysis: The proof treats five cases according to service size and the node’s associated service category.The cases include si > cj, Ωj,⊕, Ωj,⊖ with different values of ∆j,⊖, and Ωj,q for q ∈N.
- Case analysis: For nodes in Ωj,q, the probability bound uses at least ηj,q relevant slots and Lemma 4 to lower-bound the chance that one contains service i.The argument conditions on ζ(j) = 3 and combines the slot bound with Theorems 15 and 16.
- Placement-probability bound: For every service i and node j, the placement probability is bounded below by δ(1 −e−ωi,j).The proof handles cases based on service size and node categories, using slot probabilities and Lemma 4 where needed.
- Expected reward: The proof bounds the probability that a user is served through a node in Wk and obtains a lower bound δ(1−e−αk), further bounded by δαk(1−e−1) when αk ≤1.This bound is used to derive an expected total reward lower bound.
APPENDIX E PROOF OF THEOREM 11
The proof maintains an inductive hypothesis while progressively fixing node-related choices. Partitioning the remaining construction maps preserves the required expectation bound throughout the algorithm.
- Initialization: Initially, ζ′(j) = ∅ for every node, so Yτ′ contains all possible construction maps and the inductive hypothesis holds.The corresponding expectation is identified with D(ζ′).
- Inductive step: At each step, the sets Yζ∗ a for a ∈ {1, 2, 3} partition Yζ′, allowing the expectation to be bounded through the inductive hypothesis.The proof uses this partition to select the next assignment while preserving the bound.
- Conclusion: The inductive hypothesis therefore holds throughout the algorithm, which proves the stated result.The proof concludes by applying the preserved invariant.
APPENDIX F PROOF OF THEOREM 14
The proof analyzes Algorithm 6’s probability calculations for service-node events and user coverage. It establishes that the algorithm computes the required quantities correctly, while contrasting the result with prior randomized work.
- Event definitions: For each service i and node j, Ei,j denotes the event that some slot places service i on node j.This event is used to express service placement probabilities.
- Probability computation: Algorithm 6 computes conditional probabilities for node states and combines them using the law of total probability.The proof distinguishes fixed states ζ∗(j) from the unfixed state ζ∗(j) = ∅.
- User coverage: For each user k, fτ,k = 1 exactly when some node j ∈Wk realizes the corresponding coverage event, enabling computation of θ′k.The argument derives this relationship from Lemma 1 and the preceding event probabilities.
- Relation to prior work: In the GSP case, prior randomized work has approximation ratio (1 −e−1)/7.25 in expectation, and the paper states that it improves on this result.The comparison uses K := 1 and an optimally tuned parameter α from the cited prior algorithm.