The minimum backlog problem
2015 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 605, 51-61 p.Article in journal (Refereed) PublishedText
We study the minimum backlog problem (MBP). This online problem arises, e.g., in the context of sensor networks. We focus on two main variants of MBP. The discrete MBP is a 2-person game played on a graph G = (V, E). The player is initially located at a vertex of the graph. In each time step, the adversary pours a total of one unit of water into cups that are located on the vertices of the graph, arbitrarily distributing the water among the cups. The player then moves from her current vertex to an adjacent vertex and empties the cup at that vertex. The players objective is to minimize the backlog, i.e., the maximum amount of water in any cup at any time. The geometric MBP is a continuous-time version of the MBP: the cups are points in the two-dimensional plane, the adversary pours water continuously at a constant rate, and the player moves in the plane with unit speed. Again, the players objective is to minimize the backlog. We show that the competitive ratio of any algorithm for the MBP has a lower bound of Omega (D), where D is the diameter of the graph (for the discrete MBP) or the diameter of the point set (for the geometric MBP). Therefore we focus on determining a strategy for the player that guarantees a uniform upper bound on the absolute value of the backlog. For the absolute value of the backlog there is a trivial lower bound of Omega (D), and the deamortization analysis of Dietz and Sleator gives an upper bound of O (D log N) for N cups. Our main result is a tight upper bound for the geometric MBP: we show that there is a strategy for the player that guarantees a backlog of O(D), independently of the number of cups. We also study a localized version of the discrete MBP: the adversary has a location within the graph and must act locally (filling cups) with respect to his position, just as the player acts locally (emptying cups) with respect to her position. We prove that deciding the value of this game is PSPACE-hard. (C) 2015 Elsevier B.V. All rights reserved.
Place, publisher, year, edition, pages
ELSEVIER SCIENCE BV , 2015. Vol. 605, 51-61 p.
Online algorithms; Competitive analysis; Computational geometry; Games on graphs
IdentifiersURN: urn:nbn:se:liu:diva-123524DOI: 10.1016/j.tcs.2015.08.027ISI: 000365059800004OAI: oai:DiVA.org:liu-123524DiVA: diva2:886260
Funding Agencies|NSF [CCF-0621439/0621425, CCF-0540897/05414009, CCF-0634793/0632838, CNS-0627645, CCF 1114809, CCF 1217708, IIS 1247726, IIS 1251137, CNS 1408695, CCF 1439084, CCR-0329910, CCF-0528209, ACI-0328930, CCF-0431030, CCF-1018388, CCF-1540890]; DFG [FE407/9-1, FE407/9-2]; Department of Commerce [TOP 39-60-04003]; Department of Energy [DE-FC26-06NT42853]; Wright Center for Sensor Systems Engineering; U.S.-Israel Binational Science Foundation [2000160, 2010074]; NASA [NAG2-1620]; Metron Aviation; Academy of Finland [116547, 118653]; Helsinki Graduate School in Computer Science and Engineering (Hecse)2015-12-222015-12-212015-12-22