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.     

On k -diameter of k -connected graphs

Let G be a k-connected simple graph with order n. The k-diameter, combining connectivity with diameter, of G is the minimum integer d _k (G) for which between any two vertices in G there are at least k internally vertex-disjoint paths of length at most d _k (G). For a fixed positive integer d, some conditions to insure d _k (G)⩽d are given in this paper. In particular, if d⩾3 and the sum of degrees of any s (s=2 or 3) nonadjacent vertices is at least n+(s−1)k+1−d, then d _k (G)⩽d. Furthermore, these conditions are sharp and the upper bound d of k-diameter is best possible. Supported by NNSF of China (19971086).     

The bias of k-step M-estimators

It is well-known that k-step M-estimators can yield a high efficiency without losing the breakdown point of the initial estimator. In this note we derive their bias curves. In the location framework the bias increases only slightly with k, but in the scale case the bias curves change considerably.     

Sub-semi-Riemannian geometry of general H-type groups

We study a special class of nilpotent Lie groups of step 2, that generalizes the class of the so-called H(eisenberg)-type groups, defined by A. Kaplan in 1980. We change the presence of an inner product to an arbitrary scalar product and relate the construction to the composition of quadratic forms. We present the geodesic equation for sub-semi-Riemannian metric on nilpotent Lie groups of step 2 and solve them for the case of general H-type groups. We also present some results on sectional curvature and the Ricci tensor of semi-Riemannian general H-type groups.     

k-alternating knots

A projection of a knot is k-alternating if its overcrossings and undercrossings alternate in groups of k as one reads around the projection (an obvious generalization of the notion of an alternating projection). We prove that every knot admits a 2-alternating projection, which partitions nontrivial knots into two classes: alternating and 2-alternating.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

k-Domination and k-Independence in Graphs: A Survey

In 1985, Fink and Jacobson gave a generalization of the concepts of domination and independence in graphs. For a positive integer k, a subset S of vertices in a graph G = (V, E) is k-dominating if every vertex of V − S is adjacent to at least k vertices in S. The subset S is k-independent if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. In this paper we survey results on k-domination and k-independence.     

The geometry of spheres in free abelian groups

We study word metrics on ${\mathbb{Z}^d}$ by developing tools that are fine enough to measure dependence on the generating set. We obtain counting and distribution results for the words of length n. With this, we show that counting measure on spheres always converges to cone measure on a polyhedron (strongly, in an appropriate sense). Using the limit measure, we can reduce probabilistic questions about word metrics to problems in convex geometry of Euclidean space. We give several applications to the statistics of ??size-like?? functions.     

The k-ball l-path branch weight centroid

If x is a vertex of a tree T of radius r, if k and l are integers, if 0 k r, 0 l r, and if P is an l-path with one end at x, then define β(x; k, P) to be the number of vertices of T that are reachable from x via the l-path P and that are outside of the k-ball about x. That is, β(x;k,P) = {yεV(T):y is reachable from x via P,d(x,y) > k}. Define the k-ball l-path branch weight of x, denoted β(x;k,l), to be max {β(x;k,P):P an l-path with one end at x}, and define the k-balll-path branch weight centroid of T, denoted B(T;k,l), to be the set xεV(T): β(x;k,l) β(y;k,l), yεV(T). This two-parameter family of central sets in T includes the one-parameter family of central sets called the k-nuclei introduced by Slater (1981) which has been shown to be the one parameter family of central sets called the k-branch weight centroids by Zaw Win (1993). It also includes the one-parameter family of central sets called the k-ball branch weight centroid introduced by Reid (1991). In particular, this new family contains the classical central sets, the center and the median (which Zelinka (1968) showed is the ordinary branch weight centroid). The sets obtained for particular values of k and l are examined, and it is shown that for many values they consist of one vertex or two adjacent vertices.     

k-Subdomination in graphs

For a positive integer k, a k-subdominating function of a graph G=(V,E) is a function f : V→{−1,1} such that ∑_uNG[v]f(u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ_ks(G), is the minimum of ∑_vVf(v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ_ks(G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ_ks(G), the signed domination number γ_s(G) and the majority domination number γ_maj(G).     

Norm of pre-Schwarzian derivative for the class of k-uniformly convex and k-starlike functions

A quasiconformal extension for the class of k-uniformly convex functions, denoted , and for the class of k-starlike functions, denoted is provided. Also, estimation of the norm of pre-Schwarzian derivative in is given.     

Bounded geometry for Kleinian groups

We show that a Kleinian surface group, or hyperbolic 3-manifold with a cusp-preserving homotopy-equivalence to a surface, has bounded geometry if and only if there is an upper bound on an associated collection of coefficients that depend only on its end invariants. Bounded geometry is a positive lower bound on the lengths of closed geodesics. When the surface is a once-punctured torus, the coefficients coincide with the continued fraction coefficients associated to the ending laminations. Oblatum 31-VII-2000 & 9-V-2001?Published online: 20 July 2001     

Fundamental groups and Diophantine geometry

This is a brief exposition on the uses of non-commutative fundamental groups in the study of Diophantine problems.     

k-广义Hermite矩阵

本文给出了k-广义(反)Hermite矩阵的概念,研究了它的性质及其与k-广义酉矩阵之间的联系,推广了酉矩阵和(反)Hermite矩阵的相应结果.