Modular Decomposition of the Orlik-Terao Algebra

Let ${\mathcal{A}}$ be a collection of n linear hyperplanes in ${\mathbb{k}^\ell}$ , where ${\mathbb{k}}$ is an algebraically closed field. The Orlik-Terao algebra of ${\mathcal{A}}$ is the subalgebra ${{\rm R}(\mathcal{A})}$ of the rational functions generated by reciprocals of linear forms vanishing on hyperplanes of ${\mathcal{A}}$ . It determines an irreducible subvariety ${Y (\mathcal{A})}$ of ${\mathbb{P}^{n-1}}$ . We show that a flat X of ${\mathcal{A}}$ is modular if and only if ${{\rm R}(\mathcal{A})}$ is a split extension of the Orlik-Terao algebra of the subarrangement ${\mathcal{A}_X}$ . This provides another refinement of Stanley’s modular factorization theorem [34] and a new characterization of modularity, similar in spirit to the fibration theorem of [27]. We deduce that if ${\mathcal{A}}$ is supersolvable, then its Orlik-Terao algebra is Koszul. In certain cases, the algebra is also a complete intersection, and we characterize when this happens.     

Efficient and Practical Algorithms for Sequential Modular Decomposition

A module of an undirected graph G = (V, E) is a set X of vertices that have the same set of neighbors in V\X. The modular decomposition is a unique decomposition of the vertices into nested modules. We give a practical algorithm with an O(n + mα(m, n)) time bound and a variant with a linear time bound.     

An Algorithm to Construct Gilbert's Decomposition and Its Implementation for the Circuit Design Problem

An algorithm is proposed for the construction of monotone Boolean functions M ₀, M ₁,..., M _k in the decomposition of the Boolean function _f or some extension of f. The decomposition is applied to implement a circuit design algorithm that evaluates f in real LSI microelectronics devices. __________ Translated from Prikladnaya Matematika i Informatika, No. 18, pp. 108–121, 2004.     

Decomposition of Modular Codes for Computing Test Sets and Graver Basis

In order to obtain the set of codewords of minimal support for codes defined over ${\mathbb{Z}_q}$ , one can compute a Graver basis of the ideal associated to such codes. The main aim of this article is to reduce the complexity of the algorithm obtained by the authors in a previous work taking advantage of the powerful decomposition theory for linear codes provided by the decomposition theory of representable matroids over finite fields. In this way we identify the codes that can be written as ??gluing?? of codes of shorter length. If this decomposition verifies certain properties then computing the set of codewords of minimal support in each code appearing in the decomposition is equivalent to computing the set of codewords of minimal support for the original code. Moreover, these computations are independent of each other, thus they can be carried out in parallel for each component, thereby not only obtaining a reduction of the complexity of the algorithm but also decreasing the time needed to process it.     

Extremal Problems for Geometric Hypergraphs

A geometric hypergraph H is a collection of i -dimensional simplices, called hyperedges or, simply, edges, induced by some (i+1) -tuples of a vertex set V in general position in d -space. The topological structure of geometric graphs, i.e., the case d=2 , i=1 , has been studied extensively, and it proved to be instrumental for the solution of a wide range of problems in combinatorial and computational geometry. They include the k -set problem, proximity questions, bounding the number of incidences between points and lines, designing various efficient graph drawing algorithms, etc. In this paper, we make an attempt to generalize some of these tools to higher dimensions. We will mainly consider extremal problems of the following type. What is the largest number of edges (i -simplices) that a geometric hypergraph of n vertices can have without containing certain forbidden configurations? In particular, we discuss the special cases when the forbidden configurations are k intersecting edges, k pairwise intersecting edges, k crossing edges, k pairwise crossing edges, k edges that can be stabbed by an i -flat, etc. Some of our estimates are tight. Received March 4, 1996, and in revised form September 13, 1996.     

超图中的着色问题

本文是近三十年来有关超图中涉及的着色问题的综述。它包含了有关超图着色中的基本结果,临界可着色性,２－可着色性,非２－可着色性以及在超图中与顶点着色、边着色和其它着色相关的极值问题。     

Density Conditions for Panchromatic Colourings of Hypergraphs

Let be a hypergraph. A panchromatic t-colouring of is a t-colouring of its vertices such that each edge has at least one vertex of each colour; and is panchromatically t-choosable if, whenever each vertex is given a list of t colours, the vertices can be coloured from their lists in such a way that each edge receives at least t different colours. The Hall ratio of is . Among other results, it is proved here that if every edge has at least t vertices and whenever , then is panchromatically t-choosable, and this condition is sharp; the minimum such that every t-uniform hypergraph with is panchromatically t-choosable satisfies ; and except possibly when t = 3 or 5, a t-uniform hypergraph is panchromatically t-colourable if whenever , and this condition is sharp. This last result dualizes to a sharp sufficient condition for the chromatic index of a hypergraph to equal its maximum degree. Received November 10, 1998 RID="*" ID="*" This work was carried out while the first author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR/L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research.     

On Extremal Hypergraphs for Hamiltonian Cycles

We study sufficient conditions for Hamiltonian cycles in hypergraphs and obtain both Turán- and Dirac-type results. While the Turán-type result gives an exact threshold for the appearance of a Hamiltonian cycle in a hypergraph depending only on the extremal number of a certain path, the Dirac-type result yields just a sufficient condition relying solely on the minimum vertex degree.     

Non-Jumping Numbers for 4-Uniform Hypergraphs

Let r≥2 be an integer. A real number α ∈ [0,1) is a jump for r if for any Open image in new window >0 and any integer m, m≥r, any r-uniform graph with n>n₀( Open image in new window ,m) vertices and at least Open image in new window edges contains a subgraph with m vertices and at least Open image in new window edges, where c=c(α) does not depend on Open image in new window and m. It follows from a theorem of Erd?s, Stone and Simonovits that every α ∈ [0,1) is a jump for r=2. Erd?s asked whether the same is true for r≥3. Frankl and Rödl gave a negative answer by showing that Open image in new window is not a jump for r if r≥3 and l>2r. Following a similar approach, we give several sequences of non-jumping numbers generalizing the above result for r=4.     

On the Chromaticity of Multi-Bridge Hypergraphs

A multi-bridge hypergraph is an h-uniform linear hypergraph consisting of some linear paths having common extremities. In this paper it is proved that the multisets of path lengths of two chromatically equivalent multi-bridge hypergraphs are equal provided the multiplicities of path lengths are bounded above by 2 ^h-1 − 2. Also, it is shown that h-uniform linear cycles of length m are not chromatically unique for every m, h ≥ 3.     

基于最优D.C.分解的单二次约束非凸二次规划精确算法

本文提出一种基于最优D.C.分解的单二次约束非凸二次规划精确算法.本文首先对非凸二次日标函数进行D.C.分解,然后对D.C.分解中凹的部分进行线性下逼近得到一个凸二次松弛问题.本文证明了最优D.C.分解可通过求解一个半定规划问题得到,而原问题的最优解可以通过计算最优凸二次松弛问题的满足某种互补条件的解得到.最后,本文报告了初步数值计算结果.     

一类大规模二次规划问题的可行下降分解算法

本文对一类大规模二次规划问题，提出了矩阵剖分的概念和方法，并将问题转化为求解一系列容易求解的小规模二次规划子问题．另外，通过施加某些约束机制，使子问题所产生的迭代点均为可行下降点．在通常的假定下，证明算法具有全局收敛性，大量数值实验表明，本文所提出的新算法是有效的。     

A Primal-Dual Decomposition Algorithm for Multistage Stochastic Convex Programming

This paper presents a new and high performance solution method for multistage stochastic convex programming. Stochastic programming is a quantitative tool developed in the field of optimization to cope with the problem of decision-making under uncertainty. Among others, stochastic programming has found many applications in finance, such as asset-liability and bond-portfolio management. However, many stochastic programming applications still remain computationally intractable because of their overwhelming dimensionality. In this paper we propose a new decomposition algorithm for multistage stochastic programming with a convex objective and stochastic recourse matrices, based on the path-following interior point method combined with the homogeneous self-dual embedding technique. Our preliminary numerical experiments show that this approach is very promising in many ways for solving generic multistage stochastic programming, including its superiority in terms of numerical efficiency, as well as the flexibility in testing and analyzing the model.Research supported by Hong Kong RGC Earmarked Grant CUHK4233/01E.     

Parallel Algorithm for Unconstrained Optimization Based on Decomposition Techniques

We present a numerical implementation of the parallel gradient distribution (PGD) method for the solution of large-scale unconstrained optimization problems. The proposed parallel algorithm is characterized by a parallel phase which exploits the portions of the gradient of the objective function assigned to each processor; then, a coordination phase follows which, by a synchronous interaction scheme, optimizes over the partial results obtained by the parallel phase. The parallel and coordination phases are implemented using a quasi-Newton limited-memory BFGS approach. The computational experiments, carried out on a network of UNIX workstations by using the parallel software tool PVM, show that parallelization efficiency was problem dependent and ranged between 0.15 and 8.75. For the 150 problems solved by PGD on more than one processor, 85 cases had parallelization efficiency below 1, while 65 cases had a parallelization efficiency above 1.     

A New Successive Partition Algorithm for Concave Minimization Based on Cone Decomposition and Decomposition Cuts

In this paper we propose a new partition algorithm for concave minimization. The basic structure of the algorithm resembles that of conical algorithms. However, we make extensive use of the cone decomposition concept and derive decomposition cuts instead of concavity cuts to perform the bounding operation. Decomposition cuts were introduced in the context of pure cutting plane algorithms for concave minimization and has been shown to be superior to concavity cuts in numerical experiments. Thus by using decomposition cuts instead of concavity cuts to perform the bounding operation, unpromising parts of the feasible region can be excluded from further explorations at an earlier stage. The proposed successive partition algorithm finds an -global optimal solution in a finite number of iterations.     

Basic Feasible Solutions and the Dantzig-Wolfe Decomposition Algorithm

The relationship between solutions of the full master program of the Dantzig-Wolfe decomposition routine and the originally given problem is considered, and a criterion is established which states whether a basic feasible solution of the former corresponds to one of the latter.     

基于区域分解的CRS算法

本文针对带有盒子约束的非线性规划问题提出一种算法,该算法把解空间分成几个区域,根据每个区域上解的信息定义其选择概率,再根据轮盘赌选择法选择某个区域,在选择的区域上进行CRS（Control Random Search）算法操作。该方法能够缩小搜索空间,从而提高算法的搜索能力及算法的收敛速度,特别是在算法的后期效果更加明显。最后把提出的算法应用到两个典型的函数优化问题中,数值结果表明,算法是可行的、有效的。     

Supra-Hereditary Properties of Hypergraphs

A hypergraph-property P is supra-hereditary if whenever a hypergraph H has property P and K is a hypergraph generated by a nonempty subset A of X(H), then K also has the property P. In this paper we give a characterization of irreducible supra-hereditary hypergraphs thereby doubly extending a similar result in graph theory. Hence, we raise some fundamental questions in hypergraph theory.     

On Equitable Colorings of Hypergraphs

Mathematical Notes - A two-coloring is said to be equitable if, on the one hand, there are no monochromatic edges (the coloring is regular) and, on the other hand, the cardinalities of color...