13 citations · 30 across the 18 of their papers we have counts for
6 papers · 1 filter
Station Assignment with Reallocation
Austin Halper, Miguel A. Mosteiro, Yulia Rossikova +1
We study a dynamic allocation problem that arises in various scenarios where mobile clients joining and leaving the system have to communicate with static stations via radio transm…
Graph Ranking and the Cost of Sybil Defense
Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Ann Goldberg +5
Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, s…
Dynamic Windows Scheduling with Reallocation
Martin Farach-Colton, Katia Leal, Miguel A. Mosteiro +1
We consider the Windows Scheduling problem. The problem is a restricted version of Unit-Fractions Bin Packing, and it is also called Inventory Replenishment in the context of Suppl…
Power-efficient Assignment of Virtual Machines to Physical Machines
Jordi Arjona Aroca, Antonio Fernandez Anta, Miguel A. Mosteiro +2
Motivated by current trends in cloud computing, we study a version of the generalized assignment problem where a set of virtual processors has to be implemented by a set of identic…
Opportunistic Information Dissemination in Mobile Ad-hoc Networks: adaptiveness vs. obliviousness and randomization vs. determinism
Martin Farach-Colton, Antonio Fernandez Anta, Alessia Milani +2
In this paper the problem of information dissemination in Mobile Ad-hoc Networks (MANET) is studied. The problem is to disseminate a piece of information, initially held by a disti…
Insertion Sort is O(n log n)
Michael A. Bender, Martin Farach-Colton, Miguel Mosteiro
Traditional Insertion Sort runs in O(n^2) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accele…