%ABahreini, Tayebeh%AGrosu, Daniel%Anull Ed.%BJournal Name: IEEE Transactions on Cloud Computing %D2020%I %JJournal Name: IEEE Transactions on Cloud Computing %K %MOSTI ID: 10288201 %PMedium: X %TEfficient Algorithms for Multi-Component Application Placement in Mobile Edge Computing %XIn this paper, we address the Multi-Component Application Placement Problem (MCAPP) in Mobile Edge Computing (MEC) systems. We formulate this problem as a Mixed Integer Non-Linear Program (MINLP) with the objective of minimizing the total cost of running the applications. In our formulation, we take into account two important and challenging characteristics of MEC systems, the mobility of users and the network capabilities. We analyze the complexity of MCAPP and prove that it is NP-hard, that is, finding the optimal solution in reasonable amount of time is infeasible. We design two algorithms, one based on matching and local search and one based on a greedy approach, and evaluate their performance by conducting an extensive experimental analysis driven by two types of user mobility models, real-life mobility traces and random-walk. The results show that the proposed algorithms obtain near-optimal solutions and require small execution times for reasonably large problem instances. %0Journal Article