An application of H differentiability to generalized complementarity problems over symmetric cones

In this paper, we focus on a generalized complementarity problems over symmetric cone GSCCP(f,g) when the underlying functions f and g are H-differentiable. By introducing the concepts of relatively uniform Cartesian P-property, relatively Cartesian P(P₀)-property, the Cartesian semimonotone (E₀)-property (strictly Cartesian semimonotone (E)-property), and the relatively regular point with respect to the merit function Ψ(x), we extend various similar results proved in GCP(f,g) to generalized complementarity problems over symmetric cone GSCCP(f,g) and establish various conditions on f and g to get a solution to GSCCP(f,g).     

Fixed point theorem of generalized quasi-contractive mapping in cone metric space

In this paper, we introduce the generalized quasi-contractive mapping f in a cone metric space (X,d). f is called a generalized quasi-contractive if there is a real λ∈[0,1) such that for all x,y∈X,

d(fx,fy)≤λs     

Set-contractive mappings and difference equations in Banach spaces

In this paper, we consider the difference equation on an arbitrary Banach space (X, ∥·∥_x), Δ(q_nΔx_n + f_n(x_n) = 0, where {q_n} is a positive sequence and f_n is X-valued. We shall give conditions so that for a given x ϵ X, there exists a solution of this equation asymptotically equal to x.     

Variance based sensitivity analysis of model output. Design and estimator for the total sensitivity index

Variance based methods have assessed themselves as versatile and effective among the various available techniques for sensitivity analysis of model output. Practitioners can in principle describe the sensitivity pattern of a model Y=f(X₁,X₂,…,Xk) with k uncertain input factors via a full decomposition of the variance V of Y into terms depending on the factors and their interactions. More often practitioners are satisfied with computing just k first order effects and k total effects, the latter describing synthetically interactions among input factors. In sensitivity analysis a key concern is the computational cost of the analysis, defined in terms of number of evaluations of f(X₁,X₂,…,Xk) needed to complete the analysis, as f(X₁,X₂,…,Xk) is often in the form of a numerical model which may take long processing time. While the computational cost is relatively cheap and weakly dependent on k for estimating first order effects, it remains expensive and strictly k-dependent for total effect indices. In the present note we compare existing and new practices for this index and offer recommendations on which to use.     

Voronoi diagrams of moving points in the plane and of lines in space: tight bounds for simple configurations

The combinatorial complexities of (1) the Voronoi diagram of moving points in 2D and (2) the Voronoi diagram of lines in 3D, both under the Euclidean metric, continues to challenge geometers because of the open gap between the Ω(n²) lower bound and the O(n3+?) upper bound. Each of these two combinatorial problems has a closely related problem involving Minkowski sums: (1′) the complexity of a Minkowski sum of a planar disk with a set of lines in 3D and (2′) the complexity of a Minkowski sum of a sphere with a set of lines in 3D. These Minkowski sums can be considered “cross-sections” of the corresponding Voronoi diagrams. Of the four complexity problems mentioned, problems (1′) and (2′) have recently been shown to have a nearly tight bound: both complexities are O(n2+?) with lower bound Ω(n²).In this paper, we determine the combinatorial complexities of these four problems for some very simple input configurations. In particular, we study point configurations with just two degrees of freedom (DOFs), exploring both the Voronoi diagrams and the corresponding Minkowski sums. We consider the traditional versions of these problems to have 4 DOFs. We show that even for these simple configurations the combinatorial complexities have upper bounds of either O(n²) or O(n2+?) and lower bounds of Ω(n²).     

On n-Dimensional Sequences. I

Let R be a commutative ring and let n ≥ 1. We study Γ(s), the generating function and Ann(s), the ideal of characteristic polynomials of s, an n-dimensional sequence over R .We express f(X₁,…,X_n) · Γ(s)(X^-1₁,…,X^-1_n) as a partitioned sum. That is, we give (i) a 2ⁿ-fold "border" partition (ii) an explicit expression for the product as a 2ⁿ-fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is βo(f, s), the "border polynomial" of f and s, which is divisible by X₁ … X_n.We say that s is eventually rectilinear if the elimination ideals Ann(s)∩R[X_i] contain an f_i (X_i) for 1 ≤ i ≤ n. In this case, we show that Ann(s) is the ideal quotient ($\text{∑}{}^{\mathrm{n}}{}_{\mathrm{i}}\text{=1(fi) : βo(f, s)/(X}{}_1\text{… X}{}_{\mathrm{n}}\text{)}$).When R and R[[X₁, X₂ ,…, X_n]] are factorial domains (e.g. R a principal ideal domain or F [X₁,…, X_n]), we compute the monic generator γ_i of Ann(s) ∩ R[X_i] from known f_i ϵ Ann(s) ∩ R[X_i] or from a finite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O($\text{∏}{}_{\mathrm{n}}{}^{\mathrm{i}}\text{=1 δγ}{}^3{}_{\mathrm{i}}$) algorithm to compute an F-basis for Ann(s).     

On the Practical Solution of Genus Zero Diophantine Equations

Let f(X, Y) be an absolutely irreducible polynomial with integer coefficients such that the curve defined by the equation f(X, Y)  =  0 is of genus 0 having at least three infinite valuations. This paper describes a practical general method for the explicit determination of all integer solutions of the diophantine equation f(X, Y)  =  0. Some elaborated examples are given.     

On the approximation of the range of values by interval expressions

If the real-valued mappingf has a representation of the formf(x)=?₀+?(x)·h(x),x∈X where for the diameter ofh(X) the inequalityd(h(X))≤σd(X) holds and for the absolute value of ?(X) we have ??(X)?≤τd(X) ⁿ, then we introduce an interval expression forf which approximates the range of values off over the compact intervalX with ordern+1. Our result contains as a special case the theorem on higher order centered forms from [2] and a series of representations off not discussed before.     

Online Metric Tracking and Smoothing

We consider the online smoothing problem, in which a tracker is required to maintain distance no more than Δ≥0 from a time-varying signal f while minimizing its own movement. The problem is determined by a metric space (X,d) with an associated cost function c:?→?. Given a signal f ₁,f ₂,…∈X the tracker is responsible for producing a sequence a ₁,a ₂,… of elements of X that meet the proximity constraint: d(f _i ,a _i )≤Δ. To complicate matters, the tracker is on-line—the value a _i may only depend on f ₁,…,f _i —and wishes to minimize the cost of his travels, ∑c(d(a _i ,a _i+1)). We evaluate such tracking algorithms competitively, comparing this with the cost achieved by an optimal adversary apprised of the entire signal in advance. The problem was originally proposed by Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, 2009), who considered the natural circumstance where the metric spaces are taken to be ? ^k with the ? ₂ metric and the cost function is equal to 1 unless the distance is zero (thus the tracker pays a fixed cost for any nonzero motion).

We begin by studying arbitrary metric spaces with the “pay if you move” metric of Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098–1107. ACM Press, New York, [2009]) described above and describe a natural randomized algorithm that achieves a O(logb _Δ)-competitive ratio, where b _Δ=max _x∈X |B _Δ(x)| is the maximum number of points appearing in any ball of radius Δ. We show that this bound is tight.

We then focus on the metric space ? with natural families of monotone cost functions c(x)=x ^p for some p≥0. We consider both the expansive case (p≥1) and the contractive case (p<1), and show that the natural lazy algorithm performs well in the expansive case. In the contractive case, we introduce and analyze a novel deterministic algorithm that achieves a constant competitive ratio depending only on p. Finally, we observe that by slightly relaxing the guarantee provided by the tracker, one can obtain natural analogues of these algorithms that work in continuous metric spaces.

     

Approximate unions of lines and minkowski sums

We study the complexity of, and algorithms to construct, approximations of the union of lines and of the Minkowski sum of two simple polygons. We also studythick unions of lines and Minkowski sums, which are inflated with a small disc. Letb=D/ɛ be the ratio of the diameter of the region of interest and the maximum distance (or error) of the approximation. An approximate union of lines or Minkowski sum has complexity Θ (b ²) in the worst case. The thick union ofn lines has complexity Ω(n+b ²) andO(n +b√bn), and thick Minkowski sums have complexity Ω(n ²+b²) andO((n+b)n√blogn+n ² logn) in the worst case. We present algorithms that run inO(n+n ^2/3+δ b ^4/3 andO(min(bn,n ^4/3+δ b ^2/3)) time (any δ>0) for approximate and thick arrangements. For approximate Minkowski sums, the running time isO(min(b ² n,n ² +b ² + (nb)^4/3+δ); thick Minkowski sums takeO(n ^8/3+δ b ^2/3) time to compute.     

Solving Genus Zero Diophantine Equations with at Most Two Infinite Valuations

Let f(X, Y) be an absolutely irreducible polynomial with integer coefficients such that the curve defined by the equation f(X, Y)  =  0 is of genus 0 having at most two infinite valuations. This paper describes a practical general method for the explicit determination of all integer solutions of the diophantine equation f(X, Y)  =  0. Several elaborated examples are given. Furthermore, a necessary and sufficient condition for a curve of genus 0 to have infinitely many integer points is obtained.     

Supremum metric on the space of fuzzy sets and common fixed point theorems for fuzzy mappings

This paper generalizes a classical result about the space of bounded closed sets with the Hausdorff metric, and establishes the completeness of CB(X) with respect to the completeness of the metric space X, where CB(X) is the class of fuzzy sets with nonempty bounded closed α-cut sets, equipped with the supremum metric d_∞ which takes the supremum on the Hausdorff distances between the corresponding α-cut sets. In addition, some common fixed point theorems for fuzzy mappings are proved and two examples are given to illustrate the validity of the main results in fixed point theory.     

Algorithm 40 An algorithm for the integral homology of certain topological groups

We describe an algorithm which enables us to compute the homology of Ω(X ₁ ?X ₂) in terms of the homologies of ΩX ₁ and ΩX ₂ (where ΩX is the loop space ofX). A computer program implementing this algorithm is then presented.     

On the profile of the corona of two graphs

The concept of profile, together with bandwidth, originates from handling sparse matrices in solving linear systems of equations. Given a graph G, the profile minimization problem is to find a one-to-one mapping f:V(G)→{1,2,…,|V(G)|} such that ∑_v∈V(G)max_x∈N[v](f(v)−f(x)) is as small as possible, where N[v]={v}∪{x:x is adjacent to v}. This paper studies the profile of the corona G∧H of two graphs G and H. In particular, bounds for the profile of the corona of two graphs are established. Also, exact values of the profiles of coronas G∧H are obtained when G has certain properties, including when G is a caterpillar, a complete graph or a cycle.     

Ranking numbers of graphs

Given a graph G, a vertex ranking (or simply, ranking) of G is a mapping f from V(G) to the set of all positive integers, such that for any path between two distinct vertices u and v with f(u)=f(v), there is a vertex w in the path with f(w)>f(u). If f is a ranking of G, the ranking number of G under f, denoted γf(G), is defined by , and the ranking number of G, denoted γ(G), is defined by . The vertex ranking problem is to determine the ranking number γ(G) of a given graph G. This problem is a natural model for the manufacturing scheduling problem. We study the ranking numbers of graphs in this paper. We consider the relation between the ranking numbers and the minimal cut sets, and the relation between the ranking numbers and the independent sets. From this, we obtain the ranking numbers of the powers of paths and the powers of cycles, the Cartesian product of P₂ with Pn or Cn, and the caterpilars. And we also find the vertex ranking numbers of the composition of two graphs in this paper.     

Stability analysis of nonlinear retarded difference equations in Banach spaces

In this paper, we give new sufficient conditions for asymptotic stability and instability of nonlinear difference equations with delays in infinite-dimensional spaces x(k + 1) = f(k,x(k), x(k−1), …x(k−r))), x(k) ϵ X, k = 0, 1,2,…, where X is a Banach space. Our results are obtained using a general comparison condition on the right-hand side function f(k,.), which generalizes the stability and instability results obtained by Yang, Miminis, Naulin, and Vanegas. An application to the stabilizability problem of retarded control systems and illustrative examples of the obtained results are given.     

Averages of functions and ergodic measures inF-spaces

For each sequence of points in a compactF-spaceX the corresponding sequence of Cesàro sums (1/n) _i=1 ⁿ f(x _i ) diverges for somef inC(X). It follows that each minimal set in a discrete flow (X, h) supports at least two ergodich-invariant Borel probability measures.     

Monoid-labeled transition systems

Given a -complete (semi)lattice , we consider -labeled transition systems as coalgebras of a functor ⁽⁻⁾, associating with a set X the set ^X of all -fuzzy subsets. We describe simulations and bisimulations of -coalgebras to show that L⁽⁻⁾ weakly preserves nonempty kernel pairs iff it weakly preserves nonempty pullbacks iff L is join infinitely distributive (JID).Exchanging for a commutative monoid , we consider the functor ⁽⁻⁾_ω which associates with a set X all finite multisets containing elements of X with multiplicities m M. The corresponding functor weakly preserves nonempty pullbacks along injectives iff 0 is the only invertible element of , and it preserves nonempty kernel pairs iff is refinable, in the sense that two sum representations of the same value, r₁ + … + r_m = c₁ + … + c_n, have a common refinement matrix (m_{(i, j)}) whose k-th row sums to r_k and whose l-th column sums to c_l for any 1≤ k ≤ m and 1 ≤ l ≤ n.