Hausdorff measures, dimensions and mutual singularity

Let be a metric space. For a probability measure on a subset of and a Vitali cover of , we introduce the notion of a -Vitali subcover , and compare the Hausdorff measures of with respect to these two collections. As an application, we consider graph directed self-similar measures and in satisfying the open set condition. Using the notion of pointwise local dimension of with respect to , we show how the Hausdorff dimension of some general multifractal sets may be computed using an appropriate stochastic process. As another application, we show that Olsen's multifractal Hausdorff measures are mutually singular.

     

A stability property for locally uniformly rotund renorming

It is proved that C(K,E) (the space of all continuous functions on a Hausdorff compact space K taking values in a Banach space E) admits an equivalent locally uniformly rotund norm if C(K) and E do so. Moreover, if the equivalent LUR norms on C(K) and E are lower semicontinuous with respect to some weak topologies, the LUR norm on C(K,E) can be chosen to be lower semicontinuous with respect to an appropriate weak topology. As a consequence we prove that if X and Y are two Hausdorff compacta and C(X), C(Y) admit equivalent (pointwise lower semicontinuous) LUR norms, then so does C(X×Y).     

A Little More on Coz-Unique Frames

Coz-unique frames were defined and characterized by Banaschewski and Gilmour (J Pure Appl Algebra 157:1–22, 2001). In this note we give further characterizations of these frames along the lines of characterizations of absolutely z-embedded spaces obtained by Blair and Hager (Math Z 136:41–52, 1974) on the one hand, and by Hager and Johnson (Canad J Math 20:389–393, 1968) on the other. We also extend to frames certain characterizations of z-embedded spaces; namely, we give a characterization of coz-onto frame homomorphisms in terms of normal covers.      

直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性

给定一个简单图G和正整数κ,具有完美匹配的图G的κ-导出匹配划分是对顶点集V(C)的一个κ-划分(V1,V2,...,Vκ),其中对每一个i(1≤i≤κ),由Vi导出的G的子图G[Vi]是1-正则的.κ-导出匹配划分问题是指对给定的图G,判定G是否存在一个κ-导出匹配划分.令M1,M2…,Mκ为图G的κ个导出匹配,如果V(M1)UV(M2)∪...∪V(Mκ)=V(G),则我们称{M1,M2,...,Mκ}是G的κ-导出匹配覆盖.κ-导出匹配覆盖问题是指对给定的图G,判定G是否存在κ-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2一划分问题和导出匹配2-覆盖问题都是NP-完全的.     

Local Clique Covering of Claw‐Free Graphs

A clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a clique covering is called the local clique cover number of G and is denoted by lcc(G). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well‐known problems are discussed. In particular, it is proved that the local clique cover number of every claw‐free graph is at most , where Δ is the maximum degree of the graph and c is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1–3)(2000), 17–26), we prove that the clique cover number of every connected claw‐free graph on n vertices with the minimum degree δ, is at most , where c is a constant.     

Applications of k-covers

We investigate a role of k-covers in selection principles theory. Some results about relationships between Ramsey theory and game theory and selection principles that involve k-covers are also given.     

Generalized cover facet inequalities for the generalized assignment problem

The generalized assignment problem is that of finding an optimal assignment of agents to tasks, where each agent may be assigned multiple tasks and each task is performed exactly once. This is an NP-complete problem. Algorithms that employ information about the polyhedral structure of the associated polytope are typically more effective for large instances than those that ignore the structure. A class of generalized cover facet-defining inequalities for the generalized assignment problem is derived. These inequalities are based upon multiple knapsack constraints and are derived from generalized cover inequalities.     

精确覆盖问题的加权分治算法

精确覆盖问题是组合优化中经典的NP-Hard问题之一,其在诸多领域具有广泛的应用价值。本文首先研究了精确覆盖问题的数学性质,并根据数学性质提出相应的分支降阶规则以缩小问题的规模;接着设计了一个基于分支降阶的回溯算法求解该问题;然后运用常规技术分析得出该精确算法的时间复杂度为O(1.4656^k);最后运用加权分治技术对该算法的时间复杂度进行分析,将该算法的时间复杂度降为O(1.3842^k)。文章最后通过一个示例进一步阐述该算法的原理,并与其他精确算法进行了对比分析,研究结果表明该算法是可行的,也是有效的。     

Lamb Problem for a Half-Space Covered with a Two-Axially Prestretched Layer

Within the framework of a piecewise homogeneous body model, with the use of the three-dimensional linearized theory of elastic waves in initially stressed bodies, an approach for investigating the Lamb problem for a half-space covered with a layer is developed. It is assumed that the half-space and the cover layer have two-axial initial stresses operating parallel to the layer plane. To the free face of the layer, a normal point force changing harmonically with time is applied. For solving the corresponding boundary value problems, the double-exponential Fourier transformation is employed. An algorithm for obtaining numerical results is proposed, which is examined in particular cases. Numerical results for the influence of prestretching the cover layer on the interfacial stresses are presented.     

一类最小支撑树的逆问题及其求解方法

本文针对传统的基于边的最小支撑树逆问题，提出了一类基于点边更新策略的最小支撑树逆问题．更新一个点是指减少与此点相关联的某些边的权值．根据是否含有更新点的费用，考虑了两类模型，它们均可转化为森林上的最小(费用)点覆盖的求解问题，算法的复杂性都是O(mn)，其中m=|E|n=|V|。