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 Distributedk-Server Problem—A Competitive Distributed Translator fork-Server Algorithms

We consider thek-server problem23in a distributed setting. Given a network ofnprocessors andkidentical mobile servers, requests for service appear at the processors and a server must reach the request point. In addition to modeling problems in computer networks wherekidentical mobile resources are shared by the processors of the network, this models a realistic situation where the transfer of information is costly and there is no central control that governs the behavior of servers that move around to satisfy requests for service. We give a general translator to transform any deterministic global-control competitivek-server algorithm into a distributed competitive one. As consequences we get poly(k)-competitive distributed algorithms for the line, trees, and the ring. In contrast to the global-control case where there arek-server algorithms with competitive ratio that depends solely onk, we have a lower bound of Ω(max{k, (1/D) ·(log n/log log n)}) on the competitive ratio of any distributedk-server algorithm, where 1/Dis the ratio between the cost to transmit a message and the cost to move a server over the same distance. We also give a distributed version of the Harmonic randomizedk-server algorithm.     

Traversing Layered Graphs Using the Work Function Algorithm

The work function algorithm (WFA) is an on-line algorithm that has been studied mostly in connection with thek-server problem, but can actually be used on a wide variety of on-line problems. Despite being a simple algorithm, WFA has proven to be difficult to analyze, and until recently few interesting results were known. We analyze the performance of the generalized work function algorithm, denoted α-WFA, for on-line traversal of layered graphs. We show that for layered graphs of widthkand any α>1, α-WFA achieves competitive ratio (α+1)(2α/(α−1))^k−1−α. This gives anO(k2^k)-competitive ratio for appropriate choice of α, improving the previous upper bound ofO(k³2^k).     

On-line k-Truck Problem and Its Competitive Algorithms

In this paper, based on the Position Maintaining Strategy (PMS for short), on-line scheduling of k-truck problem, which is a generalization of the famous k-server problem, is originally presented by our team. We proposed several competitive algorithms applicable under different conditions for solving the on-line k-truck problem. First, a competitive algorithm with competitive ratio 2k+1/ is given for any 1. Following that, if (c+1)/(c-1) holds, then there must exist a (2k-1)-competitive algorithm for k-truck problem, where c is the competitive ratio of the on-line algorithm about the relevant k-server problem. And then a greedy algorithm with competitive ratio 1+/, where lambda is a parameter related to the structure property of a given graph, is given. Finally, competitive algorithms with ratios 1+1/ are given for two special families of graphs.     

The k-Client Problem

Virtually all previous research in online algorithms has focused on single-threaded systems where only a single sequence of requests compete for system resources. To model multithreaded online systems, we define and analyze the k-client problem, a dual of the well-studied k-server problem. In the basic k-client problem, there is a single server and k clients, each of which generates a sequence of requests for service in a metric space. The crux of the problem is deciding which client's request the single server should service rather than which server should be used to service the current request. We also consider variations where requests have nonzero processing times and where there are multiple servers as well as multiple clients.We evaluate the performance of algorithms using several cost functions including maximum completion time and average completion time. Two of the main results we derive are tight bounds on the performance of several commonly studied disk scheduling algorithms and lower bounds of on the competitive ratio of any online algorithm for the maximum completion time and average completion time cost functions when k is a power of 2. Most of our results are essentially identical for the maximum completion time and average completion time cost functions.     

K-spaces property of product spaces

LetK be a class of spaces which are eigher a pseudo-opens-image of a metric space or ak-space having a compact-countable closedk-network. LetK′ be a class of spaces which are either a Fréchet space with a point-countablek-network or a point-G _δ k-space having a compact-countablek-network. In this paper, we obtain some sufficient and necessary conditions that the products of finitely or countably many spaces in the classK orK′ are ak-space. The main results are that

k-systems, k-networks and k-covers

The concepts of k-systems, k-networks and k-covers were defined by A. Arhangel’skii in 1964, P. O’Meara in 1971 and R. McCoy, I. Ntantu in 1985, respectively. In this paper the relationships among k-systems, k-networks and k-covers are further discussed and are established by mk-systems. As applications, some new characterizations of quotients or closed images of locally compact metric spaces are given by means of mk-systems.     

On convex body chasing

A player moving in the plane is given a sequence of instructions of the following type: at stepi a planar convex setF _i is specified, and the player has to move to a point inF _i. The player is charged for the distance traveled. We provide a strategy for the player which is competitive, i.e., for any sequenceF _i the cost to the player is within a constant (multiplicative) factor of the off-line cost (i.e., the least possible cost when allF _i are known in advance). We conjecture that similar strategies can be developed for this game in any Euclidean space and perhaps even in all metric spaces. The analogous statement where convex sets are replaced by more general families of sets in a metric space includes many on-line/off-line problems such as thek-server problem; we make some remarks on these more general problems.Joel Friedman wishes to acknowledge the National Science Foundation for supporting this research in part under a PYI Grant, CCR-8858788, and IBM for an IBM faculty development award. Nathan Linial's work was supported by a grant from the Binational Science Foundation Israel/US and from the Israel Academy of Sciences.     

The Geodesic Problem in Quasimetric Spaces

In this article, we study the geodesic problem in a generalized metric space, in which the distance function satisfies a relaxed triangle inequality d(x,y)≤σ(d(x,z)+d(z,y)) for some constant σ≥1, rather than the usual triangle inequality. Such a space is called a quasimetric space. We show that many well-known results in metric spaces (e.g. Ascoli-Arzelà theorem) still hold in quasimetric spaces. Moreover, we explore conditions under which a quasimetric will induce an intrinsic metric. As an example, we introduce a family of quasimetrics on the space of atomic probability measures. The associated intrinsic metrics induced by these quasimetrics coincide with the d _α metric studied early in the study of branching structures arisen in ramified optimal transportation. An optimal transport path between two atomic probability measures typically has a “tree shaped” branching structure. Here, we show that these optimal transport paths turn out to be geodesics in these intrinsic metric spaces. This work is supported by an NSF grant DMS-0710714.     

Embedding into Rectilinear Spaces

We show that the problem whether a given finite metric space (X,d) can be embedded into the rectilinear space R ^m can be formulated in terms of m -colorability of a certain hypergraph associated with (X,d) . This is used to close a gap in the proof of an assertion of Bandelt and Chepoi [2] on certain critical metric spaces for this embedding problem. We also consider the question of determining the maximum number of equidistant points that can be placed in the m -dimensional rectilinear space and show that this number is equal to 2m for m ≤ 3 . Received March 19, 1996, and in revised form March 14, 1997.     

Simple Constructions of Almost k-wise Independent Random Variables

We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is (2 + o(1)) (log log n + k/2 + log k + log 1/?), where ? is the statistical difference between the distribution induced on any k bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as ? < 1/(k log n)). An additional advantage of our constructions is their simplicity.     

Fixed Points for Directional Multi-Valued <Emphasis Type="Italic">k</Emphasis>(·)-Contractions

A fixed point theorem for directional multi-valued k(·)-contractions acting m a complete metric space is established which extends similar results both for k(·)-contractions and directional contractions. Such theorem enables to obtain fixed points theorems for the former class of set-valued maps from those valid for the latter one without metrical convexity or proximinality assumptions, thereby contributing to unify the current setting of the theory. Connections with several recent advances on this subject are also examinated.Mathematics Subject Classifications (2000): 47H10, 54H25     

On the Countable Tightness of Product Spaces

In this paper, we discuss the countable tightness of products of spaces which are quotient simages of locally separable metric spaces, or k-spaces with a star-countable k-network. The main result is that the following conditions are equivalent： （1） b = ω1; （2） t（Sω×Sω1） 〉 ω; （3） For any pair （X, Y）, which are k-spaces with a point-countable k-network consisting of cosmic subspaces, t（X×Y）≤ω if and only if one of X, Y is first countable or both X, Y are locally cosmic spaces. Many results on the k-space property of products of spaces with certain k-networks could be deduced from the above theorem.     

Convexities of metric spaces

We introduce two kinds of the notion of convexity of a metric space, called k-convexity and L-convexity, as generalizations of the CAT(0)-property and of the nonpositively curved property in the sense of Busemann, respectively. 2-uniformly convex Banach spaces as well as CAT(1)-spaces with small diameters satisfy both these convexities. Among several geometric and analytic results, we prove the solvability of the Dirichlet problem for maps into a wide class of metric spaces.      

Blow up of balls and coverings in metric spaces

We obtain some refinements and extensions of the Basic Covering Theorem in a metric space (X, ρ). The properties of the metric ρ are used to define an inclusion coefficient k in this theorem, and this is related to the supremum of numbers t such that ρ ^t is a metric in X. The inclusion coefficient k characterizes ultrametric spaces.     

Asymptotic Results and a Markovian Approximation for the M(n)/M(n)/s+GI System

In this paper for the M(n)/M(n)/s+GI system, i.e. for a s-server queueing system where the calls in the queue may leave the system due to impatience, we present new asymptotic results for the intensities of calls leaving the system due to impatience and a Markovian system approximation where these results are applied. Furthermore, we present a new proof for the formulae of the conditional density of the virtual waiting time distributions, recently given by Movaghar for the less general M(n)/M/s+GI system. Also we obtain new explicit expressions for refined virtual waiting time characteristics as a byproduct.     

Hyperbolic rank and subexponential corank of metric spaces

We introduce a new quasi-isometry invariant corank X of a metric space X called subexponential corank. A metric space X has subexponential corank k if roughly speaking there exists a continuous map , T is a topological space, such that for each the set g ^-1(t) has subexponential growth rate in X and the topological dimension dimT = k is minimal among all such maps. Our main result is the inequality for a large class of metric spaces X including all locally compact Hadamard spaces, where rank _h X is the maximal topological dimension of among all CAT(—1) spaces Y quasi-isometrically embedded into X (the notion introduced by M. Gromov in a slightly stronger form). This proves several properties of rank _h conjectured by Gromov, in particular, that any Riemannian symmetric space X of noncompact type possesses no quasi-isometric embedding of the standard hyperbolic space H ⁿ with . Submitted: February 2001, Revised: October 2001.     

Online facility location with facility movements

In the online facility location problem demand points arrive one at a time and the goal is to decide where and when to open a facility. In this paper we consider a new version of the online facility location problem, where the algorithm is allowed to move the opened facilities in the metric space. We consider the uniform case where each facility has the same constant cost. We present an algorithm which is 2-competitive for the general case and we prove that it is 3/2-competitive if the metric space is the line. We also prove that no algorithm with smaller competitive ratio than \({(\sqrt{13}+1)/4\approx 1.1514}\) exists. We also present an empirical analysis which shows that the algorithm gives very good results in the average case.     

Mercer’s Theorem on General Domains: On the Interaction between Measures, Kernels, and RKHSs

Given a compact metric space X and a strictly positive Borel measure ν on X, Mercer’s classical theorem states that the spectral decomposition of a positive self-adjoint integral operator T _k :L ₂(ν)→L ₂(ν) of a continuous k yields a series representation of k in terms of the eigenvalues and -functions of T _k . An immediate consequence of this representation is that k is a (reproducing) kernel and that its reproducing kernel Hilbert space can also be described by these eigenvalues and -functions. It is well known that Mercer’s theorem has found important applications in various branches of mathematics, including probability theory and statistics. In particular, for some applications in the latter areas, however, it would be highly convenient to have a form of Mercer’s theorem for more general spaces X and kernels k. Unfortunately, all extensions of Mercer’s theorem in this direction either stick too closely to the original topological structure of X and k, or replace the absolute and uniform convergence by weaker notions of convergence that are not strong enough for many statistical applications. In this work, we fill this gap by establishing several Mercer type series representations for k that, on the one hand, make only very mild assumptions on X and k, and, on the other hand, provide convergence results that are strong enough for interesting applications in, e.g., statistical learning theory. To illustrate the latter, we first use these series representations to describe ranges of fractional powers of T _k in terms of interpolation spaces and investigate under which conditions these interpolation spaces are contained in L _∞(ν). For these two results, we then discuss applications related to the analysis of so-called least squares support vector machines, which are a state-of-the-art learning algorithm. Besides these results, we further use the obtained Mercer representations to show that every self-adjoint nuclear operator L ₂(ν)→L ₂(ν) is an integral operator whose representing function k is the difference of two (reproducing) kernels.