On an inverse problem of entropy othimization and related questions

In a fundamental paper Arov and Krein studied entropy minimization problems over a set of matrix-valued Schur functions which arises from a fractional linear transformation the generating matrix-valued function of which is a j_pq -inner function.Our paper handles the corresponding inverse problem: If a p x q Schur function f is given, then the problem is to determine all j_pq -inner functions for which f turns out to be the associatedentropy-minimal function     

Completion problems forj pq-inner functions. II

This paper is a continuation of [AFK]. The notations used there will be preserved. We will consider completion problems forj _pq-inner polynomials which have a prescribed structure, namely for such matrix polynomials which have a prescribed structure, namely for such matrix polynomials which can be considered as suitably normalized resolvent matrix of an appropriate non-degenerate matricial Schur problem.     

On surface area measures of convex bodies

The set L _j of jth-order surface area measures of convex bodies in d-space is well known for j=d–1. A characterization of L _j was obtained by Firey and Berg. The determination of L _j, for j{2, ..., d–2}, is an open problem. Here we show some properties of L _j concerning convexity, closeness, and size. Especially we prove that the difference set L _j–L _j is dense (in the weak topology) in the set of signed Borel measures on the unit sphere which have barycentre 0.     

Natural frequencies of a multi-degree-of-freedom vibration system

A chain structured mass-spring vibration system with N degrees of freedom is considered where massesM _j = m_jm = m/j and spring stiffnesses k_j = c_jk = (N + 1 - j)k, j = 1, …, N, have been applied. The conjecture of Mikota [1] on the natural frequencies is discussed showing how difficult it is to find an explicit solution of the related eigenvalue problem. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Finding cheapest cycles in vertex-weighted quasi-transitive and extended semicomplete digraphs

We consider the problem of finding a minimum cost cycle in a digraph with real-valued costs on the vertices. This problem generalizes the problem of finding a longest cycle and hence is NP-hard for general digraphs. We prove that the problem is solvable in polynomial time for extended semicomplete digraphs and for quasi-transitive digraphs, thereby generalizing a number of previous results on these classes. As a byproduct of our method we develop polynomial algorithms for the following problem: Given a quasi-transitive digraph D with real-valued vertex costs, find, for each j=1,2,…,|V(D)|, j disjoint paths P₁,P₂,…,P_j such that the total cost of these paths is minimum among all collections of j disjoint paths in D.     

20-relative neighborhood graphs are hamiltonian

For any two points p and q in the Euclidean plane, define LUN_pq = { v | v ∈ R², d_pv < d_pq and d_qv < d_pq}, where d_uv is the Euclidean distance between two points u and v . Given a set of points V in the plane, let LUN_pq(V) = V ∩ LUN_pq. Toussaint defined the relative neighborhood graph of V, denoted by RNG(V) or simply RNG, to be the undirected graph with vertices V such that for each pair p,q ∈ V, (p,q) is an edge of RNG(V) if and only if LUN_pq (V) = ?. The relative neighborhood graph has several applications in pattern recognition that have been studied by Toussaint. We shall generalize the idea of RNG to define the k-relative neighborhood graph of V, denoted by kRNG(V) or simply kRNG, to be the undirected graph with vertices V such that for each pair p,q ∈ V, (p,q) is an edge of kRNG(V) if and only if | LUN_pq(V) | < k, for some fixed positive number k. It can be shown that the number of edges of a kRNG is less than O(kn). Also, a kRNG can be constructed in O(kn₂) time. Let E_c = {e_pq| p ∈ V and q ∈ V}. Then G_c = (V,E_c) is a complete graph. For any subset F of E_c, define the maximum distance of F as max_epq∈Fd_pq. A Euclidean bottleneck Hamiltonian cycle is a Hamiltonian cycle in graph G_c whose maximum distance is the minimum among all Hamiltonian cycles in graph G_c. We shall prove that there exists a Euclidean bottleneck Hamiltonian cycle which is a subgraph of 20RNG(V). Hence, 20RNGs are Hamiltonian.     

A note about the cyclotomic polynomial Фpq（x） and some related results

Abstract. The expression of cyclotomic polynomial Фpq （x） is concerned for a long time. A simple and explicit expression of Фpq （x） in Z[x] has been showed. The form of the factors of Фpq （x） over F2 and the upper, lower bounds of their Hamming weight are provided.     

On the Continuous Dependence of the Exterior Dirichlet Problem on the Boundary

We consider a sequence of exterior domains D_j,j∈ℕ₀, and assume that the boundaries ∂D_j converge to ∂D₀ with respect to the Hausdorff distance. We investigate solutions to the exterior Dirichlet problem for the Laplace equation and for the Helmholtz equation in these domains. Assuming convergence of the boundary data and D_j⊂D₀, j∈ℕ, then, by essentially using the method of Perron, we show that the solutions in the domains D_j converge to the solution in the domain D₀ with respect to the maximum norm. We prove the same result in case that the requirement D_j⊂D₀,j∈ℕ, is replaced by an equicontinuity property of all barrier functions to all boundary points. © 1997 by B. G. Teubner Stuttgart–John Wiley & Sons Ltd. Math. Meth. Appl. Sci., Vol. 20, 707–716 (1997)     

Determination of natural modes of linear mass-spring vibration systems by Laguerre polynomials

Chain structured vibration systems with N degrees of freedom with masses m_j and stiffnesses k_j have been discussed in detail [1]. Some of them can be solved explicitly, others only numerically. Here, an inverse problem is considered: How m_j, k_j, j = 1, …, N, should be chosen such that the related eigenvalue/eigenvector-problem can be solved by Laguerre polynomials? (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds

We present new approximation algorithms for the problem of scheduling precedence-constrained jobs on parallel machines that are uniformly related. That is, there arenjobs andmmachines; each jobjrequiresp_junits of processing, and is to be processed on one machine without interruption; if it is assigned to machinei, which runs at a given speeds_i, it takesp_j/s_itime units. There also is a partial order on the jobs, wherej kimplies that jobkmay not start processing until jobjhas been completed. We consider two objective functions:C_max = max_j C_j, whereC_jdenotes the completion time of jobj, and ∑_jw_jC_j, wherew_jis a weight that is given for each jobj. For the first objective, the best previously known result is an -approximation algorithm, which was shown by Jaffe more than 15 years ago. We give anO(log m)-approximation algorithm. We also show how to extend this result to obtain anO(log m)-approximation algorithm for the second objective, albeit with a somewhat larger constant. These results also extend to settings in which each jobjhas a release dater_jbefore which the job may not begin processing. In addition, we obtain stronger performance guarantees if there are a limited number of distinct speeds. Our results are based on a new linear programming-based technique for estimating the speed at which each job should be run, and a variant of the list scheduling algorithm of Graham that can exploit this additional information.     

A Bayesian Decision Theory Approach to Classification Problems

We address the classification problem where an item is declared to be from populationπ_jif certain of its characteristicsvare assumed to be sampled from the distribution with pdf f_j(vθ_j), wherej=1, 2, …, m. We first solve the two population classification problem and then extend the results to the generalmpopulation classification problem. Usually only the form of the pdf's is known. To use the classical classification rule the parameters,θ_j, must be replaced by their estimates. In this paper we allow the parameters of the underlying distributions to be generated from prior distributions. With this added structure, we obtain Bayes rules based on predictive distributions and these are completely determined. Using the first-order expansion of the predictive density, where the coefficients of powers ofn⁻¹remain uniformly bounded innwhen integrated, we obtain an asymptotic bound for the Bayes risk.     

Function Spaces with Exponential Weights I

In this paper we define weighted function spaces of type B^s_pq(u) and F^s_pq(u) on the Euclidean space IRⁿ, where u is a weight function of at most exponential growth. In particular, u(x) = exp(±|χ|) is an admissible weight. We prove some basic properties of these spaces, such as completeness and density of the smooth functions.     

Discrete-event dynamic systems: The strictly convex case

Given the observed outputg _j of a discrete-event system, a classical problem is to find a matrix realisationg _j =cA ^jb withA of least possible dimension. When the sequenceg _j is convex and ultimately 1-periodic, a linear-time algorithm suffices to construct such a realisation over the algebra (R, max, +). When the transient is strictly convex, this realisation is minimal-dimensional.     

Rearrangement invariant subspaces of Lorentz function spaces

The main result is that for 2≦q≦p<∞ the only subspaces of the Lorentz function spaceL _pq [0, 1] which are isomorphic to r.i. function spaces on [0, 1] are, up to equivalent renormings,L _pq [0, 1] andL ₂[0, 1].     

A constant factor approximation algorithm for the fault-tolerant facility location problem

We consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. In this generalization, every demand point j must be served by r_j facilities instead of just one. The facilities other than the closest one are “backup” facilities for that demand, and any such facility will be used only if all closer facilities (or the links to them) fail. Hence, for any demand point, we can assign nonincreasing weights to the routing costs to farther facilities. The cost of assignment for demand j is the weighted linear combination of the assignment costs to its r_j closest open facilities. We wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand j. We obtain a factor 4 approximation to this problem through the application of various rounding techniques to the linear relaxation of an integer program formulation. We further improve the approximation ratio to 3.16 using randomization and to 2.41 using greedy local-search type techniques.     

On an Approximate Solution of the Dirichlet Problem for the Generalized Laplacian

For an arbitrary differential operator P of order p on an open set X ? R ⁿ, the Laplacian is defined by Δ = P*P. It is an elliptic differential operator of order 2p provided the symbol mapping of P is injective. Let O be a relatively compact domain in X with smooth boundary, and B_j(j = 0…,p — 1) be a Dirichlet system of order p ? 1 on ?O. By {C_j} we denote the Dirichlet system on ?O adjoint for {B_j} with respect to the Green formula for P. The Hardy space H²(O) is defined to consist of all the solutions f of Δf = 0 in O of finite order of growth near the boundary such that the weak boundary values of the expression {B_jf} and {C_j(Pf)} belong to the Lebesgue space L²(?O). Then the Dirichlet problem consists of finding a solution f ? H²(O) with prescribed data {B_jf} on ?O. We develop the classical Fischer-Riesz equations method to derive a solvability condition of the Dirichlet problem as well as an approximate formula for solutions.     

Inverse Sturm–Liouville spectral problem on symmetric star‐tree

A spectral problem for the Sturm–Liouville equation on the edges of an equilateral regular star‐tree with the Dirichlet boundary conditions at the pendant vertices and Kirchhoff and continuity conditions at the interior vertices is considered. The potential in the Sturm–Liouville equation is a real–valued square summable function, symmetrically distributed with respect to the middle point of any edge. If {λ_j}is a sequence of real numbers, necessary and sufficient conditions for {λ_j}to be the spectrum of the problem under consideration are established. Copyright © 2013 John Wiley & Sons, Ltd.     

About Approximation Numbers in Function Spaces

Sharp estimates for the approximation numbers of embeddings between the function spacesB^s_pqandF^s_pqon domains are given in a case not thoroughly studied by Edmunds and Triebel. Corresponding sharp estimates are also obtained for the counterparts of that case in the weighted function space setting.     

Competitive Algorithms for Relaxed List Update and Multilevel Caching

We study relaxed list update problem (RLUP), in which access requests are made to items stored in a list. The cost to access the jth item x_j is c_j, where c_i ≤ c_{i + 1} for all i. After the access, x_j can be repeatedly swapped, at no cost, with any item that precedes it in the list. This problem was introduced by Aggarwal et al. (1987, “Proc. 19th Symp. Theory of Computing,” pp. 305–313) as a model for the management of hierarchical memory that consists of a number of caches of increasing size and access time. They also proved that a version of LRU is C-competitive, for some C, for a restricted class of cost functions. We give an efficient offline algorithm that computes the optimal strategy for RLUP. We also show an elegant characterization of work functions for RLUP. We prove that move-to-front (MTF) is optimally competitive for RLUP with any cost function. An interesting feature of the proof is that it does not involve any estimates on the competitive ratio. Finally, we give a lower bound on the competitive ratio of online algorithms for RLUP.     

Continuity Envelopes of Spaces of Generalized Smoothness in the Critical Case

The continuity envelope for the Besov and Triebel-Lizorkin spaces of generalized smoothness B _pq ^(s,Ψ)(ℝ ⁿ ) and F _pq ^(s,Ψ)(ℝ ⁿ ), respectively, are computed in the critical case s=n/p, provided that Ψ satisfies an appropriate critical condition. Surprisingly, in this critical situation, the corresponding optimal index is ∞, when compared with all the known results. Moreover, in the particular case of the classical spaces, we solve an open problem posed by Haroske in Envelopes and Sharp Embeddings of Function Spaces, Research Notes in Mathematics, vol. 437, Chapman & Hall, Boca Raton, 2007. As an immediate application of our results we give an upper estimate for approximation numbers of related embeddings.