Unimodularity of the Clar number problem

We study the generalization to bipartite and 2-connected plane graphs of the Clar number, an optimization model proposed by Clar [E. Clar, The Aromatic Sextet, John Wiley & Sons, London, 1972] to compute indices of benzenoid hydrocarbons. Hansen and Zheng [P. Hansen, M. Zheng, The Clar number of a benzenoid hydrocarbon and linear programming, J. Math. Chem. 15 (1994) 93–107] formulated the Clar problem as an integer program and conjectured that solving the linear programming relaxation always yields integral solutions. We establish their conjecture by proving that the constraint matrix of the Clar integer program is always unimodular. Interestingly, in general these matrices are not totally unimodular. Similar results hold for the Fries number, an alternative index for benzenoids proposed earlier by Fries [K. Fries, Uber Byclische Verbindungen und ihren Vergleich mit dem Naphtalin, Ann. Chem. 454 (1927) 121–324].     

Testing primitivity on partial words

Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in numerous research areas including formal language theory, coding theory, and combinatorics on words. Testing whether or not a word is primitive can be done in linear time in the length of the word. Indeed, a word is primitive if and only if it is not an inside factor of its square. In this paper, we describe a linear time algorithm to test primitivity on partial words which are strings that may contain a number of “do not know” symbols. Our algorithm is based on the combinatorial result that under some condition, a partial word is primitive if and only if it is not compatible with an inside factor of its square. The concept of special, related to commutativity on partial words, is foundational in the design of our algorithm. A World Wide Web server interface at http://www.uncg.edu/mat/primitive/ has been established for automated use of the program.     

A General Zero-Knowledge Scheme

There is a great similarity between the zero-knowledge proof of quadratic residuocity presented by Goldwasser-Micali-Rackoff and the graph isomorphism proof presented by Goldreich-Micali-Wigderson. There is also a resemblance between the zero-knowledge proofs of Fiat-Shamir, Chaum-Evertse-van de Graaf, Beth and Guillou-Quisquater. A similar observation holds for zero-knowledge proofs based on encryption: the 3-colourability proofs and the Hamiltonian-circuit proofs of Blum and Goldreich-Micali-Wigderson, and the Brassard-Chaum-Crepeau proof for SAT. Feige, Fiat and Shamir introduced the concept of zero-knowledge proofs of knowledge. In this paper we present a general zero-knowledge scheme which unifies all these Arthur-Merlin proofs.     

Multiprocessor scheduling under precedence constraints: Polyhedral results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented.     

Cone dominance and efficiency in DEA

This paper incorporates cones on virtual multipliers of inputs and outputs into DEA analysis. Cone DEA models are developed to generalize the dual of the BCC models as well as congestion models. Input-output data and/or numbers of DMUs for BCC models are inadequate to capture many aspects where judgments, expert opinions, and other external information should be taken into analysis. Cone DEA models, on the other hand, offer improved definitions of efficiency over general cone and polyhedral cone structures. The relationships between cone models and BCC models as well as those between cone models and congestion models are discussed in the development. Two numerical examples are provided to illustrate our findings.     

Smooth representation of a parametric polyhedral convex set with application to sensitivity in optimization

We show in this paper that if a polyhedral convex set is defined by a parametric linear system with smooth entries, then it possesses local smooth representation almost everywhere. This result is then applied to study the differentiability of the solutions and the marginal functions of several classes of parametric optimization problems.

     

接枝改性POSS对PLLA结晶行为的影响*

以二氯甲烷为溶剂,利用溶液共混法将三种聚笼形多面体倍半硅氧烷(POSS)分别与聚左旋乳酸(PLLA)进行共混,制备了不同POSS含量的单氨基POSS(POSS-NH₂)/PLLA、POSS接枝聚乙二醇(POSS-PEG)/PLLA和POSS接枝聚乳酸(POSS-g-PLLA)/PLLA复合材料。利用差示扫描量热仪(DSC)、热重分析仪(TGA)、偏光显微镜(POM) 分别对复合材料的本体结晶行为、热稳定性及结晶形貌和生长速率进行了观察。结果表明当加入不同质量分数(1 wt%, 5 wt%, 10 wt%)的POSS-PEG时,PLLA的结晶能力均得到改善,而POSS-NH2和POSS-g-PLLA仅在质量分数较低(1wt%)时对PLLA起成核剂的作用,具有较高质量分数时会阻碍PLLA分子链段的运动,从而限制其结晶。三种复合材料中仅POSS-PEG在一定程度上提高了PLLA的热稳定性,利用POM观察球晶生长过程发现POSS-PEG的加入提高了PLLA的球晶生长速率。     

Stability of the extreme point set of a polyhedron

This paper is focused on the stability properties of the extreme point set of a polyhedron. We consider a polyhedral setX(A,b) which is defined by a linear system of equality and inequality constraintsAxb, where the matrixA and the right-hand sideb are subject to perturbations. The extreme point setE(X(A,b)) of the polyhedronX(A,b) defines a multivalued map :(A,b)E(X(A,b)). In the paper, characterization of continuity and Lipschitz continuity of the map is obtained. Boundedness of the setX(A,b) is not assumed It is shown that lower Lipschitz continuity is equivalent to the lower semicontinuity of the map and to the Robinson and Mangasarian-Fromovitz constraint qualifications. Upper Lipschitz continuity is proved to be equivalent to the upper semicontinuity of the map . It appears that the upper semicontinuity of the map implies the lower semicontinuity of this map. Some examples of using the conditions obtained are provided.The author wishes to thank Dr. N. M. Novikova, Dr. S. K. Zavriev, and anonymous referees for their helpful comments and advice. The research described in this publication was made possible in part by Grant NJCU100 from the International Science Foundation and Russian Government, and by the Euler Grant, Deutsche Mathematiker Vereinigung.     

Synthesis and Characterization of Ferrocenyl Substituted Styryl Octasilsesquioxane

4-(2-Ferrocenylethenyl)-phenyl-POSS Fc-CH=CH-C6H6-(C5H9)7Si8O12 (FEPS, Fc: ferrocene), containing metal and C=C double bond, was firstly synthesized as a mixture of E/Z isomers by the Wittig reaction. The chemical structure of FEPS was characterized by FTIR, 1H-, 13Cand 29Si-NMR.