Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Zheng, Da Wei
Master of Science - MSc
University of British Columbia
Let e1, e2, . . . , en be a set of entities moving with bounded speed in d-dimensional space. At each time step, we can choose one entity to query to obtain its actual location. Our goal is to establish via these queries that many of the entities could not be at a fixed point called a beacon. By failing to query an entity, the set of its potential locations, called its uncertainty region, grows over time. We want to query to keep the number of uncertainty regions that do not overlap the beacon (i.e., the number of entities away from the beacon) as large as possible. Of course, if many entities are near the beacon, we cannot avoid high overlap, but neither can any query schedule. We describe query schedules that establish that the number of entities away from the beacon is a constant fraction of the maximum number that can be shown to be away from the beacon in the case where each entity is static that is, every query reveals that the entity has not moved. In the general setting we show additive upper and lower bounds on what can be attained by a query schedule.
Scheduling Queries to Moving Entities to Certify Many AreDistant From a RegionbyDa Wei ZhengB.Sc. University of British Columbia, 2018A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THEDEGREE OFMASTER OF SCIENCEinTHE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)The University of British Columbia(Vancouver)August 2020c© Da Wei Zheng, 2020The following individuals certify that they have read, and recommend to the Faculty of Graduate andPostdoctoral Studies for acceptance, the thesis entitled:Scheduling Queries to Moving Entities to Certify Many Are Distant From a Regionsubmitted by Da Wei Zheng in partial fulfillment of the requirements for the degree of Master of Sciencein Computer Science.Examining Committee:Will Evans, Professor, Computer Science, UBCSupervisorDavid Kirkpatrick, Professor Emeritus, Computer Science, UBCSupervisory Committee MemberiiAbstractLet e1, e2, . . . , en be a set of entities moving with bounded speed in Rd. At each time step, we can chooseone entity to query to obtain its actual location. Our goal is to establish via these queries that many ofthe entities could not be at a fixed point in Rd called a beacon. By failing to query an entity, the set of itspotential locations, called its uncertainty region, grows over time. We want to query to keep the number ofuncertainty regions that do not overlap the beacon (i.e., the number of entities away from the beacon) aslarge as possible. Of course, if many entities are near the beacon, we cannot avoid high overlap, but neithercan any query schedule. We describe query schedules that establish that the number of entities away fromthe beacon is a constant fraction of the maximum number that can be shown to be away from the beacon inthe case where each entity is static that is, every query reveals that the entity has not moved. In the generalsetting we show additive upper and lower bounds on what can be attained by a query schedule.iiiLay SummaryConsider a radio network where there is a tower with a fixed signal range. There are a number of movingtransceivers with bounded speeds that communicate with the radio tower. We want to know how manytransceivers are within range of its signal. The radio tower can send queries to gain information on thelocation of the transceiver, but can only send one query every so often. The possible position of each non-queried transceiver lies in a region, which we will call its uncertainty region, that the entity could reach fromits last known position while obeying some maximum speed limit. In this thesis, we will explore the waysto query that maximizes the number of uncertainty regions of the transceivers that are entirely within therange of the radio tower, as these uncertainty regions correspond to the transceivers we can ascertain arewithin range of the tower.ivPrefaceThis dissertation is original, unpublished, work by the author, Da Wei Zheng.vContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vContents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Formal Model and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Competitive Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.4 Variations of the Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.5 Continuous Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.7 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Static Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Notation for the Static Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Fixed Time Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Related Work in Pinwheel Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3.1 Hardness of Pinwheel Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3.2 Variations of Pinwheel Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.4 Overview of the Minimum Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.5 Optimal k-schedules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.5.1 Examples of Optimal Schedules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.6 Round-Robin Schedules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.7 Approximation Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.7.1 Round-Robin Approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Dynamic Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.1 Dynamic Trajectory Plots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2 Upper Bounds by Adversarial Trajectories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2.1 Fixed Time Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.3 Minimum Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.3.1 An Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.3.2 Promise Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20vi3.4 Average Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.4.1 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.4.2 Performance of Round-Robin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.1 Conclusion of the Static Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.2 Conclusion of the Dynamic Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30viiList of Tables2.1 Performance of Theorem 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1 Dynamic bounds proved . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.2 Table of actual and upper bound gaps for performance under the minimum objective. . . . . 21viiiList of Figures3.1 Dynamic trajectory plots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2 Dynamic trajectory plot for fixed time objective . . . . . . . . . . . . . . . . . . . . . . . . . 173.3 Dynamic trajectory plot for minimum objective . . . . . . . . . . . . . . . . . . . . . . . . . . 183.4 Dynamic trajectory plot for promise setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.5 Dynamic trajectory plot with all entities at beacon . . . . . . . . . . . . . . . . . . . . . . . . 223.6 Dynamic trajectory plot for round-robin query strategy . . . . . . . . . . . . . . . . . . . . . 233.7 Trajectories for Lemma 22 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24ixChapter 1IntroductionConsider a radio network where there is a tower that has a signal range of r kilometers. There are a numberof moving transceivers with bounded speeds that communicate with the radio tower. It may be useful toknow how many transceivers are within range of its signal. Perhaps the radio tower can send queries to gaininformation on the distance of the transceivers from the tower, but can only send one query every so often.The possible position of each non-queried transceiver lies in a region, which we will call its uncertainty region,that the entity could reach from its last known position while obeying some maximum speed limit. We wantto find the optimal way to query that maximizes the number of uncertainty regions of the transceivers thatare entirely within the range of the radio tower, as these uncertainty regions correspond to the transcieverswe can ascertain are within range of the tower.Each transceiver is a moving entity. The radio tower is only capable of knowing the exact position ofan entity by querying it, and it is allowed one query per time step. In this thesis, we aim to devise querystrategies that maximize the number uncertainty regions away from a region with rate-limited queries. Inour example with the radio network, the region was all space farther than r kilometers from the radio tower.Ultimately, the exact positions of the entities from the region matter insofar as it determines the distanceof the entities from the region. Throughout the thesis, we will instead analyze the equivalent problem ofkeeping uncertainty regions away from a single point which we shall call the beacon.We will formally describe this model and the explore different methods that we use to evaluate theperformance of algorithms under this model.1.1 Formal Model and NotationLet E be a set {e1, e2, ..., en} of n point entities in Rd. Let T = {p1, p2, . . . , pn} be the set of unknowntrajectories of these entities where pi(t) is the distance of ei from the beacon at time t ∈ N. Assume weknow the starting distance ai ≡ pi(0) that entity ei is from the beacon at time 0 for all entities. We assumethat all entities have a speed bound of 1. We do not lose any generality with this assumption, as we canscale the perceived distance of the object by the speed bound to treat the entity as one that has a speed of 1.The speed constraint is in fact a smoothness constraint on the trajectories pi; it is equivalent to pi being 1-Lipschitz. If we query entity ei at time t′, we find it at distance pi(t′) from the beacon. The speed constraintimplies that at a later time t > t′, ei must be within distance t − t′ of pi(t′). If t′ was the last query to eiprior to time t, then the entity’s position at time t lies in the range [min{pi(t′)− (t− t′), 0}, pi(t′) + (t− t′)]which is the uncertainty region for ei at time t.We will have satisfactorily kept the uncertainty region of ei away from the beacon at time t if the entitycannot be distance 0 from the beacon, that is if pi(t′)− (t− t′) > 0. If this is the case, we say that entity ei issatisfied at time t. Our goal is to devise query strategies that maximize the number of satisfied entities, withthe limitation that we are allowed only one query per unit time. We will consider maximizing the number1of satisfied entities at a particular target time as well as maximizing the average and the minimum numberof satisfied entities over all time.At first, in Chapter 2, we consider entities that never move. Every query to an entity reveals that its newposition is exactly the same as it was before. In this static setting, query strategies must still query entitiesin order to satisfy them (i.e., keep their uncertainty region away from the beacon) but the trajectories donot change over time. We consider the dynamic setting, where trajectories can vary over time, in Chapter 3.1.2 Competitive AnalysisFor some trajectories T there does not exist any query strategy Q that performs well. If all n entitiesstay very close to the beacon, overlap of the beacon by many regions is unavoidable for any query strategy.Instead, we will use competitive analysis to try and perform well against the optimal offline algorithm. Wewill aim to find a query strategy that performs well as compared to the best possible query strategy for T ,which we will denote as QT . This query strategy can be thought of as clairvoyant or incredibly lucky, as itcan use the trajectories of the entities to decide what entity to query.1.3 Performance EvaluationWe desire a schedule that keeps regions away from the beacon, but there needs to be a way to quantify howgood a schedule is. We will discuss three different measures: the fixed time measure, the average measure,and the minimum measure. It will help to define the following set for a query strategy Q:A(T , Q, t) = {ei | entity ei has an uncertainty region that does not overlap the beacon at time twhen querying according to Q on trajectories T }.This set is a function of the query strategy and trajectory. We will try and seek good query strategies forall trajectories, so we will focus on worst case trajectories T .Fixed time objective Suppose a specific time t is specified in which we want to minimize the overlap.We can evaluate this by considering the quantity |A(T , Q, t)|.Minimum objective We are also interested in the minimum number of satisfied entities over time. If werestrict ourselves to a finite window of time between 0 and L, for the worst case trajectory T , the minimumcould be made to occur at time L. This would be no different from simply evaluating the fixed time measureat time L. To distinguish this measure from the fixed time measure, we will take the minimum over all time.We can denote this as Mmin and formally define it as follows.Mmin(T , Q) = mint∈N|A(T , Q, t)|Average objective We can also consider the average number of regions that are kept away from thebeacon over all time. When we look at a finite window between time 0 and L, we are subject to boundaryeffects. To overcome these effects, we can take a limit as L goes to infinity. We denote this measure as Mavgand formally define it as follows.Mavg(T , Q) = limL→∞1LL∑t=1|A(T , Q, t)|21.4 Variations of the ModelFundamentally this model is a one dimensional problem about the time it takes uncertainty regions tooverlap the beacon after they are queried. Thus the model easily generalizes to different speeds of entities,arbitrary dimensional metric spaces, and multiple beacons as well. Different speeds simply scale the time,after a query, when the uncertainty region overlaps the beacon. To represent this in the unit-speed model,we normalize the distance that an entity appears by its speed. The geometry of the underlying space is onlyused to determine the distance to the beacon, which in turn determines the time before regions overlap thebeacon. Multiple beacons, or even beacons that are not single points but subsets of our underlying spacealso work under the model by considering the earliest instance in which regions overlap the beacon.We can generalize the shape and behaviours of the uncertainty regions of each entity as well. Theuncertainty regions could be arbitrary closed regions. The only two necessary properties we need for thismodel are the ability to compute the distance of the uncertainty region to the beacon as a function of time,and a smoothness condition on how this function behaves.1.5 Continuous SensingBeyond systems that are limited by the time it takes to perform a query on moving entities, systems are alsolimited by the computational power at their disposal. Such a system may have access to powerful sensorsthat can gather information about the entirety of its surroundings, but data from the sensors need to beprocessed in order to be be used, and this processing requires computational time. If there isn’t enoughcomputational power to process all the data, only a limited subset of the processed raw data can be used tomake decisions before newer data comes in. One example of such a device is an automated crash preventionsystems equipped to a vehicle that will give drivers warning if other entities on the road get too close.Automated vehicles take this a step farther and use information from these sensors to decide in real timewhat course of action to take. If there’s more sensor data that can be feasibly analyzed in real time by thecomputers on board, this leads to the same question of effectively using their computational power to keepuncertainty of nearby entities away from the vehicle.1.6 Related WorkThis model is similar to the one studied by Evans et al. [1] and expanded on by Busto, Evans and Kirkpatrick[2]. In their model they have the same type of rate limited query that can be used to obtain the true locationof entities that move with bounded speed. However they are concerned with minimizing more global measuresof uncertainty regions such as the ply or maximum degree of the associated intersection graph. They alsoconsider constant factor approximations to minimizing the clique number and chromatic number of theintersection graph. In our model, it is a more local setting of a single predetermined point we wish toprotect. If we consider the intersection graph of the uncertainty regions and our beacon, we wish to keepthe degree of the vertex corresponding to the beacon small.In the work of Busto, Evans and Kirkpatrick [2], they use results from assuming static trajectories ofthe entities to motivate a quantity called the x-radius that is essential to determine how large uncertaintyregions are allowed to get before a query is needed. In the single beacon model, this step is not necessary, asthe distance of entities from the beacon is the only quantity needed to determine when a query is needed.Each entity can almost be treated independently, if not for the shared limit of one query per unit time.31.7 OverviewIn Chapter 2, we will consider the problem in the static setting. This problem also has many connections toother scheduling problems and other rate limited query problems like pinwheel scheduling.In Chapter 3, we analyze how large the gap in performance is between a deterministic algorithm whenfaced with an adversarial set of trajectories and an optimal query strategy that knows the trajectory. Forany query strategy Q, there exists a set of trajectories T and a strategy QT that keeps all entities satisfied,while Q can only satisfy a constant fraction less than one of the entities. There are also trajectories whereQ can’t keep any entity satisfied, while QT can satisfy a constant fraction of the entities.4Chapter 2Static SettingThe complexity of devising a good query strategy when entities are static is greatly reduced because we don’tneed to consider trajectories that change over time. We can expect the entities to be exactly where we lastqueried them, and thus we can focus on the scheduling aspect of the problem. This makes finding an optimalschedule for the fixed time objective described in Section 1.3 straightforward as discussed in Section 2.2.We start by introducing a related problem called pinwheel scheduling that we describe in Section 2.3. Theaverage objective has been studied in existing literature, and we discuss that in Section 2.3.2 in the contextof other related work. The remaining bulk of this chapter is devoted to considering the minimum objectivewhere we provide upper bounds on what an optimal schedule can achieve in Section 2.5, explore what optimalschedules look like in Section 2.5.1 and provide algorithms for generating query strategies in Section 2.7 and2.7.1.2.1 Notation for the Static SettingIn the static setting, the problem input is the multiset A = {a1, a2, . . . , an} of distances of the n entities e1,e2, . . . , en, from the beacon. We can assume that ai is an integer since queries can only be performed atunit times. If an entity is satisfied at time t, then this means that there was at least one query to ei in thetime interval (t− ai, t].Let S be an infinite sequence {Sj : j ∈ N} over the alphabet of symbols [n] = {1, 2, . . . , n}. On aninstance A, we say that S is a k-schedule if for all time it can keep k entities satisfied. Formally if S is ak-schedule, then at any time t, there is a set of entities E ⊆ E of size k such that for all ei ∈ E, there is atleast one query to ei between time t−ai and t. If this is the case, we say that the instance A is k-schedulable.With this notation, our primary goal in the static setting for the minimum objective is simple to state.We wish to find the maximum value of k such that a given instance A is k-schedulable.2.2 Fixed Time ObjectiveWhen we fix a time t and wish to maximize the number of satisfied entities at that time, we simply need toconsider the latest queries to each of entities. Let ti be the latest query to entity ei before or at time t. Theentity ei is satisfied if ti ≥ t− ai. Thus we have the following scheduling problem: what is the largest subsetof entities such that we can assign unique integer times to ti where t− ai ≤ ti ≤ t.This question we can solve optimally by sorting the distances ai in non-decreasing order and using agreedy scheduling procedure. We allocate the latest available query time to ei if that time is within range,otherwise we give up on querying ei.52.3 Related Work in Pinwheel SchedulingWhen we wish to keep all regions away from the beacon for all time, this problem is equivalent to a problemcalled pinwheel scheduling [3]. In the pinwheel problem, we are given a multiset A = {a1, a2, . . . , an} wherethe goal is to find an infinite symbol sequence S = {Sj : j ∈ Z} over [n] = {1, 2, . . . , n} such that everysubsequence of ai consecutive entries contains at least one i or deem it is impossible. This is equivalent tosaying that all entities are satisfied at all times. Holte et al. showed [3] Theorem 2.1 that these infinitesequences that are solutions to the pinwheel problem are periodic. These infinite periodic schedules can bewritten concisely as an ordering of its distances. For example, (1, 3, 1, 4, 2, 5) which denotes the schedule Swhere S6h+1 = 1, S5h+2 = 3, S6h+2 = 1, . . . , S5h+4 = 5. Alternatively the schedule can be expressed as thefollowing infinite sequence of queries.1, 3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5, 1, 3, 1, 4, 2, 5, . . . .One particularly interesting measure of an instance A is its density defined to be d(A) =∑i1ai. Afundamental fact about such instances is that d(A) ≤ 1 is a necessary condition for pinwheel schedulability[3], or else the frequency demanded by the entities would make the instance impossible to pinwheel schedule.This sparked a series of papers trying to find how small the density of an instance must be to guaranteethe existence of a pinwheel schedule. Holte et al. [3] showed that d(A) ≤ 0.5 is enough for an instance tobe schedulable. This was later improved to d(A) ≤ 0.7 by Chan and Chin [4], and then to d(A) ≤ 0.75 byFishburn and Lagarias [5].2.3.1 Hardness of Pinwheel SchedulingThe hardness of pinwheel scheduling is also of interest to researchers. The pinwheel scheduling problemis known to be in PSPACE, and the work of Jacobs and Longo [6] show that if there existed a pseudo-polynomial time algorithm then SAT can be solved by a randomized algorithm with expected runtime ofnO(logn log logn).The hardness of pinwheel scheduling means that even if there exists some schedule for the static versionof the beacon problem that satisfied k = n, it may not be easy to find in polynomial time, and may noteven have a polynomial period length. It is not known whether it is possible to find succinct versions of theschedule. We frame our problem as a maximization problem; we wish to find the maximum k such that aninstance has a k-schedule and focus on creating efficient approximation algorithms.2.3.2 Variations of Pinwheel SchedulingHere we will highlight the difference between a k-schedule and a pinwheel schedule for k < n. A scheduleS is a pinwheel schedule if for all times t and for all n entities ei, the entity is satisfied at time t, meaningt < ai or there exists a query to ei within the time interval (t − ai, t]. However for a k-schedule, we onlyneed this constraint to hold for k of the entities.Surprisingly, while other alternate forms of pinwheel scheduling have been studied [7, 8, 9], we wereunable to find any papers on this exact variant. The most similar work to finding a good k-schedule isrelated to recharging bandits by Kleinberg and Immorlica [9]. In their work, they show that there exists aPTAS for multi-armed bandit problems where the expected payout of an arm is a concave increasing functionof the last play of that arm. Their work gives a (1−ε)-approximation on the maximum payoff. This payoff isexactly the amount of time that an entity is satisfied; maximizing the payoff is equivalent to maximizing thetotal or average number of satisfied entities over time, and is equivalent to our average objective describedin Section 1.3. Their results do not generalize to maximizing k as their methods may schedule entities insuch a way that there are fewer than k satisfied at a single point in time, even though they perform well onaverage.62.4 Overview of the Minimum ObjectiveWe begin by investigating what an optimal schedule S looks like if it were a k-schedule on A. Here weprove a density bound on the farthest k entities, analogous to the density bound for pinwheel schedules. Areasonable conjecture is that k-schedules reduce to pinwheel schedules on the farthest k entities, but we finda general family of instances that are counterexamples to this conjecture. In the next section, motivatedby the simple round-robin structure of the optimal schedules on these instances, we further investigate howto find optimal round-robin schedules for general instances. In our final section, we consider approximationalgorithms to finding the best k-schedule, and use our optimal round-robin schedules as a key tool to get a34 -approximation and an even better approximations as well.2.5 Optimal k-schedulesWhen faced with numerous static entities, some near the beacon and some far away from the beacon, it isnatural to imagine that a k-schedule S will primarily focus on the k entities that are farthest away from theentities. Theorem 1, that we will later prove, captures this intuition.Theorem 1. If there exists a k-schedule S of A, then the density of the k farthest entities is at most 1.Since a k-schedule implies the k farthest entities have density at most one, it might seem appropriate toonly query these entities. This leads to the quite natural conjecture that if there exists a k-schedule S, thenthere exists a k-schedule S′ that only schedules the k farthest entities, i.e., a pinwheel schedule on those kfarthest entities.However, we will disprove this very natural-seeming conjecture by a counterexample in Example 3.Furthermore we extend this to Corollary 4 which shows that there exists a general family of instances wherethere exists a k-schedule but no pinwheel schedule on the k farthest entities. For these examples, a specificround-robin algorithm is used, motivating Theorem 6 in the next section.To prove Theorem 1, we need to know more about the structure of k-schedules. The possible periodicityof k-schedules follows almost directly from the proof of Theorem 2.1 in [3], meaning it suffices to restrict ourattention to periodic schedules. We describe this as Lemma 2.Lemma 2. If there exists a k-schedule S on an instance A, there exists a periodic k-schedule with period atmost∏ni=1(ai + 1).Proof of Lemma 2. At every time t we can represent the state of the system as a vector vt ∈ Rn≥0 of timesuntil each entity overlaps the origin. We let vt(i) = 0 denote that entity ei currently has an uncertaintyregion that overlaps the beacon and vt(i) = ai if ei is queried at time t. Note that 0 < vt(i) ≤ ai andfurthermore is an integer as uncertainty regions expand at unit rates and ai is an integer. Note also that Sis a k-schedule if the state vector vt at every time t is non-zero in at least k positions, and vt depends onlyon vt−1 and St.There are only∏ni=1(ai + 1) possible values for vt. Since there are a finite number of possible statevectors, any schedule must repeat a state vector. If A is k-schedulable, then any S must have vt0 = vt0+c forsome time t0 and some period c ≤∏ni=1(ai+1). If S is a k-schedule, repeating the schedule (St0 , . . . , St0+c−1)will yield a k-schedule with period c, since each associated state vector came from a k-schedule.We now can use the periodic nature of these schedules to prove an upper bound on the density ofthe farthest away entities by proving the desired bound for a packing problem that is a relaxation of ourscheduling problem.Proof of Theorem 1. Let’s order the entities E = {e1, e2, · · · en} in decreasing order so a1 ≥ a2 ≥ · · · ≥ an.Suppose we had a k-schedule S. By Lemma 2 we may assume that S is periodic with period c ∈ N. Let nidenote the number of times that entity ei is queried in c consecutive time steps of S. Note that this means7that∑ni=1 ni = c as there are c queries in every c time units. In every c time units, entity ei can be satisfiedat most min{c, niai} units of time. Since S is a k-schedule we must have at least k entities satisfied. Thismeans that the following must hold.n∑i=1min{c, niai} ≥ kcConsider if we remove the scheduling aspect of the problem and instead view maximizing the left handside as a packing problem, where we need to pick how much weight xi we wish to take of entity ei if everyunit of xi gives us ai in value subject to the constraint that the total weight is at most c. Consider thegreedy approach to maximizing this sum: repeatedly take the largest value aj and set xj = caj until we havetaken a total of k values. A simple swapping argument gives us that this procedure cannot end up with lessvalue than S which is restricted by the integrality of ni. However, in order to get a value of at least kc,we must have taken as much of a1, a2, . . . , ak as possible as they are the largest weight entities. Hence weconclude thatk∑i=1xi =k∑i=1cai≤ c.Dividing the above inequality by c yields our desired bound on density.2.5.1 Examples of Optimal SchedulesThe result in the previous section suggests that the best any algorithm can do is equal to the maximumnumber of entities whose density sums to 1. It may appear that the optimal way to schedule entities wouldbe to ignore the closest entities and run a pinwheel schedule on the rest. The following example shows thatwhen n ≥ k we may not be able to find a pinwheel schedule on the farthest k entities but we would be ableto find a k-schedule.Example 3. There exist instances that are 4-schedulable but the furthest 4 entities cannot be pinwheelscheduled.Proof. We will consider the instance A = {a1 = 5, a2 = 5, a3 = 4, a4 = 3, a5 = 3}, and show there is nopinwheel schedule of A′ = {a1, a2, a3, a4} but there is a k-schedule of A.First we’ll show that there is no pinwheel schedule of A′. Consider the entity e4. If we have a pinwheelschedule of A′, each query to e4 must be within a4 = 3 of another. Since a3 = 4, suppose there exists aquery to e3 between every two consecutive queries to e4. Our schedule may look something like the following,where _ denotes another as of yet unspecified query.. . . , 4, 3,_, 4,_, 3, 4, 3,_, 4, 3,_, 4, 3 . . .This means that the each query to e4 must occur in the schedule exactly 1/3 of the time if we look ateach window of size 3 starting from a query to e4. However, we still need to schedule e1 and e2 at least 15 ofthe time, but13+13+15+15=1615> 1.We can’t schedule something that occurs with density larger than 1, so therefore this can’t happen. Now weknow that if there exists a pinwheel schedule there must be two consecutive queries to e4 that don’t have aquery to e3 in between. Now let’s consider the window of five that starts at the first query of e3 right beforethis pair of e4 queries. It may look like the following:. . . , 3, 4,_, 4, 3, . . . .In this window, there must be two queries to e4 and another query of e3. However this is a windowof size 5 with two e3 and two e4 queries, so we can only query one of e1 or e2 in this window. Hence it isimpossible to fully schedule A′.8Now here is a sequence that is a 4-schedule of A = {5, 5, 4, 3, 3}:(5, 3, 2, 4, 1) = . . . , 5, 3, 2, 4, 1, 5, 3, 2, 4, 1, 5, 3, 2, 4, 1, . . .We need to check any rotation of the sequence keeps k entities satisfied. Indeed, at most one entity,either one of the e3, e4 or e5, is unsatisfied at any point in time.The instance {5, 5, 4, 3, 3} is the smallest example (in number of entities) we could find. We can generalizethis instance for odd n, to the instance A where a1 = a2 = · · · = a(n−1)/2 = n, a(n+1)/2 = n − 1 anda(n+3)/2 = · · · = an = n− 2. This more general family of instances have the property that they are (n− 1)-schedulable but the furthest n− 1 entities do not have a pinwheel schedule. To prove this, we use a methodof showing pinwheel unschedulability which may be of independent interest.Proposition 4. There exist an infinite family of instances that can be used in the proof of Example 3.Proof. We use the generalized instance we describe earlier. The sum of the items is exactly (n− 1)n, so bya later Theorem 6, which we will prove in the next section, this instance is (n− 1)-schedulable.To show that the largest a1, a2, . . . , an−1 are not pinwheel schedulable takes a bit more work. Considerthe density of the furthest n− 1 entities.(n− 12− 1)(1n− 2)+(1n− 1)+n− 12(1n)= 1− 1n(n− 1)(n− 2)To understand what happens for pinwheel schedules of these high density instances, we introduce a newnotion we call waste. Waste occurs when an entity is queried earlier than it needs to be. If entity ei isqueried at time t1 and then later at t2, then the waste of the query at time t2 is defined to be ai − (t2 − t1).When the density is exactly 1, as remarked by Holte et al. [3] all queries to ei must be exactly separatedby ai, and there must be no waste. We call these waste-free schedules. For our instance there is a bit of slacksince the density is 1 − 1/(n(n − 1)(n − 2)), so on average a schedule can have at most 1 unit of waste inevery window of size n(n− 1)(n− 2). To be precise, we know that at all times, all n− 1 entities are satisfied,so every entity must be queried either right as they stop being satisfied or queried earlier. Since queryingearly by 1 time step wastes 1 unit, that can only happen on average once every n(n− 1)(n− 2) time steps.Hence the average gap between consecutive occurrences of waste must be at least n(n − 1)(n − 2) − 1. Wewill show that the length of a waste-free window is less than 3n, contradicting the existence of a pinwheelschedule for the farthest n− 1 entities.Suppose a waste-free window of size 3n starts at some time t0. Since a(n+1)/2 = n − 1, there must besome query to a(n+1)/2 at time t1 ∈ [t0, t0 + n− 2]. As this window has no waste, a(n+1)/2 must be queriedagain at time t2 = t1 + n − 1. Between these two queries is a window of size n − 2. Since all entities mustbe queried at least once every n− 1 steps to remain satisfied and at most once within every n− 1 steps toavoid waste, all other n− 2 entities must be queried exactly once between these two queries.We claim that (i) if at time t ∈ (t1, t2) an entity at distance n is queried then at time t + 2, an entityat distance n − 2 cannot be queried. Otherwise, both would require another query at time t + n, whichwould result in at least one unit of waste when one of the two is queried at time t+ n− 1 or earlier. Sincet + n − 1 < t0 + 3n − 1, this would contradict our assumption that the window of length 3n starting at t0is waste-free. The same reasoning implies that (ii) an entity at distance n − 1 cannot be queried in (t1, t2]directly after an entity at distance n. This implies the query at time slot t2 − 1 must be to an entity atdistance n − 2 (not at distance n). Working backwards, using (i), slots t2 − 3, t2 − 5, . . . , t2 − (n − 4) allcontain queries to entities at distance n−2. This prevents a query at time t2− (n−2) = t1 +1 to any entity,since there are no more entities at distance n − 2, and yet we need to query an entity at distance n. Thiscontradiction proves the proposition.There are examples beyond this family that have the property that there exist a k-schedule but theclosest k entities are not k-schedulable. For example {7, 5, 4, 3, 3} also has this property and can be k-scheduled using the same round-robin schedule. There are also instances like {9, 9, 7, 7, 7, 6, 6, 6, 6} which9has a 7-schedule, but we have shown with a brute-force program that it can’t be attained by using onlythe farthest 7 or even 8 entities. The proof that this instance has a 7-schedule can easily be shown in thefollowing section from Theorem 6.2.6 Round-Robin SchedulesThe schedule that we created as a 4-schedule to the instance A = {5, 5, 4, 3, 3} in Example 3 has the propertythat in every 5 consecutive queries, every element is queried once. We call any query schedule on a set of nentities that repeatedly queries the same permutation of entities a round-robin schedule.Round-robin schedules may be desirable for many reasons. Primarily, round-robin schedules are verysimple to implement and reason about. Furthermore, since each entity is queried as much as any other,satisfying some notion of fairness.However in our setting, not all round-robin schedules are equally effective. For A = {5, 5, 4, 3, 3}, theidentity permutation (1, 2, 3, 4, 5), would have the uncertainty region of all of entities, other than the twoat distance 5, overlap the beacon, thus obtaining only a 2-schedule. Our schedule (5, 3, 2, 4, 1) was veryparticularly chosen to obtain a 4-schedule. In fact, we shall see by our next observation that this is the bestwe could have hoped for in any round-robin schedule.Observation 5. For a round-robin schedule S of the instance A, if S is a k-schedule,kn ≤n∑i=1min{ai, n}. (2.1)Proof. Since S is round-robin, we can focus our attention to a periodic window of size n starting at somet0 > n, when the queries are St0+1, St0+2, . . . , St0+n. Consider the following set of pairs.P = {(ei, t) | ei is satisfied at time t for integer i ∈ [n] and t ∈ [t0, t0 + n− 1]}We remark that for a pair (ei, t) ∈ P , ei may be satisfied by a query during [t0 − n, t0 − 1]. We canget our desired inequality by two simple counting arguments. If S is a k-schedule, then at every timet = t0, t0 + 1, t0 + 2, n + 2, . . . t0 + n − 1, at least k entities are satisfied, so |P | ≥ kn. On the other hand,for any entity ei, it can be satisfied for at most n units of time since we are examining a window of time ofsize n. However if ai < n, as S is a round-robin schedule, ei will be satisfied for exactly ai steps after it isqueried. This means that |P | = ∑ni=1 min{ai, n}. Hence we conclude thatkn ≤ |P | =n∑i=1min{ai, n}.For our example A = {5, 5, 4, 3, 3}, applying our lemma givesk ≤ 5 + 5 + 4 + 3 + 35= 4,so a 4-schedule is the best we could have hoped for. We call such a schedule an optimal round-robin schedule,as the round-robin schedule maximizes the minimum number of satisfied entities. The problem of findingthese optimal round-robin schedules is an interesting algorithmic question by itself. The next theorem tellsus when these schedules exist and how to find them, and is critical in our development of approximationalgorithms in the next section.Theorem 6. Suppose A = {a1, a2, . . . , an} where ai is an integer between 1 and n for all i, and∑ni=1 ai ≥ knfor some integer k. There exists an optimal round-robin schedule that is a k-schedule.10This is a critically important theorem for our approximation algorithms, so we make a few remarksbefore we prove the theorem. First of all, there is no density constraint on A. Secondly, while the statementof the theorem requires ai ∈ [n], this can be relaxed. If ai > n, we can treat ai as n. If we find a k-schedulefor the new instance, it will also be a k-schedule for the original. Finally, if the sum of the distances is notdivisible by n, we can decrease any of the ai’s until it is divisible by n before applying the theorem. Thismeans we can always find a⌊∑ni=1 ain⌋-schedule.Proof of Theorem 6. Consider any schedule where at every time t, the uncertainty region of exactly one entityoverlaps the beacon that wasn’t overlapping at time t − 1, and exactly one entity that has an uncertaintyregion overlapping the beacon is queried. Note that the queried entity could be the same as the newlyoverlapping entity. A schedule with this property is called stable.For a stable schedule the number of satisfied entities is constant. This implies we would actually haveequality in Equation 2.1 of Observation 5, i.e., kn = M . This means that stable schedules are actuallyoptimal round-robin schedules.Fix a window of time of size n, say for the times t = 1, 2, . . . n. A schedule is stable if we have twopermutations pi1 and pi2 where pi1(i) is the time modulo n we should query ei, and pi2(i) is the time whenei stops being satisfied. This way, every entity ei is satisfied exactly between time pi1(i) and pi2(i), possiblywrapping around (mod n) because of a query in a previous round-robin iteration. By the definition of astable schedule we have the following congruence.pi1(i) + ai ≡ pi2(i) (mod n).In a 1952 paper, Marshall Hall [10] proved that this problem about permutations can be solved in anyabelian group if and only if the sum of the elements is zero (in the group). The proof constructs pi1 and pi2,and implies a O(n2) algorithm. In particular we can view the elements of a permutation as equivalent toZ/nZ since our periodic round-robin schedule means we are effectively working in (mod n). Furthermore,M = kn ≡ 0 (mod n), so we may apply his result.2.7 Approximation AlgorithmsAs the pinwheel problem on a list of size n is not known to admit a pseudo-polynomial time algorithm unlessSAT can be solved by a randomized algorithm with expected runtime of nO(logn log logn), we do not expect itto be easy to find k-schedules that maximize k. Hence it is natural to look to find approximation algorithmsthat achieve good approximation factors.Our results in this section will assume that we are working with an instance A = {a1, a2, . . . , an}where d(A) ≤ 1. In general, if d(A) > 1, we may restrict our attention to the farthest n′ distances A′ ={a1, a2, . . . , an′} where n′ is the maximum value such that d(A′) ≤ 1. As we have no good upper boundon when a k schedule exists, besides the density of the k closest entities, the presence of more entities onlymakes finding a good schedules easier. This was illustrated in Example 3, where having an additional elementincreased the maximum k for which there was a k-schedule.We will present two very different ways to create 3n′/4−O(1)-schedules, one using pinwheel schedules inTheorem 7, and one with optimal round-robin in Theorem 9. We extend the optimal round-robin approachto give a better approximation factor of 0.794− ε in Theorem 10.Theorem 7. If δ is a density guarantee for pinwheel scheduling, there exists a bδn′c-schedule.Proof. The furthest bδn′c distances of A′ have density less than δ since d(A′) ≤ 1. Since δ is a densityguarantee for pinwheel scheduling, there exists a bδn′c-schedule S that is a pinwheel schedule.Theorem 7 gives us a δ− approximation on the maximum total number of entities that we can schedule.The best known pinwheel guarantee by Fishburn and Lagarias [5] is δ = 34 and implicitly implies an algorithmalgorithm for finding a schedule. By Theorem 7, this implies the following corollary.11Corollary 8. There exists a b 34n′c-schedule.2.7.1 Round-Robin ApproximationsWe present an alternative round-robin algorithm to get a 3n4 −O(1)-approximation ratio by applying Theorem6 to find optimal round-robin permutations. We further modify the algorithm to find a better guaranteeby using a tree based merging strategy. This is a similar strategy to what Busto et al. [2] call a WeightedRound-Robin strategy, and what Bar-Noy et al. call recursive round-robin schedules, with the added step offinding the optimal round-robin schedule.Theorem 9. There exists a round-robin schedule that is a ( 3n′4 −O(1))-scheduleProof. Since we will be using analyzing round-robin schedules on the farthest n′ entitites, we can do all ouranalysis on a single window of time of size n′, and work modulo n′. We will consider the amount of timethat any element can be satisfied for in a single modulo n′ window. Suppose that αn′ of the distances arecloser than n units away. Denote the density of these distances as dα =∑n′i=αn′1ai. For the other (1− α)nentities with larger window sizes, we will schedule them with a round robin schedule with period n, so theywill always be satisfied. On the other hand, an entity distanced ai away will be satisfied exactly ai timesteps of n′ time steps. We can sum up the number of satisfied entities over a window of size n.n(n− αn) +αn∑i=1ai ≥ n(n− αn) + (αn)2∑αni=1 1/ai= n2 − αn2 + α2n2dα=(1− α+ α2dα)n2 (2.2)The first inequality follows from the arithmetic mean-harmonic mean inequality. The remaining in-equalities follow from using our definition of dα and rearranging terms. By Theorem 6, the overall loss canbe distributed evenly throughout the round-robin, so we can satisfy (1 − α + α2/dα)n of the entities. Thisquantity is minimized when α = 12 and dα = 1 so we can always satisfy at least3n4 entities, as desired.Notice that in the Theorem 9, in the worst case we had α = 12 fraction of the entities take up virtuallyall the density. This suggests a way to construct schedules that approach this 34 threshold. We can haven′/2 − 1 of the entities are exactly n′/2 away, and the other n′/2 + 1 of the entities are farther than n′2/2away or any other configuration that contributes a total density of less than 2/n′.In this worst case, there are a lot of distant entities. When this is the case, we don’t need to query themvery often. In fact we can reduce the number of query slots that these entities take up by using a weightedround-robin that queries those entities less frequently, which is the key idea in proving Theorem 10.Theorem 10. There exists a a 0.794n′ −O(1)-schedule.In order to prove Theorem 10, we will first prove Theorem 11, a result that is more sensitive to theinstance A. Most of the actual algorithm for constructing the schedule will appear in Theorem 11, so wefirst present the proof to Theorem 10 assuming Theorem 11.Theorem 11. There exists a ((2√2− 2− 3−2√2an′)n′ −O(1))-schedule.Proof of Theorem 10. If an ≤ 4, then d(A \ {an}) ≤ 34 so the remaining n − 1 entities can be pinwheelscheduled, resulting in a n − 1-schedule. Otherwise, we can apply Theorem 11 and look at Table 2.1 fora′n ≥ 5 to get a 0.794−O(1)-schedule or more specifically (2√2− 2− 3−2√25 )−O(1)-schedule.Proof of Theorem 11. We will perform a greedy merging procedure to find a modified instance to run round-robin on. Starting with A0 = A′ and our set of entities E0 = E , we will modify our instance to a slightlydifferent set of entities E1 with distances A1 where |E1| = n − 1, then to E2 with distances A2 where|E2| = n − 2, and so on. For ease of notation, for the sth set of entities Es, we will reorder the entities indecreasing order of distance, so as1 ≥ as2 ≥ · · · as|Es|.12a′n (2√2− 2− 3−2√2a′n)3 0.7712174 0.7855135 0.7941136 0.7998327 0.8039178 0.8069819 0.80936310 0.81127011 0.812830· · · · · ·30 0.82270831 0.822893· · · · · ·Table 2.1: Performance for varying an according using Theorem 11On step s of the procedure, we take the two largest distances as−10 and as−11 in As−1. If as−10 ≤ 2anwe terminate this procedure. Otherwise we create a dummy entity e with a possibly fractional distance ofas−11 /2. Every time en+s is queried, instead alternate between querying es1 and es2 which themselves may bedummy entities. We define Es = Es−1 ∪ {en+s} \ {es−10 , es−11 } with corresponding distances As. Note thatas0, the largest element in As, is at most as−11 .This merging scheme is somewhat reminiscent of Huffman encoding schemes. In our final instance, alloriginal entities are leaves of a binary forest (possibly with trivial binary trees consisting of a single node),with dummy entities on higher levels of the trees.We can analyze the density d(Ak) by induction. Our induction hypothesis is for all k ≥ 0,d(Ak) ≤ d(A) + 1ak0. (2.3)This is trivially true for k = 0 as A0 = A′. For a general step s, the merger of es−10 and es−11 results in a netchange of removing their distances and adding the contribution of en+s at distance ajs+1/2. By applying theinduction hypothesis for step s− 1, we get the desired inequality.d(As) = d(As−1)− 1as−10− 1as−11+2as−11≤ d(A) + 1as−10− 1as−10+1as−11= d(A) +1as−11≤ d(A) + 1as0The last inequality follows because as−11 is at least as large as any element in As. Hence our inductionhypothesis is proven.Let’s suppose that this process ran for ` steps before stopping. As in Theorem 9, let α denote thenumber of distances in the list that are greater then ` in A. We also observe that now the largest elementof A′ must be at most 2an, in particular ajn−` ≥ 2an. We can add the following density based constraint on13the number of distances larger than ` and use our induction hypothesis from equation 2.3.n− `2`≤ d(A`)− α ≤ d(A′) + 1a`0− α ≤ d(A′) + 12ad− αWe can combine this with another inequality` ≤ n′ ≤ an′d(A′).This inequality results because an′ is the closest distance among the distances of A′ and hence contributesthe most to the density.If we use Theorem 6 to find the optimal round-robin of A′, we will get a k-schedule for A′, and henceA as well. We note that our optimal round-robin only works for integers, so we may lose at most 1 whenwe round each value of A′ down. Solving and minimizing the amount the same quadratic of Equation 2.2 ofTheorem 9 gives the following inequality.k ≥((2√2− 2) + (6− 4√2)(1− d(A′))− 3− 2√2and(A′))n− 1Since we can pinwheel schedule instances where d(A′) ≤ 34 , we can assume that d(A′) > 34 . The worst caseis attained when d(A) = 1, and hence we get our desired schedule.14Chapter 3Dynamic SettingWe will consider a fixed deterministic query strategy Q, and pit it against an adversary that knows Q, andis allowed to choose the trajectory T on which the query strategy QT does much better than Q. We willanalyze the general dynamic setting with the fixed time, minimum and average measures. We will proveupper and lower bounds on the additive difference between Q and QT listed in Table 3.1. In particular, wewill provide bounds on M(QT , T )−M(Q, T ) for different measures M in terms of n.We focus on these additive differences because traditional approximation ratios between M(QT , T ) andM(Q, T ) are impossible regardless of the measure. Theorem 13 shows the existence of an adversarial setof trajectories T where M(Q, T ) = 0, while M(QT , T ) is a constant fraction of n in both the average andminimum measure. Approximation ratios on the complementary measures on the number of entities whoseuncertainty regions contain the beacon also do not work, as Theorem 13 also shows the existence of a set oftrajectories with M(QT , T ) = n while M(Q, T ) is bounded away from n by an additive difference.To obtain upper bounds on this difference, we will let Q be any round-robin algorithm and analyze howmuch better an informed schedule can do. To prove lower bounds on this difference, we construct difficulttrajectories T based on the underlying Q, and devise a corresponding query strategy Q′ that does betterthan Q.We will also consider these bounds when we restrict to trajectories T where QT can satisfy all entitiesall the time. We call this the promise setting, as we are given a promise that there exists some perfectschedule that keeps all entities satisfied.Objective Dynamic PromiseFixed TimeLower Boundn− 1Upper BoundMinimumLower Bound⌊2n−13⌋ ⌊n2⌋Upper Bound b 4n−15 cAverageLower Bound bn+13 c⌊n16⌋Upper Bound⌊n2⌋Table 3.1: Proven bounds on the gap between a deterministic algorithm on an adversarial trajectory andthe optimal query schedule on that trajectory in the general dynamic setting and in the promise setting.153.1 Dynamic Trajectory PlotsDistanceTimeDistanceTimeFigure 3.1: On the left is an example dynamic trajectory plot. On the right is an example of the trajectoryof a single entity.To succinctly describe the trajectories T as well as the queries made by Q and Q′, we will use what wecall dynamic trajectory plots. Figure 3.1 gives an example. These plots will be used to describe the difficulttrajectories T we will construct, as well as the queries to those entities by an algorithm Q and a better querystrategy Q′ that knows the trajectories.In these plots, the trajectories of different entities are displayed with different colours along with redsquares for queries made by Q and black circles for queries made by Q′ with purple circles denoting queriesmade by both.After one such query to an entity, because all entities have unit speed, the uncertainty regions of thatentity will approach the x-axis with slope −1. This will be drawn with dashed lines to denote the closestpoint of the uncertainty region to the beacon when appropriate.3.2 Upper Bounds by Adversarial TrajectoriesIn order to show upper bounds on what online deterministic query strategies Q can attain, we look atconstructing adversarial trajectories and what a query strategy Q′ that knows these trajectories can do.3.2.1 Fixed Time ObjectiveIf our goal is to maximize the number of away regions at the beacon a fixed time t, for any fixed algorithmALG, there exist a set of trajectories T where it is impossible to compete with OPT. OPT can keep n − 1more entities away from the beacon than ALG, which is almost the worst possible news for any algorithm.The following theorem explains the adversarial trajectory.Theorem 12. For any fixed time t ≥ n, c ∈ {0, 1} and any deterministic query strategy Q, there exists atrajectory T and informed query strategy Q′ such that Mt(Q′, T ) = n− 1 + c and Mt(Q, T ) = c,Proof. It is possible to construct the trajectories such that at time t− n+ 1, all n entities are at distance nfrom the beacon. T is designed so that for Q, whatever it chooses to query at time t − i will appear to bedistance i from the beacon. Let ti be the latest time before t that entity ei is queried by Q. The trajectory ofentity ei at time ti heads away from the beacon at maximum speed. Consider the following better strategyQ′ that knows the trajectory of the entities. Q′ queries entity ei at time ti + 1. The uncertainty region ofei doesn’t overlap the beacon until time t + 1. This is illustrated in Figure 3.2. It is also possible for ti tonot exist, that is if Q does not query entity ei at all. In this case, Q′ queries ei at any time between timet − n + 1 and t. Since there are n time slots, and fewer than n unique entities queried by Q, there must16DistanceTimet9Figure 3.2: Dynamic trajectory plot for fixed time objective of n = 9 entities that appear to be headingtowards the beacon at time t, but as soon as ALG queries each entity for the last time before t, the entitiesstart moving away from the beacon.always be some time for Q′ to query ei. If Q′ does this for all entities for which ti < t, Q′ can have all n− 1regions except whatever Q queried at time t away from the beacon.For the final entity en, the entity that Q queries at time t, we can either have both Q and Q′ keepthe region of en away from the beacon or have both of them suffer overlap of that region by having en bedistance 0 from the beacon at time t.The trajectory that was constructed for this theorem will have n − 1 uncertainty regions reach thebeacon at time t+ 1 for Q′. If we were to consider the other measures of average or minimum over a windowof time that included t + 1, Q′ does not do much better than Q. However, for these measures we will seeexamples where better query strategies can do much better than Q.3.3 Minimum ObjectiveIn order to create an adversarial trajectory T against an online deterministic query strategy Q with the goalof maximizing the minimum number of satisfied entities over all time, we only need to make Q perform poorlyat some specific time t, which achieves this minimum. Furthermore, we need to ensure that the optimalquery strategy QT does relatively well at all times. We can choose a trajectory such that the only times thatmatter for QT are between time t − n and time t + n. Before and after this range of time, we can have allentities be farther than n away, and any round-robin schedule would keep all regions from overlapping thebeacon.We can make a slight adaptation of the strategy Q′ we had for the fixed time objective. Instead ofhaving Q′ query an entity one time step after Q queries it for the last time before time t, we can have Q′query the entity⌊n3⌋time steps after, and only for the farthest⌊23n⌋entities, as in Figure 3.3. This way, Q′has exactly enough time to keep these⌊2n3⌋entities away from the beacon by querying them again in thenext⌊2n3⌋time steps after time t, while Q can’t keep a single region away from the beacon at time t. Theother 0 ≤ c ≤ ⌈n3 ⌉ entities can be so far away from the beacon that earlier queries keep them away from the17DistanceTimet9Figure 3.3: Dynamic trajectory plot for n = 9 entities, adversarial for the minimum objective. Q′ keeps 6 ofthe regions away while Q fails to satisfy any entity at time t.beacon by an earlier query by Q′, or too close to the beacon that neither Q nor Q′ can keep them away attime t. This proves the following theorem.Theorem 13. For any deterministic query strategy Q, and any integer 0 ≤ c ≤ ⌈n3 ⌉, there exists a set oftrajectories T and a query strategy Q′ such that Mmin(Q′, T ) =⌊2n3⌋+ c and Mmin(Q, T ) = c.Note that the Q′ we have devised here is not optimal for the trajectory T we have chosen, as theremay be more clever ways for the optimal query strategy QT to query entities to ensure a larger fraction ofentities are kept away from the beacon both at time t and shortly thereafter. This reduces to a problemabout matching queries before time t to queries after time t to keep the same number of regions away fromthe beacon. We were unable to find a systematic matching, but we will give an upper bound on how wellthe adversary can do in the following section.3.3.1 An Upper BoundWe observe that the type of trajectory T where all entities appear to be heading to the origin at some timet and leaving right after the last time Q has queried the entity before time t is the trajectory that has theentities as far away from the beacon as possible while forcing Q to have a large number of unsatisfied entitiesat time t.Theorem 14 proves upper bounds on how large the gap in performance is by considering a round-robinstrategy Q when faced with this trajectory and the optimal query strategy QT . Afterwards, we observein Observation 15 that replacing the round-robin strategy Q with any other query strategy Q′ allows for atrajectory T ′ that has the entities farther from the beacon, resulting in a worse gap.Theorem 14. Let Q be any round-robin strategy. Mmin(QT , T )−Mmin(Q, T ) ≤ 4n−15 for any trajectory Tand optimal query strategy QT .18Proof. Let t be a time when the round-robin schedule Q satisfies the minimum number of entities. Letc = Mmin(QT , T )−Mmin(Q, T ). At all times, QT must satisfy c more entities than Q does at time t.Let E be the set of entities satisfied by QT at time t that are not satisfied by Q at time t, i.e.,E = A(QT , T , t) \A(Q, T , t).Each of these entities must have been queried by QT sometime after Q queried them, but before timet. Define ti to be the latest time before t that Q queried ei, and define t′i to be the latest time before t thatQT queried ei. For ei ∈ E, we know ei is unsatisfied by Q at time t, so we have the following inequality onthe distance ei was from the beacon at time ti:a(ei, ti) ≤ t− ti. (3.1)Since entities have a maximum speed of 1, we can bound how far ei ∈ E can be from the beacon attime t′i:a(ei, t′i) ≤ a(ei, ti) + (t′i − ti) ≤ t+ t′i − 2ti. (3.2)This means that shortly after time t, ei ∈ E will stop being satisfied for QT . We will denote this timeas tˆi. We use equation (3.2) to upper bound tˆi:tˆi = t′i + a(ei, t′i) ≤ t+ 2t′i − 2ti.Let Eˆ ⊆ E be the c entities ei ∈ E with largest tˆi values.For a round-robin schedule Q, the earliest times that Q can query entities in Eˆ are t − n + 1, t − n +2, . . . , t−n+ c, while the latest times that QT can query these entities are t− c+ 1, t− c+ 2, . . . , t. Considermaximizing the sum of tˆi over all entities in Eˆ. This sum is invariant over the order in which Q and QTchoose to query ei ∈ Eˆ. ∑ei∈Eˆtˆi ≤∑ei∈Eˆ(t+ 2t′i − 2ti)= tc+ 2∑ei∈Eˆt′i −∑ei∈Eˆti≤ tc+ 2(c∑i=1(t− c+ i)−c∑i=1(t− n+ i))= tc+ 2c(n− c).(3.3)Now we describe a requirement for schedule QT to allocate queries to entities ei ∈ E after time t sothat QT satisfies at least c more entities than Mmin(Q, T ) at all times. For all ei ∈ E, either strategy QTqueries entity ei before (or at) time tˆi or ei becomes unsatisfied at time tˆi. Let d = |E| − c. For every timet+ j, there must be at most j expiry times tˆi for ei ∈ Eˆ that occur in (t, t+ j] or else QT would be unableto satisfy c + Mmin(Q, T ) entities at time t + j. Indeed, if more than j expiry times for ei ∈ Eˆ occur in(t, t + j] then more than d + j expiry times for ei ∈ E occur in (t, t + j] since entities in Eˆ have the latestexpiry times of enitities in E. However, at most j queries can be made in this time, which means fewer than|E| − d+Mmin(Q, T ) = c+Mmin(Q, T ) entities are satisfied at time t+ j.We define I(tˆi ≤ t+ j) to be the indicator function that is 1 if tˆi ≤ t+ j and 0 otherwise. This way wecan represent the preceeding requirement as:∑ei∈EˆI(tˆi ≤ t+ j) ≤ j.Since the indicator function has value 0 or 1, we have the trivial inequality:∑ei∈EˆI(tˆi ≤ t+ j) ≤ c.19We can sum up these constraints for j between 1 and 2n to get:2n∑j=1∑ei∈EˆI(tˆi ≤ t+ j) ≤2n∑j=1min{j, c} = c(c+ 1)2+ c(2n− c) = −c2/2 + c/2 + 2cn. (3.4)Alternatively, we can switch the order of summation. For any ei ∈ E, summing the indicator function overj from 1 to 2n yields exactly t+ 2n− tˆi + 1. Thus,∑ei∈Eˆ2n∑j=1I(tˆi ≤ t+j) =∑ei∈Eˆt+2n−tˆi+1 = c(t+2n+1)−∑ei∈Eˆtˆi ≥ c(t+2n+1)−c(t+2(n−c)) = c+2c2 (3.5)where the inequality comes from equation (3.3). Together, equations (3.4) and (3.5) implyc+ 2c2 ≤ −c2/2 + c/2 + 2cn ⇒ c ≤ 4n/5− 1/5.In the proof of Theorem 14 we used the fact that for round-robin Q, the last query to entity ei beforetime t is at t′i ∈ [t− n+ 1, t]. For an arbitrary query schedule Q′, these t′is can be even earlier, giving worsebounds. This means for any non-round-robin strategy Q′, the gap for the minimum objective is larger thana round-robin strategy. This gives us the following observation.Observation 15. For any deterministic query strategy Q′, and round-robin strategy Q,maxT(Mmin(QT , T )−Mmin(Q, T )) ≤ maxT (Mmin(QT , T )−Mmin(Q′, T )).By trying all possibilities for the times t′i when QT could query entities ei, we can find the actualdifference between QT ’s and Q’s performance for n ≤ 17. We compare the bound from Theorem 14 withthis difference in Table 3.2. This bound is tight for many values of n.3.3.2 Promise Setting0DistanceTime99 181827Figure 3.4: Dynamic trajectory plot for n = 9 entities, where there exists a Q′ that can keep all n entitiessatisfied at all times by repeating this trajectory every 2n time steps.20n⌊4n−15⌋maxT (Mmin(QT , T )−Mmin(Q, T ))2 1 13 2 24 3 25 3 36 4 47 5 58 6 69 7 610 7 711 8 812 9 913 10 1014 11 1015 11 1116 12 1217 13 13Table 3.2: Table of actual and upper bound gaps for performance under the minimum objective.21If we wanted Q′ to be able to keep all n entities away, we would want to simply have the⌊13n⌋entitiesthat Q queries stay at say 3n distance away for an early query by Q′ to keep them satisfied. However Qwould be able to react to seeing those entities farther away than other entities, and may change its sequenceof queries accordingly. Hence, we need to be a little more careful and a little less ambitious when designingsuch a trajectory. Instead, we can query the d 12ne later entities that Q queried before querying the otherentities afterward. In a manner as Figure 3.4 shows, Q′ can keep all regions away from the beacon, while Qcan keep⌊12n⌋regions away from the beacon.Theorem 16. For any deterministic query strategy Q, there exists a trajectory T and query strategy Q′such that Mmin(Q′, T ) = n and Mmin(Q, T ) ≤⌊n2⌋.3.4 Average ObjectiveFor the minimum measure, it was straightforward to construct an adversarial trajectory around the timewhen an online deterministic strategy Q satisfied the minimum number of entities. It is not so easy tounderstand how to design an adversarial trajectory T that maximizes the gap in performance between Qand an optimal strategy QT for the average objective.3.4.1 Lower boundsWe can find a lower bound on how big this gap is for a fixed Q by considering an adversarial trajectory thatforces Q to always fail to keep any entity satisfied.DistanceTimeFigure 3.5: Dynamic trajectory plot where every time Q decides to query an entity, it appears to be on topof the beacon, but the entity actually moves away from the beacon to be queried by Q′.Theorem 17. For any deterministic query strategy Q, there exists a trajectory T with optimal strategy QTsuch that:Mavg(QT , T )−Mavg(Q, T ) ≥⌊n+ 13⌋Proof. We will prove this theorem by constructing an adversarial trajectory T where at every time t when Qqueries an entity, that entity will appear at the beacon. We will be able to devise a strategy Q′ that knowsthe trajectories Q′ that will keep⌊n+13⌋of the entities satisfied while Q cannot keep any entity satisfied.As Q is deterministic and we have fixed the query responses that Q will get, the queries that Q performsis a deterministic sequence. We can design a trajectory T consistent with the responses to these queriesby having each entity be exactly at the beacon at these times, and go as far away from the beacon beforecoming back to appear at the origin for the next time Q queries that entity. This trajectory is illustrated inFigure 3.5.22DistanceTimecc+ bn2cFigure 3.6: Dynamic trajectory plot for an adversarial set of trajectories against a round-robin query strategy.Suppose Q′ wants to keep x entities away from the beacon. At time t, if it queries any of the (at least)n−(2(x−1)+1) entities that are not queried by Q in time steps t−(x−1), t−(x−1)+1, . . . , t+(x−1) thenthat query will satisfy the entity for at least x time steps (up to, but not including, time t+ x). As long as,for all t, there are x such entities to choose from, Q′ can always satisfy at least x entities simply by queryingthe one at time t that it has not queried in the past x− 1 time steps. This occurs if n− (2(x− 1) + 1) ≥ xor x ≤ ⌊n+13 ⌋.Promise SettingIf we wanted to devise a trajectory for which Q′ keeps all entities away from the beacon, we can use thesame trajectory that was used to prove Theorem 16 and is shown in Figure 3.4 and repeat every 2n steps.Theorem 18. For any fixed time t and any deterministic query strategy Q, there exists a trajectory T andquery strategy Q′ such that Mavg(Q′, T ) = n and Mavg(Q, T ) ≤ 1516n.3.4.2 Performance of Round-RobinIt is very natural to consider the set of trajectories as in Figure 3.6. As depicted, whenever the round robinquery strategy Q queries an entity, it is c away from the beacon, while Q′ queries the entity⌊n2⌋units oftime later, where it is c +⌊n2⌋units away. In this setting the gap between an optimal query strategy andthe round-robin strategy under the average objective is at least⌊n2⌋.With more difficulty, we show (in Theorem 19) that n2 is an upper bound on the gap as well. Thecomplexity of the proof may be attributed to the many ways an optimal query strategy QT may queryan entity based on the many possible choices for a set of trajectories T . For some entities, QT can makemultiple queries between two successive queries by a round-robin strategy, while other entities may not bequeried very frequently at all by QT because either they are far away, or are so close to the beacon thatqueries would be ineffective. To handle this variability, we use a potential function argument, which makesthe proof somewhat technical.Theorem 19. Let Q be any round-robin strategy. For any set of trajectories T , an optimal query strategyQT for that trajectory must satisfyMavg(QT , T )−Mavg(Q, T ) ≤ n2In order to prove this theorem, we will analyze what happens to an entity e between two consecutivequeries made by the round-robin strategy. Two consecutive queries partition our time into intervals of ntime units that we will call blocks. Consecutive queries will be exactly n time units apart, and without loss230 nht2 =n−h+xn2x1n+h+x22x2n+h+x24t1 =n−3h+x24Figure 3.7: Trajectory of entity used to calculate f2 for Lemma 22of generality we can assume they are at time 0 and time n. We begin by defining a family of functions whichdescribes how much more an optimal query strategy can keep the entity away from the beacon compared toa round-robin strategy. We will call this the effectiveness of the queries made by QT .fk(x1, x2) = maxT{ n−1∑t=0I[e ∈ A(QT , T , t)]− I[e ∈ A(Q, T , t)] such thatQ queried e at time 0,the uncertainty region of e is exactly x1 away at time 0 for QT ,the uncertainty region of e is exactly x2 away at time n for QT , andQT makes k queries to e between time 0 and n− 1}.We first prove the following three lemmas about fk.Lemma 20. For a round-robin query strategy Q and x1 ≥ 0 and x2 ≥ 0,fk(x1, x2) ≤ max{0, n− x1}Lemma 21. For a round-robin query strategy Q, x1 ≥ 0 and x2 ≥ 0,f1(x1, x2) ≤ 12(n+ x1 − x2)Lemma 22. For a round-robin query strategy Q, x1 ≥ 0 and x2 ≥ 0,f2(x1, x2) ≤ 14(3n+ 3x1 − x2).Proof of Lemma 20. Let the entity e be h away from the beacon at time 0. By definition of the uncertaintyregion, h ≥ x1. Regardless of k, QT can keep e satisfied for at most n units of time in this block. Q’squery at time 0 will keep e satisfied for h units of time of which min{n, h} are in this block. Since h ≥ x1,f1(x1, x2) ≤ n−min{n, x1} = max{0, n− x1}.24Proof of Lemma 21. Let the one query that QT makes be at time t. At time 0, let the entity be distanceh away from the beacon. At time t, it can be at most distance h + t away from the beacon. On the otherhand, it must be at least x2 + (n− t) away from the beacon to ensure that its uncertainty region is x2 awayfrom the beacon at time n. Hence we have t ≥ 12 (n+x2−h). QT ’s query at time t keeps the entity satisfiedfrom time t until time n (when the uncertainty region is x2 ≥ 0 away). QT will keep the entity satisfied forthe first x1 units of time as well as the last n− t units of time for a total of at most x1 +n− t untis of time.On the other hand Q keeps the entity satisfied for h units of time from its query at time 0. This allows usto bound f1(x1, x2).f1(x1, x2) ≤ x1 + n− t− h ≤ x1 + n− 12(n+ x2 − h)− h = 12(n− x2 + 2x1 − h)Observing that h ≥ x1 by the definition of the uncertainty region gives us the lemma.Proof of Lemma 22. Let the two queries that QT makes be at time t1 and t2 respectively. Let the distanceof the entity from the beacon be h at time 0, h1 at time t1 and h2 at time t2. t2 should be at queried at thefirst instance that a query can have the uncertainty region exactly b away at time n. As before we must havet2 ≥ 12 (n − h + b) at distance h2 = x2 + n − t. To upper bound f2, we may assume that t2 occurs as earlyas possible at time 12 (n − h + b) as to keep the entity satisfied for as long as possible. The only trajectorythat is consistent with t2 and h2 must have the entity move directly away from the beacon the entire timebetween time 0 and time t2. If this is the case, to maximize the effectiveness of the first query, it should bewhen it is at 12h2, then this would keep e satisfied for all time [t1, n). Figure 3.7 illustrates this. We canfigure out the earliest time that the entity is exactly 14 (n+ h+ b) by extrapolating backwards from time t2,it would be at the following time t′ which we can find as follows.t1 ≥ t2 − 14(n+ h+ b) ≥ 12(n− h+ b)− 14(n+ h+ b) =14(n− 3h+ b)QT keeps the e satisfied for the first x1 units of time and at most the last n− t1 units of time. On theother hand Q keeps e satisfied for exactly h units of time. This let’s us upper bound f2(x1, x2).f2(x1, x2) ≤ x1 + (n− t1)− h = 14(4x1 + 4n− (n− 3h+ x2)− 4h) ≤ 14(3n+ 4x1 − h− x2)Observing that h ≥ x1 by the definition of the uncertainty region gives us the lemma.Proof of Theorem 19. We analyze for any trajectory T , how much better QT can do than the round-robinstrategy Q from a window of time of length mn for some m we specify later.Fix an entity e ∈ E . Queries to e are spaced n apart because Q is a round-robin strategy. Without lossof generality, we can assume that e is queried by Q at time 0, n, 2n, · · · , (m−1)n. Let x0, x1, x2, · · · , xm−1be the distance the uncertainty region of e is from the beacon for QT at those respective times. Let ki bethe number of queries that QT made to e in the ith block of time. With this notation, and our previouslydefined notion of effectiveness, we analyze how much better than n2 effectiveness QT can get per query bydefining a quantity ∆e as follows.∆e =m−1∑i=0fki(xi, xi+1)−m−1∑i=0kin2We rearrange the summations and include the net change in height into the summation. This parttelescopes.∆e =x02− xnm2+m−1∑i=0(fki(xi, xi+1)−kin2− xi2+xi+12)25We let gi denote the ith summand of the equation.gi = fki(xi, xi+1)−kin2− xi2+xi+12We group these blocks into contiguous chunks that start with blocks where xi ≤ n2 . We will let B denotethe indices of these starting blocks, and define ` = |B|.B ={i|xi ≤ n2}= {b1, b2, . . . , b`}We define the following summation sj over the jth chunk for 1 ≤ j ≤ `− 1.sj =bj+1−1∑i=bjgiIt is useful to also define two more summations over (possibly empty) chunks s0 and s` as follows.s0 =b1−1∑i=0gis` =nm−1∑i=b`giThis way, we can separately analyze three parts of ∆e.∆e =(x02+ s0)+(−xnm2+ s`)+`−1∑j=1sjWe first show that sj ≤ 0 for the chunks 1 ≤ j ≤ `− 1. This analysis we split into three parts. First weanalyze when the jth chunk consists of a single block. If it does not, we will first analyze the contribution ofthe first block within that chunk, then the contribution of the rest. Afterwards, we analyze the contributionsof the first chunk s0 and the last chunk sj .Singleton chunks Let’s first consider the case where sj is a summation over a single block. If this is thecase, xbj ≤ n2 and xbj+1 = xbj+1 ≤ n2 . If kbj = 0, then xbj+1 = 0, as there were no queries to e in the bjthblock. In this case, gbj = −xbj2 ≤ 0. If kbj ∈ {0, 1}, it follows from Lemma 21 and Lemma 22 that gbj ≤ 0.If kbj ≥ 3, we can use Lemma 20 to get the following inequality.gbj = fkbj (xbj , xbj+1)−nk2− xbj2+xbj+12≤ n− xbj −3n2+n2= −xbj ≤ 0First block of a chunk For a chunk to not consist of a single block, for the first block we must havexbj ≤ n2 and xbj+1 > n2 . In the following section we will show that the contribution of the first block gbj ≤ λwhere λ = xbj+1/2− n/4. Note that λ > 0. Now we split into cases depending on kbj .kbj 6= 0, since the uncertainty region can’t increase in distance to the beacon without QT using at least onequery.If kbj = 1, Lemma 21 shows thatgbj ≤ 0 ≤ λIf kbj ≥ 3, applying Lemma 20 we get the following.gbj ≤ n− xbj −kbjn2+xbj+12− xbj2≤ xbj+12− n2≤ λIf kbj = 2, then by Lemma 22 we know the following:gbj ≤3n+ 3xbj − xbj+14− n− xbj2+xbj+12=xbj + xbj+1 − n4≤ xbj+12− n4= λ26Tail of a chunk Let’s proceed to analyze the contribution of the rest of the blocks i for bj + 1 ≤ i < bj+1,where xi > n2 . By Lemma 20 we know the following.fki(xi, xi+1) ≤ max{0, n− xi} ≤n2Applying this to the definition of gi gives the following inequality.gi = fki(xi, xi+1)−kin2− xi2+xi+12≤ −xi2+xi+12.This will telescope until the end of the block where xbj+1 ≤ n2 .bj+1−1∑i=bj+1gi ≤bj+1−1∑i=bj+1−xi2+xi+12= −xbj+12+xbj+12≤ −xbj+12+n4= −λHence we have shown that for this case,sj =bj+1−1∑i=bjgi = gbj +bj+1−1∑i=bj+1gi ≤ λ− λ = 0.First chunk Now we will show that x02 +s0 ≤ n4 . If x0 ≤ n2 , then s0 is an empty summation, so x02 +s0 ≤ n4 .Otherwise x0 > n2 . This would mean it telescopes, sox02+ s0 ≤ x02− x02+xb12≤ n4.Last chunk Finally we will show that −xnm2 + s` ≤ n. It is possible that there B is empty so s` is anempty summation. In this case s` = 0 and the total contribution is nonpositive. It is possible that s` consistsof a single block, so b` = nm− 1. In this case we apply Lemma 20 to show the following.−xnm2+ s` = −xnm2+ gnm−1 ≤ −xnm2+ max{0, n− xnm−1} − knm−1n2− xnm−12+xnm2≤ nOtherwise, we apply the same analysis as to the start of a chunk gb` ≤ xb`+12 − n4 and the rest telescopes so,−xnm2+ s` = −xnm2+ gb` +nm∑i=b`+1gi ≤ −xnm2+xb`+12− n4− xb`+12+xnm2= −n4< n.Now we can bound our ∆e as follows.∆e =(x02+ s0)+(−xnm2+ s`)+`−1∑j=1sj ≤ n+ n2≤ 3n2Notice that ∆e has no dependence on m. This means that the contribution becomes vanishingly smallas m grows large. This means that:1mn∑e∈E∆e = O(n/m)For entity e, let ke denote the number of times QT queried e. Note that∑e∈E ke = nm as QT shouldquery every entity at every time step. We sum over all entities of E and normalized by mn to get thefollowing.1mn∑e∈E∆e =1nm(mn∑t=1(|A(T , QT , t)| − |A(T , Q, t)|)−∑e∈Eken2)=1nmmn∑t=1(|A(T , QT , t)| − |A(T , Q, t)|)−n227This means that:1nmmn∑t=1(|A(T , QT , t)| − |A(T , Q, t)|)− n2≤ O(n/m)If we take a limit as m goes to infinity, we get the theorem.Mavg(T , QT )−Mavg(T , QT )− n2≤ 028Chapter 4Conclusion4.1 Conclusion of the Static SettingIn the static setting we focused our attention to the minimum overlap and started by proving an upper densitybound on what can be scheduled in Theorem 1, a similar bound in the related problem of pinwheel scheduling.We also investigated optimal round-robin schedules and provided guarantees about their performance inTheorem 9 and Theorem 10.There are questions relating to creating optimal schedules that achieve better approximation guarantees.Are there algorithms that can attain better approximation factors? Does there exist a PTAS that gets a(1 − ε)-approximation like the work by Kleinberg and Immorlica [9]? We don’t believe that much betterthan a constant factor approximation bounded away from 1 is possible with round-robin techniques withoutnew techniques.4.2 Conclusion of the Dynamic SettingWe have shown a multitude of results on the gap between a deterministic query strategy and the optimalquery strategy when an adversary chooses the trajectory. Theorem 12 proved that the gap for the fixed timeobjective was n− 1 no matter what query strategy was employed. Theorem 13 proved that the gap for theminimum objective is at least⌊2n3⌋for any algorithm, Theorem 14 proved that it is at most⌊4n−15⌋. Finallyfor the average measure Theorem 17 proved that the gap was at least⌊n+13⌋, while Theorem 19 proved itwas at most n2 for the round-robin strategy. In the promise setting, we also showed similar gaps.Most of the bounds we have found for round-robin in the minimum and average objective seem to betight, but it is difficult to find adversarial trajectories that work on all query strategies. It is even moredifficult to do so in the promise setting. It would be interesting to see the lower bounds refined by moresophisticated trajectories.Randomized query strategies are also an entirely separate setting that also deserves some more investi-gation. Some of the trajectories that were used in the lower bound proofs can be modified to work well inexpectation against any random query strategy, but this is a direction that has not been explored.Under both minimum and average objective, we conclude that a round robin algorithm is the onlyreasonable algorithm when we wish to be competitive. This may be attributed to the highly pessimisticnature of the worst case analysis. It would be interesting to consider less pessimistic competitive analysis,such as when trajectories and movements of entities are random and follow some distribution.29Bibliography[1] William Evans, David Kirkpatrick, Maarten Löffler, and Frank Staals. Minimizing co-location potentialof moving entities. SIAM Journal on Computing, 45(5):1870–1893, 2016.[2] Daniel Busto, William Evans, and David Kirkpatrick. Minimizing Interference Potential Among MovingEntities, pages 2400–2418.[3] R. Holte, A. Mok, L. Rosier, I. Tulchinsky, and D. Varvel. The pinwheel: a real-time schedulingproblem. In Proceedings of the Twenty-Second Annual Hawaii International Conference on SystemSciences. Volume II: Software Track, volume 2, pages 693–702. IEEE Comput. Soc. Press, 1989.[4] Mee Yee Chan and Francis Y. L. Chin. General schedulers for the pinwheel problem based on double-integer reduction. IEEE Trans. Comput., 41(6):755–768, June 1992.[5] Fishburn and Lagarias. Pinwheel scheduling: Achievable densities. Algorithmica, 34(1):14–38, Sep 2002.[6] Tobias Jacobs and Salvatore Longo. A new perspective on the windows scheduling problem. CoRR,abs/1410.7237, 2014.[7] Amotz. Bar-Noy and Richard E. Ladner. Windows scheduling problems for broadcast systems. SIAMJournal on Computing, 32(4):1091–1113, 2003.[8] Leszek Gąsieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, and Tomasz Radzik.Bamboo garden trimming problem (perpetual maintenance of machines with different attendance ur-gency factors). In Bernhard Steffen, Christel Baier, Mark van den Brand, Johann Eder, Mike Hinchey,and Tiziana Margaria, editors, SOFSEM 2017: Theory and Practice of Computer Science, pages 229–240, Cham, 2017. Springer International Publishing.[9] R. Kleinberg and N. Immorlica. Recharging bandits. In 2018 IEEE 59th Annual Symposium on Foun-dations of Computer Science (FOCS), pages 309–319, Oct 2018.[10] Marshall Hall. A combinatorial problem on abelian groups. Proceedings of the American MathematicalSociety, 3(4):584–587, 1952.30
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Scheduling queries to moving entities to certify many are distant from a region
Text