Algorithm Theory - SWAT 2010

136 Z. Xu and B. Rodrigues We next prove that both E(Q) and E(W ) include Et+−1 but are disjoint with Et−−1. On one hand, from e ∈ E(Ft) \\ Et+ and Et+−1 ⊆ Et+ we know e ∈/ Et+−1. From Et+−1 ⊆ E(Ft−1) and Q = (Ft−1 ∪ {et}) \\ {e} we obtain Et+−1 ⊆ E(Q). Since Et+−1 ⊆ E(Ft−1) and e ∈/ Et+−1, which implies Et+−1 ⊆ E(Ft−1) \\ {e}, we obtain Et+−1 ⊆ W . On the other hand, since E(Ft−1) is disjoint with Et−−1 and et ∈/ Et−−1, we have E(Q) is disjoint with Et−−1. Since Et−−1 is disjoint with E(C∗), by (3) we have Et−−1 ⊆ Et−, which implies e ∈/ Et−−1 because e ∈/ Et−. Notice E(Ft−1) is disjoint with Et−−1. Thus W , which is a subset of E(Ft−1)∪{e }, must be disjoint with Et−−1. It is now possible to prove that at least one of Q and W is an (Et+−1, Et−−1)- DRSF wrt (G, D) with length shorter than (Ft−1). From (2) and (3), it can be seen that Et+−1 ⊆ Et+ and Et−−1 ⊆ Et−. Thus both Ft and Ft are (Et+−1, Et−−1)- DRSFs wrt (G, D). From (4), since E(Ft−1) contains et but not et, we obtain Ft−1 = Ft \\{et}∪{et}. Since both Ft and Ft−1 are (Et+−1, Et−−1)-DRSFs, by state- ments (ii) and (iii) of Lemma 4 and by Proposition 2.5 of [16], there must exist an edge x ∈ [E(Ft )\\(E(Ft)\\{et})], such that (Ft \\{x})∪{et} is an (Et+−1, Et−−1)- DRSFs. From (7), it is easily verified that [E(Ft ) \\ (E(Ft) \\ {et})] ⊆ {et, e }. By (5) and (6), we conclude that at least one of Q and W is an (Et+−1, Et−−1)-DRSF. If W is an (Et+−1, Et−−1)-DRSF, then we have already shown (W ) < (Ft−1). Consider the case when W is not, but Q is, an (Et+−1, Et−−1)-DRSF. We now show e ∈ E(V (Tb)) by contradiction. Suppose e is not in E(V (Tb)). Then, since E(Ft−1) ∩ E(V (Tb)) = {et}, by (8) we know E(Ft ) \\ {et} has no intersection with E(V (Tb)). Notice et ∈ E(V (Tb)) and Tb contains no depot. Since Ft is an (Et+−1, Et−−1)-DRSF, by (6), W must be an (Et+−1, Et−−1)-DRSF, leading to a contradiction. Hence, e ∈ E(V (Tb)). Thus, since E(Ft−1) \\ {et} has no intersection with E(V (Tb)) and Tb contains no depot, (Ft−1 \\ {et}) ∪ {e } must be an (Et+−1, Et−−1)-DRSF wrt (G, D). More- over, from e ∈/ Et− and (3) we know e ∈ E(C∗). Since e is different from et, we know e ∈/ E(Ft−1), implying (et) ≤ (e ) by definition of et. Since (e ) < (e), we obtain (et) < (e). Notice Q = (Ft−1 ∪ {et}) \\ {e}. Thus (Q) < (Ft−1). By the argument above, Ft−1 cannot be a minimum (Et+−1, Et−−1)-DRSF, which contradicts to the fact that Ft−1 satisfies constraint (iii) of Lemma 5 for i = t − 1. Therefore, Ft is a minimum (Et+, Et−)-DRSF wrt (G, D), and sat- isfies (iii) of Lemma 5 for i = t. Lemma 10. Ft defined in (4) satisfies (iv) of Lemma 5 for i = t, i.e., (Ft) ≤ [ (C∗) − C∈C∗ (emax(C))]. Proof. Notice that Et+ ⊆ E(C∗) and Et− ∩ E(C∗) is empty by Lemma 7 and Lemma 8. Thus, deleting emax(C) from each tour C of C∗ constitutes an (Et+, Et−) -DRSF wrt (G, D), which has a length not longer than (Ft) due to Lemma 9. Hence, Ft is not longer than [ (C∗) − C∈C∗ (emax(C))]. Lemma 11. Ft defined in (4) satisfies (v) of Lemma 5 for i = t, i.e., At is a minimal auxiliary edge subset of Ft wrt C∗, with (At) ≤ (nA − t) (emax(C∗)).

A 3/2-Approximation Algorithm for MDMTSP 137 Proof. To prove that At is a minimal auxiliary edge subset of Ft wrt C∗, notice that At = At−1 \\{et} and that At−1 and Ft−1 satisfy (v) of Lemma 5 for i = t−1. For the edge et = (a, b), its endpoints a and b must belong to two different tours of C∗, which are denoted by Ca and Cb containing a and b respectively. Since et ∈ At−1, vertices representing Ca and Cb must belong to the same G[C ∗ ] G[C ∗ ] connected component denoted by U of . Therefore, splits U At−1 At−1 \\{et } into two connected components Ua and Ub, which contain vertices representing Ca and Cb respectively. Since At−1 is minimal, et is not redundant. Thus, both G[C∗] Ua and Ub contain an odd number of odd vertices of ) . Since deleting E(Ft−1 et = (a, b) from Ft−1 changes parities of degrees of vertices a and b only, both Ua G[C∗] and Ub contain an even number of odd vertices of )\\{et } . Therefore, At is E(Ft−1 winrtGCE[C∗(∗.F]St)inacsetehteybehloanvegsintoGaE[Ct(∗Fo] tu−r1 ∗ an auxiliary edge subset of Ft−1 \\ {et} of C } , vertices of G[C∗] have the same parities . )\\{et Thus, At is also an auxiliary edge subset of Ft wrt C∗. Moreover, by the argument above, vertices representing Ca and Cb are the G[C ∗ ] GE[C(∗F] t). only vertices that have different parities in and in Since they E (Ft−1 ) GwE[rCt(∗F]Ct)∗,. are not connected by any path in and since At−1 is minimal, At must be a minimal auxiliary forest of Ft To prove (Ai) ≤ (nA − i) (emax(C∗)), consider every edge e = (u, v) of A∗, where u is the parent of v in F ∗. By Lemma 2, the optimal solution C∗ has a unique tour Cv that contains v, and Cv has an edge e such that (F ∗ \\ {(u, v)}) ∪ {e } is a DRSF wrt (G, D) with length not shorter than (F ∗), which implies (u, v) ≤ (e ). Therefore, (u, v) ≤ (emax(Cv)) ≤ (emax(C∗)). (9) Since Ai is a subset of A∗ and |Ai| = nA − i, for 0 ≤ i ≤ nA, we obtain (Ai) ≤ (nA − i) (emax(C∗)). Thus Ft satisfies (v) of Lemma 5 for i = t. As Lemmas 7–11 complete the induction, Lemma 5 is proved. Using Lemma 5, Lemma 3 now follows: Proof of Lemma 3. Consider a minimal auxiliary edge subset A∗ of F ∗ wrt C∗. If A∗ is empty, F ∗ satisfies conditions (i) and (ii) in Lemma 3 , and so Lemma 3 is proved. Otherwise, A∗ is not empty. By definition of A∗, since C∗ contains exactly k tours, we know |A∗| ≤ k − 1. Adopting notation defined in Lemma 5, since A∗ is not empty, 2 ≤ k and 1 ≤ nA. By Lemma 5, there exists a pair of disjoint edge subsets (En+A−1, En−A−1) satisfying constraints (i)–(v) of Lemma 5 for i = nA−1. Taking E+ = En+A−1, E− = AnA−1, F = FnA−1, and A= A=nAn−A1−, w1e≤ca|nA∗v|e−rif1y Lemma 3 as follows. By constraint (i) of Lemma 5, |E+| ≤ k−2 and E+ ⊆ E \\ F ∗. By definition of AnA−1, we know E− ⊆ F ∗ and |E−| ≤ k − 1. Due to constraints (iii) and (iv) of Lemma 5, F = (F ∗ \\ E−) ∪ E+ is a DRSF wrt (G, D) with length not longer

138 Z. Xu and B. Rodrigues than [ (C∗) − (emax(C∗))]. By cworntstCr∗aiwntith(vl)enogf tLhenmomt alo5n,geArntAh−a1n is a minimal auxiliary edge subset of FnA−1 (emax (C ∗ )). Thus, F satisfies conditions (i) and (ii) in Lemma 3, and so, Lemma 3 is true. References 1. Arkin, E.M., Hassin, R., Levin, A.: Approximations for minimum and min-max vehicle routing problems. Journal of Algorithms 59(1), 1–18 (2006) 2. Christofides, N.: Worst-case analysis of a new heuristic for the travelling sales- man problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University (1976) 3. Eiselt, H.A., Gendreau, M., Laporte, G.: Arc routing problems, part i: The chinese postman problem. Operations Research 43(2), 231–242 (1995) 4. Eiselt, H.A., Gendreau, M., Laporte, G.: Arc routing problems, part ii: The rural postman problem. Operations Research 43(3), 399–414 (1995) 5. Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, New York (1979) 6. Giosa, I.D., Tansini, I.L., Viera, I.O.: New assignment algorithms for the multi- depot vehicle routing problem. Journal of the Operational Research Society 53(9), 977–984 (2002) 7. Lim, A., Wang, F.: Multi-depot vehicle routing problem: a one-stage approach. IEEE Transactions on Automation Science and Engineering 2(4), 397–402 (2005) 8. Malik, W., Rathinam, S., Darbha, S.: An approximation algorithm for a symmet- ric generalized multiple depot, multiple travelling salesman problem. Operations Research Letters 35(6), 747–753 (2007) 9. Papadimitriou, C.H., Steiglitz, K.: Approximation algorithms for the traveling salesman problem. In: Combinatorial Optimization: Algorithms and Complexity, pp. 410–419. Courier Dover Publications (1998) 10. Rathinam, S., Sengupta, R.: 3/2-Approximation Algorithm for a Generalized, Mul- tiple Depot, Hamiltonina Path Problem. Technical report, University of California, Berkeley (2007) 11. Rathinam, S., Sengupta, R.: 5/3-approximation algorithm for a multiple depot, ter- minal hamiltonian path problem. Technical report, University of California, Berke- ley (2007) 12. Rathinam, S., Sengupta, R., Darbha, S.: A resource allocation algorithm for multi- vehicle systems with non holonomic constraints. IEEE Transactions on Automation Sciences and Engineering 4(1), 98–104 (2006) 13. Rathinama, S., Senguptab, R.: 3/2-approximation algorithm for two variants of a 2-depot hamiltonian path problem. Operations Research Letters 38(1), 63–68 (2010) 14. Renaud, J., Laporte, G., Boctor, F.F.: A tabu search heuristic for the multi- depot vehicle routing problem. Computers and Operations Research 23(3), 229–235 (1996) 15. Rosenkrantz, D.J., Stearns, R.E., Lewis, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing 6(3), 563–581 (1977) 16. Wolsey, L.A., Nemhauser, G.L.: Integer and Combinatorial Optimization, ch. sec- tion III.3, p. 664. Wiley-Interscience, Hoboken (1988)

Minimum and Maximum against k Lies Michael Hoffmann1, Jiˇr´ı Matouˇsek2,1, Yoshio Okamoto3, , and Philipp Zumstein1 1 Institute of Theoretical Computer Science, Department of Computer Science, ETH Zurich, Switzerland {hoffmann,matousek,zuphilip}@inf.ethz.ch 2 Department of Applied Mathematics and Institute for Theoretical Computer Science (ITI), Charles University, Prague, Czech Republic [email protected] 3 Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Japan [email protected] Abstract. A neat 1972 result of Pohl asserts that 3n/2 − 2 com- parisons are sufficient, and also necessary in the worst case, for finding both the minimum and the maximum of an n-element totally ordered set. The set is accessed via an oracle for pairwise comparisons. More re- cently, the problem has been studied in the context of the R´enyi–Ulam liar games, where the oracle may give up to k false ans√wers. For large k, an upper bound due to Aigner shows that (k + O( k))n compar- isons suffice. We improve on this by providing an algorithm with at most (k + 1 + C)n + O(k3) comparisons for some constant C. The known lower bounds are of the form (k + 1 + ck)n − D, for some constant D, where c0 = 0.5, c1 = 23 = 0.71875, and ck = Ω(2−5k/4 ) as k → ∞. 32 1 Introduction We consider an n-element set X with an unknown total ordering ≤. The ordering can be accessed via an oracle that, given two elements x, y ∈ X, tells us whether x < y or x > y. It is easily seen that the minimum element of X can be found using n − 1 comparisons. This is optimal in the sense that n − 2 comparisons are not enough to find the minimum element in the worst case. One of the nice little surprises in computer science is that if we want to find both the minimum and the maximum, we can do significantly better than finding the minimum and the maximum separately. Pohl [8] proved that 3n/2 − 2 is the optimal number of comparisons for this problem (n ≥ 2). The algorithm first partitions the elements of X into pairs and makes a comparison in each pair. The minimum can then be found among the “losers” of these comparisons, while the maximum is found among the “winners.” Here we consider the problem of determining both the minimum and the max- imum in the case where the oracle is not completely reliable: it may sometimes Supported by Global COE Program “Computationism as a Foundation for the Sci- ences” and Grant-in-Aid for Scientific Research from Ministry of Education, Science and Culture, Japan, and Japan Society for the Promotion of Science. H. Kaplan (Ed.): SWAT 2010, LNCS 6139, pp. 139–149, 2010. c Springer-Verlag Berlin Heidelberg 2010

140 M. Hoffmann et al. give a false answer, but only at most k times during the whole computation, where k is a given parameter. We refer to this model as computation against k lies. Let us stress that we admit repeating the same query to the oracle several times, and each false an- swer counts as a lie. This seems to be the most sensible definition—if repeated queries were not allowed, or if the oracle could always give the wrong answer to a particular query, then the minimum cannot be determined. So, for example, if we repeat a given query 2k + 1 times, we always get the correct answer by majority vote. Thus, we can simulate any algorithm with a reliable oracle, asking every question 2k+1 times, but for the problems considered here, this is not a very efficient way, as we will see. The problem of finding both the minimum and the maxi√mum against k lies was investigated by Aigner [1], who proved that (k + O( k))n comparisons always suffice.1 We improve on this as follows. Theorem 1. There is an algorithm that finds both the minimum and the max- imum among n elements against k lies using at most (k + 1 + C)n + O(k3) comparisons, where C is a constant. Our proof yields the constant C reasonably small (below 10, say, at least if k is assumed to be sufficiently large), but we do not try to optimize it. Lower Bounds. The best known lower bounds for the number of comparisons necessary to determine both the minimum and the maximum against k lies have the form (k + 1 + ck)n − D, where D is a small constant and the ck are as follows: – c0 = 0.5, and this is the best possible. This is the result of Pohl [8] for a truthful oracle mentioned above. – c1 = 23 = 0.71875, and this is again tight. This follows from a recent work 32 by Gerbner, Pa´lvo¨lgyi, Patko´s, and Wiener [5] who determined the optimum number of comparisons for k = 1 up to a small additive constant: it lies between 87 n − 3 and 87 n + 12. This proves a conjecture of Aigner [1]. 32 32 – ck = Ω(2−5k/4) for all k, as was shown by Aigner [1]. The optimal constant c1 = 23 indicates that obtaining precise answers for k > 1 32 may be difficult. Related Work. The problem of determining the minimum alone against k lies was resolved by Ravikumar, Ganesan, and Lakshmanan [9], who proved that finding the minimum against k lies can be performed by using at most (k + 1)n − 1 comparisons, and this is optimal in the worst case. The problem considered in this paper belongs to the area of searching problems against lies and, in a wider context, it is an example of “computation in the presence of errors.” This field has a rich history and beautiful results. A prototype problem, still far from completely solved, is the R´enyi–Ulam liar game from the 1960s, where one wants to determine an unknown integer x between 1 and n, 1 Here and in the sequel, O(.) and Ω(.) hide only absolute constants, independent of both n and k.

Minimum and Maximum against k Lies 141 an oracle provides comparisons of x with specified numbers, and it may give at most k false answers. We refer to the surveys by Pelc [7] and by Deppe [2] for more information. 2 A Simple Algorithm Before proving Theorem 1, we explain a simpler algorithm, which illustrates the main ideas but yields a weaker bound. We begin with formulating a generic algorithm, with some steps left unspecified. Both the simple algorithm in this section and an improved algorithm in the next sections are instances of the generic algorithm. The generic algorithm 1. For a suitable integer parameter s = s(k), we arbitrarily partition the considered n-element set X into n/s groups X1, . . . , Xn/s of size s each.a 2. In each group Xi, we find the minimum mi and the maximum Mi. The method for doing this is left unspecified in the generic algorithm. 3. We find the minimum of {m1, . . . , mn/s} against k lies, and indepen- dently, we find the maximum of {M1, M2, . . . , Mn/s} against k lies. a If n is not divisible by s, we can form an extra group smaller than s and treat it separately, say—we will not bore the reader with the details. The correctness of the generic algorithm is clear, provided that Step 2 is im- plemented correctly. Eventually, we set s := k in the simple and in the improved algorithm. However, we keep s as a separate parameter, because the choice s := k is in a sense accidental. In the simple algorithm we implement Step 2 as follows. Step 2 in the simple algorithm 2.1. (Sorting.) We sort the elements of Xi by an asymptotically optimal sort- ing algorithm, say mergesort, using O(s log s) comparisons, and ignoring the possibility of lies. Thus, we obtain an ordering x1, x2, . . . , xs of the elements of Xi such that if all queries during the sorting have been answered correctly, then x1 < x2 < · · · < xs. If there was at least one false answer, we make no assumptions, except that the sorting algorithm does not crash and outputs some ordering. 2.2. (Verifying the minimum and maximum.) For each j = 2, 3, . . . , s, we query the oracle k+1 times with the pair xj−1, xj. If any of these queries returns the answer xj−1 > xj , we restart : We go back to Step 2.1 and repeat the computation for the group Xi from scratch. Otherwise, if all the answers are xj−1 < xj, we proceed with the next step. 2.3. We set mi := x1 and Mi := xs.

142 M. Hoffmann et al. Lemma 1 (Correctness). The simple algorithm always correctly computes the minimum and the maximum against k lies. Proof. We note that once the processing of the group Xi in the above algorithm reaches Step 2.3, then mi = x1 has to be the minimum. Indeed, for every other element xj , j ≥ 2, the oracle has answered k + 1 times that xj > xj−1, and hence xj cannot be the minimum. Similarly, Mi has to be the maximum, and thus the algorithm is always correct. Actually, at Step 2.3 we can be sure that x1, . . . , xs is the sorted order of Xi, but in the improved algorithm in the next section the situation will be more subtle. The next lemma shows, that the s√imple algorithm already provides an improvement of Aigner’s bound of (k + O( k))n. Lemma 2 (Complexity). The number of comparisons of the simple algorithm for s = k on an n-element set is (k + O(log k))n + O(k3). Proof. For processing the group Xi in Step 2, we need O(s log s)+(k+1)(s−1) = k2 + O(k log k) comparisons, provided that no restart is required. But since restarts may occur only if the the oracle lies at least once, and the total number of lies is at most k, there are no more than k restarts for all groups together. These restarts may account for at most k(k2 + O(k log k)) = O(k3) comparisons. Thus, the total number of comparisons in Step 2 is n (k2 + O(k log k)) + O(k3) = s (k + O(log k))n + O(k3). As we mentioned in the introduction, the minimum (or maximum) of an n- element set against k lies can be found using (k + 1)n − 1 comparisons, and so Step 3 needs no more than 2(k + 1)(n/s) = O(n) comparisons. (We do not really need the optimal algorithm for finding the minimum; any O((k + 1)n) algorithm would do.) The claimed bound on the total number of comparisons follows. 3 The Improved Algorithm: Proof of Theorem 1 In order to certify that x1 is indeed the minimum of Xi, we want that for every xj, j = 1, the oracle declares xj larger than some other element k + 1 times. (In the simple algorithm, these k + 1 comparisons were all made with xj−1, but any other smaller elements will do.) This in itself requires (k + 1)(s − 1) queries per group, or (k + 1)(n − n/s) in total, which is already close to our target upper bound in Theorem 1 (we note that s has to be at least of order k, for otherwise, Step 3 of the generic algorithm would be too costly). Similarly, every xj , j = s, should be compared with smaller elements k + 1 times, which again needs (k + 1)(n − n/s) comparisons, so all but O(n) comparisons in the whole algorithm should better be used for both of these purposes.