Dynamic resource location with tropical algebra

The traditional dynamic resource location problem attempts to minimize the cost of servicing a number of sequential requests, given foreknowledge of a limited number of requests. This paper presents an algebraic framework for addressing this question in general, and relates he algebraic properties of a generating set to questions in long-term optimizability, addressing the two questions: for a given graph, is there a finite quantity of future knowledge with which a server’s relocation scheme can be completely optimized, and if not, then how does the performance of a non-omniscient optimization scheme improve as the quantity of future knowledge increases?