The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.     

Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.     

Randomization helps to perform independent tasks reliably

This paper is about algorithms that schedule tasks to be performed in a distributed failure‐prone environment, when processors communicate by message‐passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly‐bounded adversaries may fail up to a constant fraction of the processors. Weakly‐adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure‐prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point‐to‐point messages. A randomized algorithm is developed, that attains both ??(n log*n) expected work and ??(n log*n) expected communication, against weakly‐adaptive linearly‐bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly‐adaptive linearly‐bounded adversaries, which has to be Ω(n log n/log log n) in terms of work. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

纵横扩张的优化

得到了最小折数纵横扩张的判别准则．针对4-正则图的平面嵌入的纵横扩张的特殊性，给出了它的最小折数纵横扩张判别准则．     

Second Order Nonlinear Evolution Inclusions Ⅰ： Existence and Relaxation Results

This is the first part of a work on second order nonlinear, nonmonotone evolution inclusions defined in the framework of an evolution triple of spaces and with a multivalued nonlinearity depending on both x（t） and x（t）. In this first part we prove existence and relaxation theorems. We consider the case of an usc, convex valued nonlinearity and we show that for this problem the solution set is nonempty and compact in C^1 （T, H）. Also we examine the Isc, nonconvex case and again we prove the existence of solutions. In addition we establish the existence of extremal solutions and by strengthening our hypotheses, we show that the extremal solutions are dense in C^1 （T, H） to the solutions of the original convex problem （strong relaxation）. An example of a nonlinear hyperbolic optimal control problem is also discussed.     

Positive set‐operators of low complexity

The powerset operator, ??, is compared with other operators of similar type and logical complexity. Namely we examine positive operators whose defining formula has a canonical form containing at most a string of universal quantifiers. We call them ?‐operators. The question we address in this paper is: How is the class of ?‐operators generated ? It is shown that every positive ?‐operator Γ such that Γ(??) ≠ ??, is finitely generated from ??, the identity operator Id, constant operators and certain trivial ones by composition, ∪ and ∩. This extends results of [3] concerning bounded positive operators.     

Conditional expectation of integrands and random sets

The conditional expectation of integrands and random sets is the main tool of stochastic optimization. This work wishes to make up for the lack of real synthesis about this subject. We improve the existing hypothesis and simplify the corresponding proofs. In the convex case we especially study the problem of the exchange of conditional expectation and subdifferential operators.     

Characteristics and structures of weak efficient surfaces of production possibility sets

This paper studies the characteristics and structure of the weak surface of the production possibility set. We apply techniques and methods of transferring a polyhedral cone from its intersection form to its sum form, identify an intersection representation of the production possibility set. We give the structure theorem of weak surface of the production possibility set, which includes three complementary slackness conditions. We define the input weak efficiency and output weak efficiency for different DEA models according to the representation of the intersection form. It investigates the characteristics of the weak surfaces, and proves the structure theorems of input weak DEA efficiency and output weak DEA efficiency. The structure theorems establish weighted combination of inputs and outputs that are weak DEA efficient. Numerical examples are provided for illustration.     

一类递归集的Hausdorff维数及Bouligand维数

本文给出递归集的Ｈａｕｓｄｏｒｆｆ维数的下界估计，并由此确定了一类递归集的维数，所获结果包含并推广了Ｂｅｄｆｏｒｄ，Ｄｅｋｋｉｎｇ及文志英、钟红柳等人的有关结果。