AbstractThis note addresses the input and output of intervals in the sense of intervalarithmetic and interval constraints. The most obvious, and so far most widely usednotation, for intervals has drawbacks that we remedy with a new notation that wepropose to call factored notation. It is more compact and allows one to ﬁnd a goodtrade-oﬀ between interval width and ease of reading. We describe how such a trade-oﬀ can be based on the information yield (in the sense of information theory) of thelast decimal shown. 1 Introduction Once upon a time, it was a matter of professional ethics among computers never to writea meaningless decimal. Since then computers have become machines and thereby lost anyform of ethics, professional or otherwise. The human computers of yore were helped intheir ethical behaviour by the fact that it took eﬀort to write spurious decimals. Now thesituation is reversed: the lazy way is to use the default precision of the I O library function.As a result it is common to see ﬁfteen decimals, all but three of which are meaningless.Of course interval arithmetic is not guilty of such negligence. After all, the very raisond’ˆetre of the subject is to be explicit about the precision of computed results. Yet, eveninterval arithmetic is plagued by phoney decimals, albeit in a more subtle way. Just as con-ventional computation often needs more care in the presentation of computational results,the most obvious interval notation with default precision needs improvement.As a bounded interval has two bounds, say, l and u, the most straightforward notationis something like [l,u]. Written like this, it may not be immediately obvious what is wrongwith writing it that way. But when confronted with a real-life consequence
Hansen @cite_3 , @cite_5 , and Kearfott @cite_1 opt for the straightforward @math notation. Hansen mostly presents bounds with few digits, but for instance on page 178 we find @math demonstrating the problems addressed here.
@cite_5 @cite_1 @cite_3
2000931246 2508647357 2010193278 2034680223
Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say O(n1+Δ) bits. There is an inherent tradeoff between the sparsity parameter Δ and the stretch function f of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that when Δ ≥ 1 3 there are schemes with constant additive stretch (distance d is stretched to at most f(d) = d + O(1)), and recent results of Abboud and Bodwin show that when Δ In this paper we show that the lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that characterize the asymptotic behavior of the optimal stretch function f for sparsity parameter Δ ∈ (0,1 3). Specifically, for any integer k ≥ 2, any compression scheme with size [EQUATION] has a sublinear additive stretch function f: f(d) = d + Ω(d1−1 k). This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's (1 + ϵ, β)-spanners have an essentially optimal tradeoff between Δ, ϵ, and β, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of (1 + ϵ, O(k ϵ)k−1)-spanners with size [EQUATION], where hk Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of (β, ϵ)-hopsets, matching Elkin and Neiman's construction (2016), and lower bounds on shortcutting sets for digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least 2γ + 1. One consequence is that 's (2010) additive O(γ)-spanners with size [EQUATION] cannot be improved in the exponent. Let Fk(n,m) be a random k-SAT formula on n variables formed by selecting uniformly and independently m out of all possible k-clauses. It is well-known that for r ≥ 2k ln 2, Fk(n,rn) is unsatisfiable with probability 1-o(1). We prove that there exists a sequence tk = O(k) such that for r ≥ 2k ln 2 - tk, Fk(n,rn) is satisfiable with probability 1-o(1).Our technique yields an explicit lower bound for every k which for k > 3 improves upon all previously known bounds. For example, when k=10 our lower bound is 704.94 while the upper bound is 708.94. Let G = (V,E) be a weighted undirected graph with |V | = n and |E| = m. An estimate ( u,v ) of the distance ( u,v ) in G between u, v V is said to be of stretch t iff ( u,v ) ( u,v ) t ? ( u,v ). The most efficient algorithms known for computing small stretch distances in G are the approximate distance oracles of [16] and the three algorithms in [9] to compute all-pairs stretch t distances for t = 2, 7 3, and 3. We present faster algorithms for these problems. For any integer k 1, Thorup and Zwick in [16] gave an O(kmn^ 1 k ) algorithm to construct a data structure of size O(kn^ 1+1 k ) which, given a query (u, v) V ? V , returns in O(k) time, a 2k - 1 stretch estimate of ( u,v ). But for small values of k, the time to construct the oracle is rather high. Here we present an O(n^2 log n) algorithm to construct such a data structure of size O(kn^ 1+1 k ) for all integers k 2. Our query answering time is O(k) for k 2 and (log n) for k = 2. We use a new generic scheme for all-pairs approximate shortest paths for these results. This scheme also enables us to design faster algorithms for allpairs t-stretch distances for t = 2 and 7 3, and compute all-pairs almost stretch 2 distances in O(n^2 log n) time.