Optimal broadcast domination in polynomial time

Broadcast domination was introduced by Erwin in 2002, and it is a variant of the standard dominating set problem, such that different vertices can be assigned different domination powers. Broadcast domination assigns an integer power f(v)?0 to each vertex v of a given graph, such that every vertex of the graph is within distance f(v) from some vertex v having f(v)?1. The optimal broadcast domination problem seeks to minimize the sum of the powers assigned to the vertices of the graph. Since the presentation of this problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, we show that optimal broadcast domination is actually in P, and we give a polynomial time algorithm for solving the problem on arbitrary graphs, using a non-standard approach.     

Polynomial approximation, local polynomial convexity, and degenerate CR singularities

We begin with the following question: given a closed disc and a complex-valued function , is the uniform algebra on generated by z and F equal to ? When F∈C¹(D), this question is complicated by the presence of points in the surface that have complex tangents. Such points are called CR singularities. Let p∈S be a CR singularity at which the order of contact of the tangent plane with S is greater than 2; i.e. a degenerate CR singularity. We provide sufficient conditions for S to be locally polynomially convex at the degenerate singularity p. This is useful because it is essential to know whether S is locally polynomially convex at a CR singularity in order to answer the initial question. To this end, we also present a general theorem on the uniform algebra generated by z and F, which we use in our investigations. This result may be of independent interest because it is applicable even to non-smooth, complex-valued F.     

Ternary analogues of Lie and Malcev algebras

We consider two analogues of associativity for ternary algebras: total and partial associativity. Using the corresponding ternary associators, we define ternary analogues of alternative and assosymmetric algebras. On any ternary algebra the alternating sum [a, b, c] = abc − acb − bac + bca + cab − cba (the ternary analogue of the Lie bracket) defines a structure of an anticommutative ternary algebra. We determine the polynomial identities of degree ?7 satisfied by this operation in totally and partially associative, alternative, and assosymmetric ternary algebras. These identities define varieties of ternary algebras which can be regarded as ternary analogues of Lie and Malcev algebras. Our methods involve computational linear algebra based on the representation theory of the symmetric group.     

Asymptotic Distribution of Nodes for Near-Optimal Polynomial Interpolation on Certain Curves in R 2

Let E\subset \Bbb R ^s be compact and let d _n ^E denote the dimension of the space of polynomials of degree at most n in s variables restricted to E . We introduce the notion of an asymptotic interpolation measure (AIM). Such a measure, if it exists , describes the asymptotic behavior of any scheme τ _n ={ \bf x _k,n } _k=1 ^dnE , n=1,2,\ldots , of nodes for multivariate polynomial interpolation for which the norms of the corresponding interpolation operators do not grow geometrically large with n . We demonstrate the existence of AIMs for the finite union of compact subsets of certain algebraic curves in R ² . It turns out that the theory of logarithmic potentials with external fields plays a useful role in the investigation. Furthermore, for the sets mentioned above, we give a computationally simple construction for ``good' interpolation schemes. November 9, 2000. Date revised: August 4, 2001. Date accepted: September 14, 2001.     

Asymptotics of zeros of polynomials arising from rational integrals

We prove that the zeros of the polynomials Pm(a) of degree m, defined by Boros and Moll via

     

极限环的表达式和计算

本文提出一种解析法和数值法相结合的方法，用来计算多项式微分系统的极限环，极限环表示为x=∑k≥0(ak cos kφ bk sin kφ),y=∑k≥0(ck cos kφ dk sin kφ)，先用解析法求出小参数时极限环的初始表达式，然后用增量法和迭代法求出任意参数时极限环满足给定精度的表达式，半稳定极限环和分叉值也可以计算。     

A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms

The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and; ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scale-invariant condition number associated with m × n constraint matrix of the LP. In this paper, we establish a relationship between these bounds by showing that the first one can be majorized by the second one. We also establish a geometric result about the central path which gives a rigorous justification based on the curvature of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the central path consists of long but straight continuous parts while the remaining curved part is relatively “short”. R. D. C. Monteiro was supported in part by NSF Grants CCR-0203113 and CCF-0430644 and ONR grant N00014-05-1-0183. T. Tsuchiya was supported in part by Japan-US Joint Research Projects of Japan Society for the Promotion of Science “Algorithms for linear programs over symmetric cones” and the Grants-in-Aid for Scientific Research (C) 15510144 of Japan Society for the Promotion of Science.     

Atomic decompositions for tensor products and polynomial spaces

We study the existence of atomic decompositions for tensor products of Banach spaces and spaces of homogeneous polynomials. If a Banach space X admits an atomic decomposition of a certain kind, we show that the symmetrized tensor product of the elements of the atomic decomposition provides an atomic decomposition for the symmetric tensor product , for any symmetric tensor norm μ. In addition, the reciprocal statement is investigated and analogous consequences for the full tensor product are obtained. Finally we apply the previous results to establish the existence of monomial atomic decompositions for certain ideals of polynomials on X.     

基于多项式模型法的低端数码相机的颜色特性化

近年来随着数字技术,以及彩色数字图像输入输出设备的不断发展和广泛使用,颜色在不同的设备之间精确的传递或再现成为该领域的重要课题。本论文以彩色数码相机特性化为研究内容,采用多项式转换方法,研究了多项式回归模型不同系数矩阵、不同训练样本对数码相机特性化精度的影响,得出了系数矩阵为11×3多项式模型时误差较小(2.874ΔE*ab)的结论,达到了实用水平。     

General local convergence theory for a class of iterative processes and its applications to Newton’s method

General local convergence theorems with order of convergence r≥1$r\ge 1$ are provided for iterative processes of the type _xn+1=T_xn$x_{n+1}=T{x}_n$, where T:D⊂X→X$T:D\subset X\to X$ is an iteration function in a metric space X$X$. The new local convergence theory is applied to Newton iteration for simple zeros of nonlinear operators in Banach spaces as well as to Schröder iteration for multiple zeros of polynomials and analytic functions. The theory is also applied to establish a general theorem for the uniqueness ball of nonlinear equations in Banach spaces. The new results extend and improve some results of [K. Do?ev, Über Newtonsche Iterationen, C. R. Acad. Bulg. Sci. 36 (1962) 695–701; J.F. Traub, H. Wo?niakowski, Convergence and complexity of Newton iteration for operator equations, J. Assoc. Comput. Mach. 26 (1979) 250–258; S. Smale, Newton’s method estimates from data at one point, in: R.E. Ewing, K.E. Gross, C.F. Martin (Eds.), The Merging of Disciplines: New Direction in Pure, Applied, and Computational Mathematics, Springer, New York, 1986, pp. 185–196; P. Tilli, Convergence conditions of some methods for the simultaneous computation of polynomial zeros, Calcolo 35 (1998) 3–15; X.H. Wang, Convergence of Newton’s method and uniqueness of the solution of equations in Banach space, IMA J. Numer. Anal. 20 (2000) 123–134; I.K. Argyros, J.M. Gutiérrez, A unified approach for enlarging the radius of convergence for Newton’s method and applications, Nonlinear Funct. Anal. Appl. 10 (2005) 555–563; M. Giusti, G. Lecerf, B. Salvy, J.-C. Yakoubsohn, Location and approximation of clusters of zeros of analytic functions, Found. Comput. Math. 5 (3) (2005) 257–311], and others.