Greedy Families for Linear Objective Functions

The following structures are characterized: for which families of feasible subsets of a finite set does the greedy algorithm return the optimum subset independent of the weighting of a linear objective function on the set? Characteristically, the family must then have as bases the bases of a matroid (even when the feasible family is not a system of independent sets), and for every accessible feasible set X, the subset of elements by which X can be augmented is the complement of a proper closed set of the matroid. Another characterization is given for a family in which the greedy algorithm gives the optimum subset at every stage: the family is that of the bases of a sequence of matroid strong maps resulting in a natural duality theory. Theoretical underpinnings are given for several classical instances such as the algorithms of Kruskal, Prim, and Dijkstra.     

On Optimization of Tax Functions

Mathematical Notes - We consider the problem of maximization of an integral functional on the space of increasing functions, which is motivated by economic concerns for tax mechanisms optimization....     

集值映射向量优化问题ε-超有效解集的连通性

本文在赋范向量空间中讨论集值映射向量优化问题的ε-超有效性，在锥-半连续和广义锥-次类凸的假设条件下，获得了ε-超有效点(解)集的连通性结果．     

On Optimization Problems with Set-Valued Objective Maps: Existence and Optimality

In this paper, we consider constrained optimization problems with set-valued objective maps. First, we define three types of quasi orderings on the set of all non-empty subsets of n-dimensional Euclidean space. Second, by using these quasi orderings, we define the concepts of lower semi-continuity for set-valued maps and investigate their properties. Finally, based on these results, we define the concepts of optimal solutions to constrained optimization problems with set-valued objective maps and we give some conditions under which these optimal solutions exist to the problems and give necessary and sufficient conditions for optimality.     

p-Harmonic Maps and Convex Functions

p-harmonic maps (p ' 2) between Riemannian manifolds are investigated. Some theorems of Liouville type are given for such maps when target manifolds have convex functions.     

集合上的递归函数

本文在Ｊｅｎｓｅｎ和Ｋａｒｐ工作的基础上引进了集合上的递归函数的概念．研究了递归集函数的初步性质，讨论了递归集函数与Ｊｅｎｓｅｎ和Ｋａｒｐ定义的原始递归集函数及递归数论函数之间的关系，并给出了ＺＦＣ的可定义集模型上递归集函数的范式定理．     

Cantor集合上的连续自映射

本文证明了Ｃａｎｔｏｒ集Ｃ上所有拓扑共轭于（单边的）有限型子移位的连续自映射的集合在H中稠密，此外Ｃ上每个拓扑传递（混合）映射均可被拓扑共轭于有限型子移位的拓仆传递（混合）映射一致逼近．     

A Tight Analysis of the Greedy Algorithm for Set Cover

We establish significantly improved bounds on the performance of the greedy algorithm for approximatingset cover. In particular, we provide the first substantial improvement of the 20-year-old classical harmonic upper bound,H(m), of Johnson, Lovász, and Chvátal, by showing that the performance ratio of the greedy algorithm is, in fact,exactlyln m − ln ln m + Θ(1), wheremis the size of the ground set. The difference between the upper and lower bounds turns out to be less than 1.1. This provides the first tight analysis of the greedy algorithm, as well as the first upper bound that lies belowH(m) by a function going to infinity withm. We also show that the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on theintegrality gap. Our improvements result from a new approach which might be generally useful for attacking other similar problems.     

On the Linear Dependence of a Finite Set of Additive Functions

In this note we prove the following: Let n?≥ 2 be a fixed integer. A system of additive functions ${A_{1},A_{2},\ldots,A_{n}:\mathbb{R} \to\mathbb{R}}$ is linearly dependent (as elements of the ${\mathbb{R}}$ vector space ${\mathbb{R}^{\mathbb{R}}}$ ), if and only if, there exists an indefinite quadratic form ${Q:\mathbb{R}^{n}\to\mathbb{R} }$ such that ${Q(A_{1}(x),A_{2}(x),\ldots,A_{n}(x))\geq 0}$ or ${Q(A_{1}(x),A_{2}(x),\ldots,A_{n}(x))\leq 0}$ holds for all ${x\in\mathbb{R}}$ .     

关于集值映射的极大极小定理

在锥序线性空间中建立了关于集值映射的不动点型极大极小定理,从而扩大了关于极大极小定理的应用范围     

On Thermodynamics of Rational Maps. II: Non-Recurrent Maps

The pressure function p(t) of a non-recurrent map is real analyticon some interval (0,t_*) with t_* strictly greater than the dimensionof the Julia set. The proof is an adaptation of the well knowntower techniques to the complex dynamics situation. In general,p(t) need not be analytic on the whole positive axis.     

Nonsmooth Calculus of Semismooth Functions and Maps

In this paper, we pursue two goals. First, we find exact relationships between the three concepts of semismooth sets, functions, and maps. Then, we consider the nonsmooth calculus of these notions. Particularly, we prove that the Mordukhovich and linear subdifferentials (coderivatives) are equal for the semismooth functions (maps). Several examples are presented to illustrate the results of the paper.     

保持算子乘积谱函数的映射

设A和B为无限维复Banach空间上的标准算子代数,记ΔR(·)为下列谱函数之一σR(·),σRl(·),σRr(·),σRl(·)∩σRr(·),(a)σR(·),ησR(·),σRp(·),σRc(·),σRap(·),σRs(·),σRap(·)∩σRs(·),σRp(·)∩σRc(·),σRp(·)∪σRc(·),其中R=A或B.证明了A和B之间的每个保持算子Jordan三乘积(算子乘积)之谱函数ΔR(·)的满射φ必有形式φ=επ,其中ε是1的立方根(1的平方根)而π或者是A和B之间的代数同构,或者是代数反同构.也获得不定度规空间上的标准算子代数之间保持算子斜乘积之谱函数的映射的完全刻画.     

保持算子乘积谱函数的映射

设A和B为无限维复Banach空间上的标准算子代数,记Δ~R(·)为下列谱函数之一:σ~R(·),σ_l~R(·),σ_r~R(·),σ_l~R(·)∩σ_r~R(·),(?)σ~R(·),(?)σ~R(·),σ_p~R(·),σ_c~R(·),σ_(ap)~R(·),σ_s~R(·),σ_(ap)~R(·)∩σ_s~R(·),σ_p~R(·)∩σ_c~R(·),σ_p~R(·)∪σ_c~R(·),其中R=A或B.证明了A和B之间的每个保持算子Jordan三乘积(算子乘积)之谱函数△~R(·)的满射Φ必有形式Φ=(?)π,其中(?)是1的立方根(1的平方根)而π或者是A和B之间的代数同构,或者是代数反同构.也获得不定度规空间上的标准算子代数之间保持算子斜乘积之谱函数的映射的完全刻画.     

The Julia Set of Hénon Maps

In this paper we investigate the support of the unique measure of maximal entropy of complex Hénon maps, J^*. The main question is whether this set is the same as the analogue of the Julia set J. July 4, 2005. The author is supported by an NSF grant     

The Greedy Independent Set in a Random Graph with Given Degrees

We analyse the size of an independent set in a random graph on n vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as (the jamming constant), expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges in probability to the jamming constant as . The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 565–586, 2017     

关于向量集值优化的Benson真有效性

对广义锥次数凸向量集值优化问题Benson真有效性解的标量化问题进行了研究,借助于一种新的择一性定理建立了广义锥次类凸向是集值优化问题Benson真有效解的Lagrange乘子型定理并讨论了乘子型对偶问题。