Techniques in Design and Analysis of Online Algorithms

Get Complete Project Material File(s) Now! »

A New Model with Untrusted Advice

In the machine-learning community, a new advice model was proposed to cap-ture the above observations by Lykouris and Vassilvitskii [52], and Purohit et al. [57]. In their work, they use predictors to design and analyze online algorithms. If the predictor is bad, then the online algorithm should perform close to the one without predictions; if the predictor is good, then the online algorithm should perform close to the optimal offline algorithm.
Motivated by the above work from machine learning, in this thesis, we consider the advice model in which the advice can be either trusted or untrusted. In this setting, the performance of an online algorithm can be characterized by a pair of competitive ratios, namely the competitive ratio when the advice is trusted and the competitive ratio when the advice is untrusted. We also assume that, in the latter case, the un-trusted advice is generated by a malicious adversary to be in accordance with the worst-case nature of the incompetitive analysis.
Thus the competitiveness of an algorithm can be presented as a point in the 2-dimensional space with coordinates depicted by the competitive ratios when the advice is either trusted or untrusted. We are interested in finding a Pareto frontier of the set of all possible algorithms assuming that the advice has an infinite number of bits so that the advice can encode the optimal solution. A more formal description of the model and of the competitiveness will be given in Section 5.1.2. In this thesis, we will work on a specific application of this model, namely the online bidding with untrusted advice problem, which is presented as follows.

Lower Bound on the Competitive Ratio of Deterministic Algorithms

Boyar et al. [17] show that the deterministic competitive ratio of the problem is 2 for k = 1 and 3/2 for k = 2. We complete this picture by showing a lower bound of 1 + k 1 1 for all k 3. Note that the lower bound is tight for k = 3, as the algorithm GREEDY, which works by assuming that k is only 2, has competitive ratio 3/2.
Theorem 2.9. The deterministic competitive ratio of the online matching problem with k edge-recourse is at least 1 + k 1 1 for all k 3.
Proof. We consider three cases, namely the cases k = 3, k is even and at least 4, and finally k is odd and at least 5. For each case we present an appropriate adversarial argument. Case k = 3. Suppose, by way of contradiction, some algorithm claims a compet-itive ratio strictly smaller than (3n + 2)/(2n + 2) for some arbitrary n 1. The adversary releases a single edge, creating an augmenting path of length 1. Then the algorithm applies the augmenting path, which the adversary extends by appending one edge on each side, creating an augmenting path of type 0,1,0, as shown in Fig-ure 2.5(a). Since the current competitive ratio is 2, the algorithm needs to apply this path, which the adversary again extends by appending an edge on each side, creat-ing an augmenting path of type 0,1,2,1,0, as shown in Figure 2.5(b). Since the current competitive ratio is 3/2, the algorithm applies this path. In response the adversary appends an edge at each endpoint of the type 3 edge, and at each endpoint of one of the type 1 edges, as shown in Figure 2.5(c). The resulting graph has a blocked augmenting path of type 0,3,0, and an augmenting path of type 0,1,0, as shown in Figure 2.5(c). The algorithm needs to apply the latter one as the competitive ratio is currently 5/3 > 3/2.

Online Matching in the Edge Arrival/Departure Model

In this section we consider the online matching problem with k edge-recourse in the setting in which edges may arrive but also depart online. More precisely, a request sequence for this problem is of the form (pi, ei)i 1, namely the i-th request consists of an edge ei and its mode pi 2 farrive, departg. If pi = arrive then the edge ei becomes available; this corresponds to the arrival setting studied in Section 2.2. If pi = depart, then ei is removed from the graph, and can be used by neither the online algorithm or the optimal offline algorithm. We emphasize that in this model, an edge of the form (u, v) may arrive and depart several times in the course of serv-ing a request sequence, but every time it arrives it is considered as a “fresh” edge. As a consequence, upon each arrival, such an edge is assigned type 0. Moreover, a departing edge ceases to exist in any matchings.
As explained in the Introduction, we will further distinguish between two mod-els. In the limited departure model, an edge cannot depart while it is being used in the matching of the online algorithm, whereas in the stronger full departure model any edge can depart.
It turns out that the full departure model is quite restrictive. This is because it is possible for the adversary to force an online algorithm to augment some augmenting path and then to remove one of the edges in its matching. Eventually the algorithm can end up with blocked edges (type k), without having the chance to augment its matching. This intuition is formalized in the following lemma.
Proof. To show an upper bound of 2, consider an algorithm which adds to its match-ing any edge whose endpoints are unmatched. The edge types are either 0 or 1, and therefore the algorithm is not sensitive to the given edge budget. The matching pro-duced by the algorithm is (inclusion wise) a maximal matching, and it is well known that its size is at least 1/2 the size of the maximum matching.
To show a lower bound of 2, consider a graph consisting of vertices 1, 2, 3, 4, with the edge (2, 3) arriving at the beginning. Then the edges (1, 2), (3, 4) arrive and depart repeatedly, alternating between two configurations. When the graph consists of the single edge (2, 3), the algorithm needs to include it in its matching. When the graph consists of the path (1, 2, 3, 4), the algorithm needs to apply this augmenting path if it claims to have a competitive ratio strictly lower than 2. As a result, the type of the edge (2, 3) keeps increasing, and when it reaches k, the algorithm cannot augment the matching anymore. Thus, for even k, the algorithm has a matching of size 0, while the optimal matching consists of the edge (2, 3). Similarly, for odd k, the algorithm has a matching of size 1, while the optimal matching has size 2. Hence, no algorithm can achieve a competitive ratio strictly lower than 2.
Since the full departure model is very restrictive for the algorithm, as shown in Lemma 2.10, we will concentrate on the limited departure model, as defined in the introduction. For this model, we observe that the algorithms L-GREEDY and AMP have the same performance guarantee as in the edge arrival model. This is because the analysis of L-GREEDY uses weights on vertices which are not affected by edge departures, and the analysis of AMP is based on an upper bound over the number of type k edges, which still holds under edge departures. We thus focus on obtaining stronger lower bounds in this model (also included in Table 2.1). We begin by observing that the bound of 3/2 of the competitive ratio in the edge arrival model for k 2 f2, 3g still holds for the limited departure model, in which the adversary is stronger. Hence, the smallest interesting value for k in this model is k = 4, for which we provide the following specific lower bound. The proof will also provide some intuition about the adversarial argument for general k.
Theorem 2.11. The competitive ratio of online matching with k edge-recourse in the limited departure model is at least 10/7 for k = 4.
Proof. We will prove the theorem by applying a game between the online algorithm and the adversary. In particular, the adversary will enforce arrivals and deletions of edges in such a way that, at every moment in time, the symmetric difference between the matching produced by the algorithm and the optimal matching consists only of augmenting paths. In particular, this symmetric difference will have no alternating cycles or alternating paths of even length. Any such augmenting path can be represented as a string of integers in f0, 1, . . . , kg, which is precisely the type of this path. Note that for an augmenting path, this string begins and ends with 0. We can thus think of the above-defined symmetric differ-ence as a collection of strings, which in turn allows us to define the game between the algorithm and the adversary over this collection of strings as opposed to defining it over the actual graph. Whenever the algorithm applies an augmenting path, this translates into the in-crement of all edge types of the corresponding string, for example the string 01210 becomes 12321. The adversary will respond to this augmentation by a combination of the following three types of operations.
— The adversary may append 0’s to both ends of a string, for example 101 ! 01010. To do so, the adversary releases two new edges (of type 0). Each edge is incident with only one endpoint of the path described by the string, and is not incident with any other edge in the current graph.

Cyclic Schedules and the LP Formulation

In this section we show that for a given end guarantee L, there is a cyclic schedule that is optimal for L. This will allow us to focus exclusively on this class of schedules, which we will later analyze by our technique on LP. To this end, we first define a property that will be useful in the proof.
Definition 4.2. A schedule X = ((xi, pi))i2[1,m] is called normalized if for each i 2 [1, m], ‘pi ,Ti 1(X)(X) ‘q,Ti 1(X)(X), for all q 6= pi. Informally, a normalized schedule X assigns, at each time, a contract to the prob-lem that has been worked the least among all problems up to that time. The follow-ing lemma shows that for every L there exists an optimal normalized schedule. Its proof expands the property that is already known, namely that there exists a nor-malized schedule that has optimal acceleration ratio [47].
Lemma 4.3. For every schedule X feasible for L, there exists a normalized schedule X0 feasible for L such that r(X0) r(X) and T(X0) T(X).
Proof. Suppose that X is not normalized for the i-th contract. Then, there exists a problem q 6= pi such that ‘q,Ti 1(X)(X) < ‘pi ,Ti 1(X)(X). Consider X0 that is derived from X as follows: X0 is identical to X for the first i 1 contracts and its i contract is (xi, q). Furthermore, for all j > i, the j-th contract in X is (xj, r), where r = pj, if pj 2/ fpi, qg, r = q, if p j = pi, and r = pi, if pj = q. In words, X0 swaps the problem assignments of contracts for pi and q for all such contracts scheduled after time Ti 1(X) in X. Note that T(X0) = T(X). We first argue that if X is feasible for L, then so is X0. We consider two cases: if a contract for q is scheduled after time Ti(X) in X, then both pi, q have completed a contract of length at least L in both X and X0, hence X0 is feasible for L. Otherwise, since X is feasible for L, X0 clearly completes a contract of length at least L for pi, and remains to argue the same about q. This is indeed the case, since for X to be feasible, it must be that there is a contract of length at least L for q that was scheduled prior to time Ti 1(X) in X, hence one such contract for q is in X0 as well.
It remains to show that r(X0) r(X). Again we consider two cases, depending on whether a contract for q is scheduled after time Ti(X) in X. Suppose first that this is not the case, then we observe that an interruption t Ti that occurs right before a contract for pi in X corresponds to an interruption t that occurs right before a contract for q in X0. Since maxf‘pi ,t(X), ‘q,t(X)g maxf‘pi ,t(X 0), ‘q,t(X0) g, it follows that in this case r(X0) r(X). It remains to consider the case that there is a contract for q that is scheduled after time Ti(X) in X; let Tq0 denote the end time of this con-tract. From the previous argument, interruptions that occur prior to Tq0 contribute to the acceleration ratio of X at least as much as the corresponding interruptions in X0. Moreover, for all interruptions t with t Tq0 have the same contribution in X as in X0, since maxi2[0,…,n 1] ‘i,t(X) = maxi2[0,…,n 1] ‘i,t(X0). Thus, it follows that in this case as well r(X0) r(X) and the proof is completed.

Table of contents :

1 Introduction 
1.1 Online Computation
1.1.1 Competitive Analysis
1.1.2 Techniques in Design and Analysis of Online Algorithms
1.2 Online Computation with Recourse
1.2.1 Online Matching with Recourse
1.3 Other Performance Measures
1.3.1 The Linear Search Problem
1.3.2 The Discovery Ratio
1.3.3 An Application from Artificial Intelligence
1.4 Online Computation with Advice
1.4.1 A New Model with Untrusted Advice
1.4.2 Online Bidding with Untrusted Advice
1.5 Summary of the Thesis
2 Online Maximum Matching with Recourse 
2.1 Introduction
2.1.1 RelatedWork
2.1.2 Contributions
2.1.3 Preliminaries
2.2 Online matching in the edge arrival model
2.2.1 The Algorithm AMP
2.2.2 The Algorithm GREEDY
2.2.3 The algorithm L-GREEDY
2.2.4 Lower Bound on the Competitive Ratio of Deterministic Algorithms
2.2.5 Comparing the Algorithms L-GREEDY and AMP
2.3 Online Matching in the Edge Arrival/Departure Model
2.4 Conclusion
3 Searching on the Line Using Discovery Ratio 
3.1 Introduction
3.1.1 RelatedWork
3.1.2 Contribution
3.1.3 Preliminaries
3.2 Strategies of Optimal Discovery Ratio in S
3.3 The Discovery Ratio of Competitively Optimal Strategies
3.3.1 Properties of Competitively Optimal Strategies
3.3.2 Discovery Ratio of Strategies in S9
3.3.3 On the Uniqueness of Strategies with Optimal Discovery Ratio
3.4 Computational Evaluation
3.5 Conclusion
4 Contract Scheduling with End Guarantees 
4.1 Introduction
4.1.1 Contribution
4.1.2 Preliminaries
4.2 Cyclic Schedules and the LP Formulation
4.3 Obtaining an Optimal Schedule
4.4 Computational Evaluation
4.5 Conclusion
5 Online Bidding with Untrusted Advice 
5.1 Introduction
5.1.1 Online Computation with Advice
5.1.2 A New Model with Untrusted Advice
5.1.3 Online Bidding with Untrusted Advice
5.1.4 Preliminaries
5.2 Identifying a Pareto-optimal Bidding Strategy
5.2.1 Algorithm Overview
5.2.2 Phase 1: Identifying a dominant strategy X m ,u in Sm,u
5.2.3 Phase 2: Identifying an optimal strategy X u
5.3 Conclusion
6 Conclusion
6.1 Summary of Results
6.2 What Next?

GET THE COMPLETE PROJECT