An approximation scheme for a problem of search for a vector subset

We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n ^2/?+1(9/?)^3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space.     

On Quantum Dynamics on <Emphasis Type="Italic">C</Emphasis>*-Algebras

We study three related extremal problems in the space H of functions analytic in the unit disk such that their boundary values on a part γ₁ of the unit circle Γ belong to the space \(L_{{\psi _1}}^\infty ({\gamma _1})\)of functions essentially bounded on γ₁ with weight ψ₁ and their boundary values on the set γ₀ = Γ γ₁ belong to the space \(L_{{\psi _0}}^\infty ({\gamma _0})\)with weight ψ₀. More exactly, on the class Q of functions from H such that the \(L_{{\psi _0}}^\infty ({\gamma _0})\)-norm of their boundary values on γ₀ does not exceed 1, we solve the problem of optimal recovery of an analytic function on a subset of the unit disk from its boundary values on γ₁ specified approximately with respect to the norm of \(L_{{\psi _1}}^\infty ({\gamma _1})\). We also study the problem of the optimal choice of the set γ₁ for a given fixed value of its measure. The problem of the best approximation of the operator of analytic continuation from a part of the boundary by bounded linear operators is investigated.     

Space of invariant bilinear forms

Let \({\mathbb {F}}\) be a field, V a vector space of dimension n over \({\mathbb {F}}\). Then the set of bilinear forms on V forms a vector space of dimension \(n^2\) over \({\mathbb {F}}\). For char \({\mathbb {F}}\ne 2\), if T is an invertible linear map from V onto V then the set of T-invariant bilinear forms, forms a subspace of this space of forms. In this paper, we compute the dimension of T-invariant bilinear forms over \({\mathbb {F}}\). Also we investigate similar type of questions for the infinitesimally T-invariant bilinear forms (T-skew symmetric forms). Moreover, we discuss the existence of nondegenerate invariant (resp. infinitesimally invariant) bilinear forms.     

Heuristic algorithms for general <Emphasis Type="Italic">k</Emphasis>-level facility location problems

In a general k-level uncapacitated facility location problem (k-GLUFLP), we are given a set of demand points, denoted by D, where clients are located. Facilities have to be located at a given set of potential sites, which is denoted by F in order to serve the clients. Each client needs to be served by a chain of k different facilities. The problem is to determine some sites of F to be set up and to find an assignment of each client to a chain of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, for a fixed k, an approximation algorithm within a factor of 3 of the optimum cost is presented for k-GLUFLP under the assumption that the shipping costs satisfy the properties of metric space. In addition, when no fixed cost is charged for setting up the facilities and k=2, we show that the problem is strong NP-complete and the constant approximation factor is further sharpen to be 3/2 by a simple algorithm. Furthermore, it is shown that this ratio analysis is tight.     

On the rank of compact <Emphasis Type="Italic">p</Emphasis>-adic Lie groups

The rank of a profinite group G is the basic invariant \({{\rm rk}(G):={\rm sup}\{d(H) \mid H \leq G\}}\), where H ranges over all closed subgroups of G and d(H) denotes the minimal cardinality of a topological generating set for H. A compact topological group G admits the structure of a p-adic Lie group if and only if it contains an open pro-p subgroup of finite rank. For every compact p-adic Lie group G one has rk(G) ≥ dim(G), where dim(G) denotes the dimension of G as a p-adic manifold. In this paper we consider the converse problem, bounding rk(G) in terms of dim(G). Every profinite group G of finite rank admits a maximal finite normal subgroup, its periodic radical π(G). One of our main results is the following. Let G be a compact p-adic Lie group such that π(G) = 1, and suppose that p is odd. If \(\{g \in G \mid g^{p-1}=1 \}\) is equal to {1}, then rk(G) = dim(G).     

Uncountable equilateral sets in Banach spaces of the form <Emphasis Type="Italic">C</Emphasis>(<Emphasis Type="Italic">K</Emphasis>)

The paper is concerned with the problem whether a nonseparable Banach space must contain an uncountable set of vectors such that the distances between every two distinct vectors of the set are the same. Such sets are called equilateral. We show that Martin’s axiom and the negation of the continuum hypothesis imply that every nonseparable Banach space of the form C(K) has an uncountable equilateral set. We also show that one cannot obtain such a result without an additional set-theoretic assumption since we construct an example of nonseparable Banach space of the form C(K) which has no uncountable equilateral set (or equivalently no uncountable (1+ε)-separated set in the unit sphere for any ε > 0) making another consistent combinatorial assumption. The compact K is a version of the split interval obtained from a sequence of functions which behave in an anti-Ramsey manner. It remains open if there is an absolute example of a nonseparable Banach space of the form different than C(K) which has no uncountable equilateral set. It follows from the results of S. Mercourakis and G. Vassiliadis that our example has an equivalent renorming in which it has an uncountable equilateral set. It remains open if there are consistent examples of nonseparable Banach spaces which have no uncountable equilateral sets in any equivalent renorming but it follows from the results of S. Todorcevic that it is consistent that every nonseparable Banach space has an equivalent renorming in which it has an uncountable equilateral set.     

Density of characters of bounded <Emphasis Type="Italic">p</Emphasis>-adic analytic functions in the topological dual

Let K be an ultrametric complete algebraically closed field, let D be a disk {x ∈ K ‖x| < R} (with R in the set of absolute values of K) and let A be the Banach algebra of bounded analytic functions in D. The vector space generated by the set of characters of A is dense in the topological dual of A if and only if K is not spherically complete. Let H(D) be the Banach algebra of analytic elements in D. The vector space generated by the set of characters of H(D) is never dense in the topological dual of H(D).     

On the asymptotic optimality of a solution of the euclidean problem of covering a graph by <Emphasis Type="Italic">m</Emphasis> nonadjacent cycles of maximum total weight

In the problem of covering an n-vertex graph by m cycles of maximum total weight, it is required to find a family of m vertex-nonadjacent cycles such that it covers all vertices of the graph and the total weight of edges in the cover is maximum. The paper presents an algorithm for approximately solving the problem of covering a graph in Euclidean d-space R^d by m nonadjacent cycles of maximum total weight. The algorithm has time complexity O(n³). An estimate of the accuracy of the algorithm depending on the parameters d, m, and n is substantiated; it is shown that if the dimension d of the space is fixed and the number of covering cycles is m = o(n), then the algorithm is asymptotically exact.     

Extending Lipschitz maps into <Emphasis Type="Italic">C</Emphasis>(<Emphasis Type="Italic">K</Emphasis>)-spaces

We show that if K is a compact metric space then C(K) is a 2-absolute Lipschitz retract. We then study the best Lipschitz extension constants for maps into C(K) from a given metric space M, extending recent results of Lancien and Randrianantoanina. They showed that a finite-dimensional normed space which is polyhedral has the isometric extension property for C(K)-spaces; here we show that the same result holds for spaces with Gateaux smooth norm or of dimension two; a three-dimensional counterexample is also given. We also show that X is polyhedral if and only if every subset E of X has the universal isometric extension property for C(K)-spaces. We also answer a question of Naor on the extension of Hölder continuous maps.     

Positive-fraction intersection results and variations of weak epsilon-nets

A connected Finsler space (M, F) is said to be homogeneous if it admits a transitive connected Lie group G of isometries. A geodesic in a homogeneous Finsler space (G / H, F) is called a homogeneous geodesic if it is an orbit of a one-parameter subgroup of G. In this paper, we study the problem of the existence of homogeneous geodesics on a homogeneous Finsler space, and prove that any homogeneous Finsler space of odd dimension admits at least one homogeneous geodesic through each point.     

The Local Metric Dimension of Strong Product Graphs

A vertex \(v\in V(G)\) is said to distinguish two vertices \(x,y\in V(G)\) of a nontrivial connected graph G if the distance from v to x is different from the distance from v to y. A set \(S\subset V(G)\) is a local metric generator for G if every two adjacent vertices of G are distinguished by some vertex of S. A local metric generator with the minimum cardinality is called a local metric basis for G and its cardinality, the local metric dimension of G. It is known that the problem of computing the local metric dimension of a graph is NP-Complete. In this paper we study the problem of finding exact values or bounds for the local metric dimension of strong product of graphs.     

<Emphasis Type="Bold">K</Emphasis><Subscript>0</Subscript> of Semiartinian Von Neumann Regular Rings. Direct Finiteness Versus Unit-Regularity

If R is a regular and semiartinian ring, it is proved that the following conditions are equivalent: (1) R is unit-regular, (2) every factor ring of R is directly finite, (3) the abelian group K _O(R) is free and admits a basis which is in a canonical one to one correspondence with a set of representatives of simple right R-modules. For the class of semiartinian and unit-regular rings the canonical partial order of K _O(R) is investigated. Starting from any partially ordered set I, a special dimension group G(I) is built and a large class of semiartinian and unit-regular rings is shown to have the corresponding K _O(R) order isomorphic to G(P r i m _R ), where P r i m _R is the primitive spectrum of R. Conversely, if I is an artinian partially ordered set having a finite cofinal subset, it is proved that the dimension group G(I) is realizable as K _O(R) for a suitable semiartinian and unit-regular ring R.     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

On solutions of the mixed Dirichlet-Steklov problem for the biharmonic equation in exterior domains

We study the unique solvability of the mixed Dirichlet-Steklov problem for the biharmonic equation in exterior domains under the assumption that a generalized solution of this problem has a bounded Dirichlet integral with weight |x| ^a . Depending on the value of the parameter a, we prove uniqueness theorem or present exact formulas for the dimension of the solution space of the mixed Dirichlet-Steklov problem in the exterior of a compact set.     

Minimal Translation Hypersurfaces in Euclidean Space

The graph of a function f defined in some open set of the Euclidean space of dimension (p + q) is said to be a translation graph if f may be expressed as the sum of two independent functions ? and ψ defined in open sets of the Euclidean spaces of dimension p and q, respectively. We obtain a useful expression for the mean curvature of the graph of f in terms of the Laplacian, the gradient of ? and ψ as well as of the mean curvatures of their graphs. We study translation graphs having zero mean curvature, that is, minimal translation graphs, by imposing natural conditions on ? and ψ, like harmonicity, minimality and eikonality (constant norm of the gradient), giving several examples as well as characterization results.     

On separability of the functional space with the open-point and bi-point-open topologies

We study the property of separability of functional space C(X) with the open-point and bi-point-open topologies and show that it is consistent with ZFC that there is a set of reals of cardinality \({\mathfrak{c}}\) such that a set C(X) with the open-point topology is not a separable space. We also show in a set model (the iterated perfect set model) that for every set of reals X, C(X) with the bi-point-open topology is a separable space.     

Strict <Emphasis Type="Italic">K</Emphasis>-monotonicity and <Emphasis Type="Italic">K</Emphasis>-order continuity in symmetric spaces

This paper is devoted to strict K-monotonicity and K-order continuity in symmetric spaces. Using a local approach to the geometric structure in a symmetric space E we investigate a connection between strict K-monotonicity and global convergence in measure of a sequence of the maximal functions. Next, we solve an essential problem whether an existence of a point of K-order continuity in a symmetric space E on \([0,\infty )\) implies that the embedding \(E\hookrightarrow {L^1}[0,\infty )\) does not hold. We present a complete characterization of an equivalent condition to K-order continuity in a symmetric space E using a notion of order continuity and the fundamental function of E. We also investigate a relationship between strict K-monotonicity and K-order continuity in symmetric spaces and show some examples of Lorentz spaces and Marcinkiewicz spaces having these properties or not. Finally, we discuss a local version of a crucial correspondence between order continuity and the Kadec–Klee property for global convergence in measure in a symmetric space E.     

On solutions of a boundary value problem for the biharmonic equation

We study the uniqueness of the solution of a boundary value problem for the biharmonic equation in unbounded domains under the assumption that the generalized solution of this problem has a bounded Dirichlet integral with weight |x|^a. Depending on the value of the parameter a, we prove uniqueness theorems or present exact formulas for the dimension of the solution space of this problem in the exterior of a compact set and in a half-space.     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

Discretization orders for distance geometry problems

Given a weighted, undirected simple graph G = (V, E, d) (where \({d:E\to\mathbb{R}_+}\)), the distance geometry problem (DGP) is to determine an embedding \({x:V\to\mathbb{R}^K}\) such that \({\forall \{i,j\} \in E\;\|x_i-x_j\|=d_{ij}}\) . Although, in general, the DGP is solved using continuous methods, under certain conditions the search is reduced to a discrete set of points. We give one such condition as a particular order on V. We formalize the decision problem of determining whether such an order exists for a given graph and show that this problem is NP-complete in general and polynomial for fixed dimension K. We present results of computational experiments on a set of protein backbones whose natural atomic order does not satisfy the order requirements and compare our approach with some available continuous space searches.