Edge Computing (EC) represents the most promising solution to the real-time or near-real-time processing needs of the data generated by Internet of Things devices. The emergence of Edge Infrastructure Providers (EIPs) will bring the EC benefits to those enterprises that cannot afford to purchase, deploy, and manage their own edge infrastructures. The main goal of EIPs will be that of max-imizing their profit, i.e. the difference of the revenues they make to host applications, and the cost they incur to run the infrastructure plus the penalty they have to pay when QoS requirements of hosted applications are not met. To maximize profit, an EIP must strike a balance between the above two factors. In this paper we present the Online Profit Maximization (OPM) algorithm, an approximation algorithm that aims at increasing the profit of an EIP without a priori knowledge. We assess the performance of OPM by simulating its behavior for a variety of realistic scenarios, in which data are generated by a population of moving users, and by comparing the results it yields against those attained by an oracle (i.e., an unrealistic algorithm able to always make optimal decisions) and by a state-of-the-art alternative. Our results indicate that OPM is able to achieve results that are always within 1% of the optimal ones, and that always outperforms the alternative solution.