## 1 Introduction
### Our Results  
The overarching goal of this line of research is to formulate efficient query schemes that, for all possible collections of moving entities, maintain fixed bounds on congestion potential measures continuously (i.e., at all times). Naturally, for many such collections, the required query frequency changes over time as entities cluster and spread, so efficient query schemes need to adapt to changes in the configuration of entities. While such changes are continuous and bounded in rate, they are only discernible through queries to individual entities, so entity configurations are _never_ known precisely; future configurations are of course entirely hidden. In this latter respect, our schemes and the competitive analysis of their efficiency using as a benchmark a _clairvoyant scheme_ that bases its queries on full knowledge of all entity trajectories (and hence, all future configurations), resembles familiar scenarios that arise in the design and analysis of on-line algorithms.  
Our goal in this paper is to show how to optimize query frequency to guarantee low congestion potential at one fixed target time, say time \(\tau>0\) in the future, starting from a state of complete uncertainty of entity locations. In a companion paper [3] we turn our attention to the optimization of query frequency to guarantee low congestion potential continuously. Motivation for restricting attention to a fixed target time comes in part from the desire to prepare for a computation, at some known time in the future, whose efficiency depends on this low congestion potential (see [2; 13] for examples). As we will see in Section 4, a modification of our fixed-target schemes also plays an important role in the efficient initialization of query schemes that optimize queries to guarantee low congestion potential continuously, from some point in time onward Our fixed-target schemes also provide an informative contrast to continuous optimization schemes, highlighting the unavoidable extra cost of maintaining low congestion continuously.  
We begin by describing a query scheme to achieve uncertainty ply at most \(x\) at one fixed target time in the future, reminiscent of the objective in [1]. The detailed description and analysis of our fixed target time scheme shows that uncertainty ply at most \(x\) can be achieved using query granularity that is at most a factor \(\Theta(x)\) smaller than that used by any, even clairvoyant, query scheme to achieve the same goal. A similar, but more intricate scheme and analysis establishes the same result for uncertainty degree. An example shows that the competitive factor for both congestion potential measures is asymptotically optimal in the worst case. Nevertheless, if we relax our objective, allowing instead uncertainty degree at most \(x~{}+~{}\Delta\), where \(1\leq\Delta\leq x\), the competitive factor \(\Theta(x)\) drops to \(\Theta(\frac{x}{1+\Delta})\). Again, this competitive factor is shown to be asymptotically optimal in the worst case. This analysis of a query scheme that solves a slightly relaxed optimization, relative to a clairvoyant scheme that solves the un-relaxed optimization, foreshadows similar analyses of our schemes for continuous-time query optimization [14].  
In the concluding discussion, we describe modifications to our model that make our query optimization framework even more broadly applicable.