Randomized algorithm for the k-server problem on decomposable spaces

We study the randomized k-server problem on metric spaces consisting of widely separated subspaces. We give a method which extends existing algorithms to larger spaces with the growth rate of the competitive quotients being at most O(logk). This method yields o(k)-competitive algorithms solving the randomized k-server problem for some special underlying metric spaces, e.g. HSTs of “small” height (but unbounded degree). HSTs are important tools for probabilistic approximation of metric spaces.     

The Reception of Frege''sBegriffsschrift

The topic of the paper is the public reception of Gottlob Frege's (1848–1925)Begriffsschriftright after its publication in 1879. According to a widespread conception, the reception of the book was “unfavorable” and even “tragic.” The aim of the paper is to correct this exaggerated and even false view. The arguments are based, above all, on the six journal reviews of Frege's book in 1879 and 1880, and on Leonhard Rabus's critical comment on it in his bookDie neuesten Bestrebungen auf dem Gebiete der Logik bei den Deutschen und die logische Frage(1880). The conclusion is that it is misleading to regard the reception of Frege's first work as unfair and hostile even though it is apparent thatsomereviewers of the book were rather poorly motivated to comment on theBegriffsschrift.Copyright 1998 Academic Press.Der Gegenstand dieses Beitrags ist die öffentliche Rezeption von Gottlob Freges (1848–1925)Begriffsschriftnach ihrer Publikation 1879. Nach einer weitverbreiteten Auffassung war die Rezeption “ungünstig,” sogar “tragisch.” Ziel des Beitrags ist es zu zeigen, dass solche Interpretationen überspannt, teilweise sogar falsch sind. Der Verfasser gründet seine Behauptung vor allem auf die Rezensionen, die in verschiedenen Zeitschriften in den Jahren 1879 und 1880 erschienen sind. Er benutzt auch den Kommentar von Leonhard RabusDie neuesten Bestrebungen auf dem Gebiete der Logik bei den Deutschen und Die logische Frage(1880). Die Untersuchung kommt zu dem Schluss, dass, obwohl offensichtlicheinigeRezensenten dem Buch eher ablehnend gegenüberstanden, es irreführend ist, von einer ungerechtfertigten oder abweisenden Rezeption der Fregeschen Begriffsschrift zu sprechenCopyright 1998 Academic Press.AMS subject classification: 00A30, 01A55, 03A05     

An Oblivious Routing Algorithm for Two-Dimensional Meshes of Constant Queue-Size

This paper shows an important exception to the common perception that three-dimensional meshes are more powerful than two-dimensional ones. Let N be the total number of processors. Then permutation routing over three-dimensional mesh computers needs Θ(N^2/3) steps while it takes Θ(N^1/2) steps over two-dimensional ones under the following conditions: (1) The path of each packet must be determined solely by its initial position and destination, i.e., the algorithm must be oblivious. (2) Each path must be “elementary,” i.e., it must be shortest and as straight as possible. Thus the conditions, under which, somewhat surprisingly, three-dimensional meshes are significantly less powerful than two-dimensional ones for the fundamental network operation, are quite reasonable in practice.     

Mixed expansion formula for the rectangular Schur functions and the affine Lie algebra

Formulas are obtained that express the Schur S-functions indexed by Young diagrams of rectangular shape as linear combinations of “mixed” products of Schur's S- and Q-functions. The proof is achieved by using representations of the affine Lie algebra of type . A realization of the basic representation that is of “”-type plays the central role.     

A general framework of compactly supported splines and wavelets

Let {V_k} be a nested sequence of closed subspaces that constitute a multiresolution analysis of L²( ). We characterize the family Φ = {φ} where each φ generates this multiresolution analysis such that the two-scale relation of φ is governed by a finite sequence. In particular, we identify the ε Φ that has minimum support. We also characterize the collection Ψ of functions η such that each η generates the orthogonal complementary subspaces W_k of V_k, . In particular, the minimally supported ψ ε Ψ is determined. Hence, the “B-spline” and “B-wavelet” pair (, ψ) provides the most economical and computational efficient “spline” representations and “wavelet” decompositions of L² functions from the “spline” spaces V_k and “wavelet” spaces W_k, k . A very general duality principle, which yields the dual bases of both {(·−j):j and {η(·−j):j } for any η ε Ψ by essentially interchanging the pair of two-scale sequences with the pair of decomposition sequences, is also established. For many filtering applications, it is very important to select a multiresolution for which both and ψ have linear phases. Hence, “non-symmetric” and ψ, such as the compactly supported orthogonal ones introduced by Daubechies, are sometimes undesirable for these applications. Conditions on linear-phase φ and ψ are established in this paper. In particular, even-order polynomial B-splines and B-wavelets φ_m and ψ_m have linear phases, but the odd-order B-wavelet only has generalized linear phases.     

Dense trees: a new look at degenerate graphs

Dense trees are undirected graphs defined as natural extensions of trees. They are already known in the realm of graph coloring under the name of k-degenerate graphs. For a given integer k1, a k-dense cycle is a connected graph, where the degree of each vertex is greater than k. A k-dense forest F=(V,E) is a graph without k-dense cycles as subgraphs. If F is connected, then is a k-dense tree. 1-dense trees are standard trees. We have |E|k|V|−k(k+1)/2. If equality holds F is connected and is called a maximal k-dense tree. k-trees (a subfamily of triangulated graphs) are special cases of maximal k-dense trees.We review the basic theory of dense trees in the family of graphs and show their relation with k-trees. Vertex and edge connectivity is thoroughly investigated, and the role of maximal k-dense trees as “reinforced” spanning trees of arbitrary graphs is presented. Then it is shown how a k-dense forest or tree can be decomposed into a set of standard spanning trees connected through a common “root” of k vertices. All sections include efficient construction algorithms. Applications of k-dense trees in the fields of distributed systems and data structures are finally indicated.     

Nearly monotone and nearly convex approximation by smooth splines in ,

Given a monotone or convex function on a finite interval we construct splines of arbitrarily high order having maximum smoothness which are “nearly monotone” or “nearly convex” and provide the rate of -approximation which can be estimated in terms of the third or fourth (classical or Ditzian–Totik) moduli of smoothness (for uniformly spaced or Chebyshev knots). It is known that these estimates are impossible in terms of higher moduli and are no longer true for “purely monotone” and “purely convex” spline approximation.     

Reflection sieve obstructions in finite groups of type dn

In [4] we constructed certain homology representations of a finite group G of type A_n, B_n or C_n, and showed that these representations can be used to sift out the reflection compound characters of G. In the present note, we show that for a group G of type D_n, each reflection compound character π^(k), 2 k n − 2, determines a unique “obstruction” character θ^(k), which occurs with positive multiplicity in every homology representation containing π^(k).     

Moment methods in two point Padé approximation

In the separable Hilbert space (H, ·, ·) the following “operator moment problem” is solved: given a complex sequence (c_k)_{k ε Z} generated by a meromorphic function f, find T ε B(H) and u₀ ε H such that T^ku₀, u₀ = c_k (k ε Z). If the sequence (c_k)_{k ε Z} is “normal,” an adapted form of Vorobyev's method of moments yields a sequence of two point Padé approximants to f. A sufficient condition for convergence of this sequence of approximants is given.     

Self-intersection local time for Gaussian ′( )-processes: Existence, path continuity and examples

In this paper we develop a criterion for existence or non-existence of self-intersection local time (SILT) for a wide class of Gaussian ′( ^d)-valued processes, we show that quite generally the SILT process has continuous paths, and we give several examples which illustrate existence of SILT for different ranges of dimensions (e.g., d ≤ 3, d ≤ 7 and 5 ≤ d ≤ 11 in the Brownian case). Some of the examples involve branching and exhibit “dimension gaps”. Our results generalize the work of Adler and coauthors, who studied the special case of “density processes” and proved that SILT paths are cadlag in the Brownian case making use of a “particle picture” approximation (this technique is not available for our general formulation).     

CDS simulation and pattern formation of phase separation

Several properties of the generation and evolution of phase separating patterns for binary material studied by CDS model are proposed. The main conclusions are (1) for alloys spinodal decomposition, the conceptions of “macro-pattern” and “micropattern” are posed by “black-and- white graph” and “gray-scale graph” respectively. We find that though the four forms of map f that represent the self-evolution of order parameter in a cell (lattice) are similar to each other in “macro-pattern”, there are evident differences in their micro-pattern, e.g., some different fine netted structures in the black domain and the white domain are found by the micro-pattern, so that distinct mechanical and physical behaviors shall be obtained. (2) If the two constitutions of block copolymers are not symmetric (i.e. r ≠ 0.5), a pattern called “grain-strip cross pattern” is discovered, in the 0.43 <r <0.45.     

An -module structure of the cokernel of the second Johnson homomorphism

The Johnson homomorphisms τ_k (k1) give Abelian quotients of a series of certain subgroups of the mapping class group of a surface. Morita determined the rational image of the second Johnson homomorphism τ₂. In this paper, we study the structure of the torsion part of the cokernel of τ₂. First, we determine the rank of the cokernel over . Although we do it first by computing explicitly, later we improve the proof, using the Birman–Craggs homomorphism, obtained by the classical Rohlin invariant of homology 3-spheres. Since τ₂ is equivariant with respect to the action of the mapping class group, Im τ₂ is -invariant and hence acts on the cokernel. Moreover, computing this action explicitly, we show that the action reduces to that of the finite symplectic group .     

Permutations with Low Discrepancy Consecutive k-sums

Consider the permutation π=(π₁,…, π_n) of 1,2,…, n as being placed on a circle with indices taken modulo n. For given kn there are n sums of k consecutive entries. We say the maximum difference of any consecutive k-sum from the average k-sum is the discrepancy of the permutation. We seek a permutation of minimum discrepancy. We find that in general the discrepancy is small, never more than k+6, independent of n. For g= gcd(n,k)>1, we show that the discrepancy is . For g=1 it is more complicated. Our constructions show that the discrepancy never exceeds k/2 by more than 9 for large n, while it is at least k/2 for infinitely many n.We also give an analysis for the easier case of linear permutations, where we view the permutation as written on a line. The analogous discrepancy is at most 2 for all n,k.     

Fuzzy Relation Equations for Compression/Decompression Processes of Colour Images in the RGB and YUV Colour Spaces

We use particular fuzzy relation equations for compression/decompression of colour images in the RGB and YUV spaces, by comparing the results of the reconstructed images obtained in both cases. Our tests are made over well known images of 256×256 pixels (8 bits per pixel in each band) extracted from Corel Gallery. After the decomposition of each image in the three bands of the RGB and YUV colour spaces, the compression is performed using fuzzy relation equations of “min - →_t” type, where “t” is the Lukasiewicz t-norm and “→_t” is its residuum. Any image is subdivided in blocks and each block is compressed by optimizing a parameter inserted in the Gaussian membership functions of the fuzzy sets, used as coders in the fuzzy equations. The decompression process is realized via a fuzzy relation equation of max-t type. In both RGB and YUV spaces we evaluate and compare the root means square error (RMSE) and the consequentpeak signal to noise ratio (PSNR) on the decompressed images with respect to the original image under several compression rates.     

On a decision rule using dichotomies for identifying the nonnegligible parameter in certain linear models

Consider the class of linear models (with uncorrelated observation, each having variance σ²), in which it is known that at most k (location) parameters are negligible, but it is not known which are negligible. The problem is to identify the nonnegligible parameters. In this paper, for k = 1, and under certain restrictions on the model, a technique is developed for solving this problem, which has the feature of requiring (in an information theoretic sense) the minimum amount of computation. (It can “search through” 2^m objects, using m “steps.”) The technique consists of dichotomizing the set of parameters (one known subset possibly containing the nonnegligible element, and the other not), using chi-square variables. A method for computing the probability that the correct parameter is identified, is presented, and an important application to factorial search designs is established.     

Nonmonotone, nonlinear evolution inclusions

In this paper, we consider nonlinear evolution problems, defined on an evolution triple of spaces, driven by a nonmonotone operator, and with a perturbation term which is multivalued. We prove existence theorems for the cases of a convex and of a nonconvex valued perturbation term which is defined on all of T × H or only on T × X with values in H or even in X^* (here X - H - X^* is the evolution triple). Also, we prove the existence of extremal solutions, and for the “monotone” problem we have a strong relaxation theorem. Some examples of nonlinear parabolic problems are presented.     

Passage to the limit in Proposition I, Book I of Newton's Principia

The purpose of this paper is to analyze the way in which Newton uses his polygon model and passes to the limit in Proposition I, Book I of his Principia. It will be evident from his method that the limit of the polygon is indeed the orbital arc of the body and that his approximation of the actual continuous force situation by a series of impulses passes correctly in the limit into the continuous centripetal force situation. The analysis of the polygon model is done in two ways: (1) using the modern concepts of force, linear momentum, linear impulse, and velocity, and (2) using Newton's concepts of motive force and quantity of motion. It should be clearly understood that the term “force” without the adjective “motive,” is used in the modern sense, which is that force is a vector which is the time rate of change of the linear momentum. Newton did not use the word “force” in this modern sense. The symbol F denotes modern force. For Newton “force” was “motive force,” which is measured by the change in the quantity of motion of a body. Newton's “quantity of motion” is proportional to the magnitude of the modern vector momentum. Motive force is a scalar and the symbol F_m is used for motive force.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

Generalized rational approximation in interpolating subspaces of Lp(μ)

We extend the geometric approach of Cheney and Loeb in [2] to the problem of approximation in L_p(μ) by “admissable” generalized rational functions. We obtain a characterization for locally best approximations and find the interpolating condition sufficient for their local unicity. Our results are comparable to those for the linear approximation problem as investigated by Singer and Ault, Deutsch, Morris, and Olson.