Ubiquitous Wireless Power Transfer for Multiple Mobile Devices - Souza, Alexander Decker de; Vieira, Luiz Filipe Menezes; Vieira, Marcos Augusto Menezes (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2021: Anais do XXXIV Concurso de Teses e DissertaçõesDO - 10.5753/ctd.2021.15764, 2021)
We propose two new computational problems associated with the charging of mobile devices using wireless power transfer via magnetic induction. Algorithms for these problems may enable ubiquitous charging, meaning the user is no longer required to be aware of the devices charging processes. We prove both problems as being NP-Hard and propose three dynamic programming algorithms to solve them in linear time regarding the size of the time horizon. We also propose three greedy algorithms for the problems. Experiments indicate that the best dynamic-programming algorithm among those proposed reaches between 89% and 97% of effectiveness, while the best greedy reaches between 74% and 92%, depending on the considered scenario.