Estimation under ℓ1-Symmetry

The estimation of the location parameter of an ℓ₁-symmetric distribution is considered. Specifically when a p-dimensional random vector has a distribution that is a mixture of uniform distributions on the ℓ₁-sphere, we investigate a general class of estimators of the form δ=X+g. Under the usual quadratic loss, domination of δ over X is obtained through the partial differential inequality 4 div g+2X ∂²g+ g²0 and a new superharmonicity-type-like notion adapted to the ℓ₁-context. Specifically the condition of ℓ₁-superharmonicity is that 2Δf+X ³f0 and div ³f0 as compared to the usual (ℓ₂) condition Δf0.     

Entropy numbers in sequence spaces with an application to weighted function spaces

We determine the exact asymptotic behaviour of entropy numbers of diagonal operators from ℓ_p to ℓ_q, 0<q<p∞, under mild regularity conditions on the generating diagonal sequence. On one hand, this is a quantitative version of Pitt's theorem for diagonal operators, and on the other hand it is a limiting case of results by Carl. An application to embeddings of weighted Besov and Triebel–Lizorkin spaces is also given.     

Asymptotic Behaviour of Best lp-Approximations from Affi ne Subspaces

In this paper we consider the problem of best approximation in ℓ_pⁿ, 1<p∞. If h_p, 1<p<∞, denotes the best ℓ_p-approximation of the element h ⁿ from a proper affine subspace K of ⁿ, hK, then lim_p→∞h_p=h_∞^*, where h_∞^* is a best uniform approximation of h from K, the so-called strict uniform approximation. Our aim is to prove that for all r there are α_j ⁿ, 1jr, such that

Full-size image

, with γ_p^{(r) n} and γ_p^(r)= (p^−r−1).     

All-norm approximation algorithms

A major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. In many cases the various measures are different ℓ_p norms. We address this problem by introducing the concept of an all-norm ρ-approximation algorithm, which supplies one solution that guarantees ρ-approximation to all ℓ_p norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are m machines and n jobs, each job is associated with a subset of the machines and should be assigned to one of them. Previous work considered approximation algorithms for each norm separately. Lenstra et al. [Math. Program. 46 (1990) 259–271] showed a 2-approximation algorithm for the problem with respect to the ℓ_∞ norm. For any fixed ℓ_p norm the previously known approximation algorithm has a performance of θ(p). We provide an all-norm 2-approximation polynomial algorithm for the restricted assignment problem. On the other hand, we show that for any given ℓ_p norm (p>1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given ℓ_p norm a FPTAS for any fixed number of machines.     

Minimal cyclic codes of length pq

Explicit expressions for all the 3n+2 primitive idempotents in the ring R_pⁿq=GF(ℓ)[x]/(x^pnq−1), where p,q,ℓ are distinct odd primes, ℓ is a primitive root modulo pⁿ and q both, , are obtained. The dimension, generating polynomials and the minimum distance of the minimal cyclic codes of length pⁿq over GF(ℓ) are also discussed.     

Linear time algorithm for the longest common repeat problem

Given a set of strings U={T₁,T₂,…,T_ℓ}, the longest common repeat problem is to find the longest common substring that appears at least twice in each string of U. We also consider reversed and reverse-complemented repeats as well as normal repeats. We present a linear time algorithm for the longest common repeat problem.     

On nonautonomous linear systems of differential and difference equations with -symmetric coefficient matrices

Let denote the set of continuous n×n matrices on an interval . We say that is a nontrivial k-involution if where ζ=e^-2πi/k, d₀+d₁++d_k-1=n, and with . We say that is R-symmetric if R(t)A(t)R^-1(t)=A(t), , and we show that if A is R-symmetric then solving x^′=A(t)x or x^′=A(t)x+f(t) reduces to solving k independent d_ℓ×d_ℓ systems, 0ℓk-1. We consider the asymptotic behavior of the solutions in the case where . Finally, we sketch analogous results for linear systems of difference equations.     

On the chromatic number of random graphs

In this paper we consider the classical Erdős–Rényi model of random graphs G_n,p. We show that for p=p(n)n^−3/4−δ, for any fixed δ>0, the chromatic number χ(G_n,p) is a.a.s. ℓ, ℓ+1, or ℓ+2, where ℓ is the maximum integer satisfying 2(ℓ−1)log(ℓ−1)p(n−1).     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

Pattern Matching with Swaps

Let a text string T of n symbols and a pattern string P of m symbols from alphabet Σ be given. A swapped version T′ of T is a length n string derived from T by a series of local swaps (i.e., t′_ℓ ← t_ℓ + 1 and t′_ℓ + 1 ← t_ℓ), where each element can participate in no more than one swap. The pattern matching with swaps problem is that of finding all locations i for which there exists a swapped version T′ of T with an exact matching of P in location i of T′. It has been an open problem whether swapped matching can be done in less than O(nm) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time o(nm). We present an algorithm whose time complexity is O(nm^1/3 log m log σ) for a general alphabet Σ, where σ = min(m,Σ).     

Estimates of Distances Between Sums of the Spaces ℓ<Stack><Subscript>n</Subscript><Superscript>p</Superscript></Stack>. II

We study classical, modified, and weak Banach-Mazur distances between sums of the spaces ℓ _n ^p . We calculate explicitly the classical and weak Banach-Mazur distances between sums of the spaces ℓ _n ^p and obtain bounds for ratios of distances between sums of the spaces ℓ _n ^p . Bibliography: 14 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 303, 2003, pp. 203–217.     

Algorithms for finding distance-edge-colorings of graphs

For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.     

Maximal ℓ-Frattini quotients of ℓ-Poincaré duality groups of dimension 2

Any morphism of profinite groups has maximal ℓ-Frattini quotients

A simple proof of the uniqueness theorem in impedance tomography

Let·(σ(x)u)= 0 in D R³, where D is a bounded domain with a smooth boundary. Suppose that σ ≥ m> 0, σ H³(D), where H^ℓ is the Sobolev space. Let the set {u, σu_N} be given on Γ for all u H^3/2(Γ), where u_N is the normal derivative of u on Γ.     

Complementary ℓ1-Graphs Embeddable in the Half-Cube

A finite connected graph is called an ℓ₁-graph if it can be isometrically embedded into the space ℓ₁. We complete the classification of pairs of complementaryℓ₁ -graphs started by Deza and Huang, and continued by Shpectorov.     

On the Common Substring Alignment Problem

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S₁, S₂ … S_c and a target string T, Y is a common substring of all strings S_i, that is, S_i = B_iYF_i. The goal is to compute the similarity of all strings S_i with T, without computing the part of Y again and again. Using the classical dynamic programming tables, each appearance of Y in a source string would require the computation of all the values in a dynamic programming table of size O(nℓ) where ℓ is the size of Y. Here we describe an algorithm which is composed of an encoding stage and an alignment stage. During the first stage, a data structure is constructed which encodes the comparison of Y with T. Then, during the alignment stage, for each comparison of a source S_i with T, the pre-compiled data structure is used to speed up the part of Y. We show how to reduce the O(nℓ) alignment work, for each appearance of the common substring Y in a source string, to O(n)-at the cost of O(nℓ) encoding work, which is executed only once.     

Gâteaux Differentiability of Bump Functions in Banach Spaces

Upper estimates for the order of Gâteaux smoothness of bump functions in Orlicz spaces ℓ_M(Γ) and Lorentz spaces d(w, p, Γ), Γ uncountable, are obtained.     

Sparse hypergraphs and pebble game algorithms

A hypergraph G=(V,E) is (k,ℓ)-sparse if no subset V^′V spans more than k|V^′|−ℓ hyperedges. We characterize (k,ℓ)-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behavior in terms of the sparsity parameters k and ℓ. Our constructions extend the pebble games of Lee and Streinu [A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (8) (2008) 1425–1437] from graphs to hypergraphs.     

Sparsest solutions of underdetermined linear systems via -minimization for

We present a condition on the matrix of an underdetermined linear system which guarantees that the solution of the system with minimal ℓ_q-quasinorm is also the sparsest one. This generalizes, and slightly improves, a similar result for the ℓ₁-norm. We then introduce a simple numerical scheme to compute solutions with minimal ℓ_q-quasinorm, and we study its convergence. Finally, we display the results of some experiments which indicate that the ℓ_q-method performs better than other available methods.     

The asymptotic behavior of nonoscillatory solutions of nonlinear neutral type difference equations

In this paper, the authors study the asymptotic behavior of solutions of second-order neutral type difference equations of the form

Δ²(y_n+py_n−k)+f(n,y_n−ℓ)=0,n