首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
The assignment problem may be stated as follows: Given finite sets of points S and T, with|S| ? |T|, and given a “metric” which assigns a distance d(x, y) to each pair (x, y) such that xT and yS find a 1?1 function Q: TS which minimizes ΣxTd(x, Q(x)) We consider the two special cases in which the points lie (1) on a line segment and (2) on a circle, and the metric is the distance along the line segment or circle, respectively. In each case, we show that the optimal assignment Q can be computed in a number of steps (additions and comparisons) proportional to the number of points. The problem arose in connection with the efficient rearrangement of desks located in offices along a corridor which encircles one floor of a building.  相似文献   

2.
A subsetS of a metric space (X,d) is calledd-convex if for any pair of pointsx,y S each pointz X withd(x,z) +d(z,y) =d(x,y) belongs toS. We give some results and open questions concerning isometric and convexity-preserving embeddings of finite metric spaces into standard spaces and the number ofd-convex sets of a finite metric space.  相似文献   

3.
We study an inverse problem for a non-compact Riemannian manifold whose ends have the following properties: On each end, the Riemannian metric is assumed to be a short-range perturbation of the metric of the form 2(dy)+h(x,dx), h(x,dx) being the metric of some compact manifold of codimension 1. Moreover one end is exactly cylindrical, i.e. the metric is equal to 2(dy)+h(x,dx). Given two such manifolds having the same scattering matrix on that exactly cylindrical end for all energies, we show that these two manifolds are isometric.  相似文献   

4.
A quasi-metric space (X,d) is called sup-separable if (X,ds) is a separable metric space, where ds(x,y)=max{d(x,y),d(y,x)} for all x,yX. We characterize those preferences, defined on a sup-separable quasi-metric space, for which there is a semi-Lipschitz utility function. We deduce from our results that several interesting examples of quasi-metric spaces which appear in different fields of theoretical computer science admit semi-Lipschitz utility functions. We also apply our methods to the study of certain kinds of dynamical systems defined on quasi-metric spaces.  相似文献   

5.
We denote the distance between vertices x and y of a graph by d(x, y), and pij(x, y) = ∥ {z : d(x, z) = i, d(y, z) = j} ∥. The (s, q, d)-projective graph is the graph having the s-dimensional subspaces of a d-dimensional vector space over GF(q) as vertex set, and two vertices x, y adjacent iff dim(x ? y) = s ? 1. These graphs are regular graphs. Also, there exist integers λ and μ > 4 so that μ is a perfect square, p11(x, y) = λ whenever d(x, y) = 1, and p11(x, y) = μ whenever d(x, y) = 2. The (s, q, d)-projective graphs where 2d3 ≤ s < d ? 2 and (s, q, d) ≠ (2d3, 2, d), are characterized by the above conditions together with the property that there exists an integer r satisfying certain inequalities.  相似文献   

6.
Let d ? 3 be an integer, and set r = 2d?1 + 1 for 3 ? d ? 4, \(\tfrac{{17}}{{32}} \cdot 2^d + 1\) for 5 ? d ? 6, r = d2+d+1 for 7 ? d ? 8, and r = d2+d+2 for d ? 9, respectively. Suppose that Φ i (x, y) ∈ ?[x, y] (1 ? i ? r) are homogeneous and nondegenerate binary forms of degree d. Suppose further that λ1, λ2,..., λ r are nonzero real numbers with λ12 irrational, and λ1Φ1(x1, y1) + λ2Φ2(x2, y2) + · · · + λ r Φ r (x r , y r ) is indefinite. Then for any given real η and σ with 0 < σ < 22?d, it is proved that the inequality
$$\left| {\sum\limits_{i = 1}^r {{\lambda _i}\Phi {}_i\left( {{x_i},{y_i}} \right) + \eta } } \right| < {\left( {\mathop {\max \left\{ {\left| {{x_i}} \right|,\left| {{y_i}} \right|} \right\}}\limits_{1 \leqslant i \leqslant r} } \right)^{ - \sigma }}$$
has infinitely many solutions in integers x1, x2,..., x r , y1, y2,..., y r . This result constitutes an improvement upon that of B. Q. Xue.
  相似文献   

7.
In any connected, undirected graph G = (V, E), the distance d(x, y) between two vertices x and y of G is the minimum number of edges in a path linking x to y in G. A sphere in G is a set of the form S r (x) = {yV : d(x, y) = r}, where x is a vertex and r is a nonnegative integer called the radius of the sphere. We first address in this paper the following question: What is the minimum number of spheres with fixed radius r ≥ 0 required to cover all the vertices of a finite, connected, undirected graph G? We then turn our attention to the Hamming Hypercube of dimension n, and we show that the minimum number of spheres with any radii required to cover this graph is either n or n + 1, depending on the parity of n. We also relate the two above problems to other questions in combinatorics, in particular to identifying codes.  相似文献   

8.
We describe a connection between the combinatorics of generators for certain groups and the combinatorics of Helly's 1913 theorem on convex sets. We use this connection to prove fixed point theorems for actions of these groups on nonpositively curved metric spaces. These results are encoded in a property that we introduce called “property FAr”, which reduces to Serre's property FA when r=1. The method applies to S-arithmetic groups in higher Q-rank, to simplex reflection groups (including some nonarithmetic ones), and to higher rank Chevalley groups over polynomial and other rings (for example SLn(Z[x1,…,xd]), n>2).  相似文献   

9.
Let Π n d denote the space of all spherical polynomials of degree at most n on the unit sphere $\mathbb{S}^{d}Let Π n d denote the space of all spherical polynomials of degree at most n on the unit sphere \mathbbSd\mathbb{S}^{d} of ℝ d+1, and let d(x,y) denote the geodesic distance arccos xy between x,y ? \mathbbSdx,y\in\mathbb{S}^{d} . Given a spherical cap
B(e,a)={x ? \mathbbSd:d(x,e) £ a}    (e ? \mathbbSd, a ? (0,p) is bounded awayfrom p),B(e,\alpha)=\big\{x\in\mathbb{S}^{d}:d(x,e)\leq\alpha\big\}\quad \bigl(e\in\mathbb{S}^{d},\ \alpha\in(0,\pi)\ \mbox{is bounded awayfrom}\ \pi\bigr),  相似文献   

10.
Let X be a non-empty set and F:X×XX be a given mapping. An element (x,y)∈X×X is said to be a coupled fixed point of the mapping F if F(x,y)=x and F(y,x)=y. In this paper, we consider the case when X is a complete metric space endowed with a partial order. We define generalized Meir-Keeler type functions and we prove some coupled fixed point theorems under a generalized Meir-Keeler contractive condition. Some applications of our obtained results are given. The presented theorems extend and complement the recent fixed point theorems due to Bhaskar and Lakshmikantham [T. Gnana Bhaskar, V. Lakshmikantham, Fixed point theorems in partially ordered metric spaces and applications, Nonlinear Anal. 65 (2006) 1379-1393].  相似文献   

11.
S. Sadiq Basha 《TOP》2014,22(2):543-553
This paper addresses the non-linear programming problem of globally minimizing the real valued function x?d(x,Sx) where S is a generalized proximal contraction in the setting of a metric space. Eventually, one can obtain optimal approximate solutions to some fixed-point equations in the event that they have no solution.  相似文献   

12.
A metric space (X,d) is monotone if there is a linear order < on X and a constant c>0 such that d(x,y)≦cd(x,z) for all x<y<zX. Properties of continuous functions with monotone graph (considered as a planar set) are investigated. It is shown, for example, that such a function can be almost nowhere differentiable, but must be differentiable at a dense set, and that the Hausdorff dimension of the graph of such a function is 1.  相似文献   

13.
We study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^dWe study the asymptotic growth of the diameter of a graph obtained by adding sparse “long” edges to a square box in ${\mathbb Z}^d$. We focus on the cases when an edge between x and y is added with probability decaying with the Euclidean distance as |x ? y|?s+o(1) when |x ? y| → ∞. For s ∈ (d, 2d) we show that the graph diameter for the graph reduced to a box of side L scales like (log L)Δ+o(1) where Δ?1 := log2(2d/s). In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance L. We also show that a ball of radius r in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius exp{r1/Δ+o(1)} in the Euclidean metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 210‐227, 2011  相似文献   

14.
Let be a contractive gauge function in the sense that φ is continuous, φ(s)<s for s>0, and if f:M→M satisfies d(f(x),f(y))?φ(d(x,y)) for all x,y in a complete metric space (M,d), then f always has a unique fixed point. It is proved that if T:M→M satisfies
  相似文献   

15.
For every metric space (X, d) and origin oX, we show the inequality I o (x, y) ≤ 2d o (x, y), where I o (x, y) = d(x, y)/d(x, o)d(y, o) is the metric space inversion semimetric, d o is a metric subordinate to I o , and x, yX \ {o} The constant 2 is best possible.  相似文献   

16.
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.  相似文献   

17.
We investigate the minimal Riesz s-energy problem for positive measures on the d-dimensional unit sphere Sd in the presence of an external field induced by a point charge, and more generally by a line charge. The model interaction is that of Riesz potentials |xy|s with d−2?s<d. For a given axis-supported external field, the support and the density of the corresponding extremal measure on Sd is determined. The special case s=d−2 yields interesting phenomena, which we investigate in detail. A weak asymptotic analysis is provided as s+(d−2).  相似文献   

18.
A ubiquitous class of lattice ordered semigroups introduced by Bosbach, which we call Bezout monoids, seems to be the appropriate structure for the study of divisibility in various classical rings like GCD domains (including UFD??s), rings of low dimension (including semi-hereditary rings), as well as certain subdirect products of such rings and certain factors of such subdirect products. A Bezout monoid is a commutative monoid S with 0 such that under the natural partial order (for a, b ?? S, a ?? b ?? S ? bS ? aS), S is a distributive lattice, multiplication is distributive over both meets and joins, and for any x, y ?? S, if d = x ?? y and dx 1 = x then there is a y 1 ?? S with dy 1 = y and x 1 ?? y 1 = 1. We investigate Bezout monoids by using filters and m-prime filters, and describe all homorphisms between them. We also prove analogues of the Pierce and the Grothendieck sheaf representations of rings for Bezout monoids. The question whether Bezout monoids describe divisibility in Bezout rings (rings whose finitely generated ideals are principal) is still open.  相似文献   

19.
Let S be a numerical semigroup and let (?,≤ S ) be the (locally finite) poset induced by S on the set of integers ? defined by x S y if and only if y?xS for all integers x and y. In this paper, we investigate the Möbius function associated to (?,≤ S ) when S is an arithmetic semigroup.  相似文献   

20.
We prove that if (X,d) is a metric space, C is a closed subset of X and xX, then the distance of x to RS agrees with the maximum of the distances of x to R and S, for every closed subsets R,SC such that C=RS, if and only if C is x-boundedly connected.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号