On the number of connected convex subgraphs of a connected acyclic digraph

A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.     

On an outer approximation concept in global optimization

A simple outer approximation concept for global optimization problems is presented that simplifies and generalizes several previous approaches. Unbounded feasible regions and non-affine cuts are admitted. Constraint dropping strategies and a large class of cutting plane methods are derived.     

On guarding the vertices of rectilinear domains

We prove that guarding the vertices of a rectilinear polygon P, whether by guards lying at vertices of P, or by guards lying on the boundary of P, or by guards lying anywhere in P, is NP-hard. For the first two proofs (i.e., vertex guards and boundary guards), we construct a reduction from minimum piercing of 2-intervals. The third proof is somewhat simpler; it is obtained by adapting a known reduction from minimum line cover.

We also consider the problem of guarding the vertices of a 1.5D rectilinear terrain. We establish an interesting connection between this problem and the problem of computing a minimum clique cover in chordal graphs. This connection yields a 2-approximation algorithm for the guarding problem.     

On the structure of strong 3-quasi-transitive digraphs

In this paper, D=(V(D),A(D)) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V(D). Given a digraph D, we say that D is 3-quasi-transitive if, whenever u→v→w→z in D, then u and z are adjacent or u=z. In Bang-Jensen (2004) [3], Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs.     

几个著名网络的限长路径

设给出了（h,ψ）-η限长路径问题是图论中的Menger定理的变形和推广，在实时容错网络设计和分析中有重要意义。对于给定的正整数d,Ad(D)表示网络D中任何距离至少为2的两顶点之间内点不交且长度都不超过d的路的最大条数；Bd(D)表示D的顶点子集B中的最小顶点数使得D－B的直径大于d.已证明确定Ad(D)的问题是NPC问题，而且显然有不等式Ad(D)≤Bd(D)。本文考虑D为超立方体网络、De Bruijn网络和Kautz网络，对d的不同值确定了Ad(D)及Bd(D),而且均有Ad(D)=Bd(D)。     

Some results associated with the longest run in a strongly ergodic Markov chain

This paper discusses the asymptotic behaviors of the longest run on a countable state Markov chain.Let {Xa} a∈Z + be a stationary strongly ergodic reversible Markov chain on countablestate space S = {1,2,...}.Let TS be an arbitrary finite subset of S.Denote by Ln the length of the longest run of consecutive i's for i∈T,that occurs in the sequence X1,...,Xn.In this paper,we obtain a limit law and a week version of an Erds-Rényi type law for Ln.A large deviation result of Ln is also discussed.     

Almost Surely Convergent Global Optimization Algorithm Using Noise-Corrupted Observations

A new recursive algorithm for searching the global minimizer of a function is proposed when the function is observed with noise. The algorithm is based on switches between the stochastic approximation and the random search. The combination of SA with RS is not a new idea in such combination, the difficulty consists in creating a good switching rule and in designing an efficient method to reduce the noise effect. The proposed switching rule is easily realizable, the noise reducing method is effective, and the whole recursive optimization algorithm is simply calculated. It is proved that the algorithm a.s. converges to the global minimizer and is asymptotically normal. In comparison with existing methods, the proposed algorithm not only requires much weaker conditions, but also is more efficient as shown by simulation.     

A global optimization approach for solving the convex multiplicative programming problem

We consider a convex multiplicative programming problem of the form% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9qq-f0-yqaqVeLsFr0-vr% 0-vr0db8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaGG7bGaam% OzamaaBaaaleaacaaIXaaabeaakiaacIcacaWG4bGaaiykaiabgwSi% xlaadAgadaWgaaWcbaGaaGOmaaqabaGccaGGOaGaamiEaiaacMcaca% GG6aGaamiEaiabgIGiolaadIfacaGG9baaaa!4A08!\[\{ f_1 (x) \cdot f_2 (x):x \in X\} \]where X is a compact convex set of ⁿ and f ₁, f ₂ are convex functions which have nonnegative values over X.Using two additional variables we transform this problem into a problem with a special structure in which the objective function depends only on two of the (n+2) variables. Following a decomposition concept in global optimization we then reduce this problem to a master problem of minimizing a quasi-concave function over a convex set in ² ₂. This master problem can be solved by an outer approximation method which requires performing a sequence of simplex tableau pivoting operations. The proposed algorithm is finite when the functions f _i, (i=1, 2) are affine-linear and X is a polytope and it is convergent for the general convex case.Partly supported by the Deutsche Forschungsgemeinschaft Project CONMIN.     

On the structure of the adjacency matrix of the line digraph of a regular digraph

We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as M=AB, where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D.     

Approximation of the capillarity problem by an augmented lagrangian method

We propose an algorithm to compute an approximation of capillary surfaces in a gravitational field. This algorithm is based on a decomposition-coordination method by augmented lagrangians and the discretization is done using the finite element method. We study the convergence of the algorithm and the error of discretization for the axisymmetric case; some numerical results are given. This method can be generalized to a two-dimensional space.Projet IDOPT (CNRS-UJF-INPG-INRIA).     

关于大学课程表问题的研究

大学课程表问题可以表述为：如何为给定的一组课程编排一个时间表，以使得所有的学生选课要求都得到满足，并且这些课程所用的不同课时段数目最少。在本中我们首先证明了即使每位学生最多选两门课程，该问题仍然是NP-难解的，然后我们提出了求解该问题一般情形的一个启发式算法。     

Errata Corrige: On an Optimality Condition in DC Optimization

We take care of an omission in Proposition 4.4 of Ref. 1.     

On an Identity of Mahler

We prove that certain multiple integrals depending on the complex parameter z can be expressed as polynomials in z and ln(1 ? z). Similar identities were first used by K. Mahler in connection with the proofs of certain results of the theory of transcendental numbers.     

On the partial order polytope of a digraph

We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete.     

On the length of longest chordless cycles

Upper bounds for the length of a longest (circuit) cycle without chords in a (directed) graph are given in terms of the rank of the adjacency matrix and in terms of its eigenvalues.Received: October 2003, Revised: January 2005, AMS classification: 05C     

On the longest length of consecutive integers

Choose m numbers from the set {1, 2, …, n} at random without replacement. In this paper we first establish the limiting distribution of the longest length of consecutive integers and then apply the result to test randomness of selecting numbers without replacement.     

求解简单界约束优化问题的一种逐次逼近法

１引言考虑变量带简单界约束的非线性规划问题：其中二阶连续可微,ａ＝（ａ１,ａ２,…,ａｎ）,ｂ＝（ｂ１,ｂ２,…,ｂｎ）,＋ｉ＝１,２,…,ｎ．问题（１）不仅是实际应用中出现的简单界约束最优化问题,而且相当一部分最优化问题可以把变量限制在有意义的区间内（参见［１］）．因此无论在理论方面还是在实际应用方面,都有研究此类问题并给出简便而有效算法的必要．假设ｆ是凸函数,记ｇ（ｘ）＝ｆ（ｘ）,则由Ｋ－Ｔ条件,问题（１）可化为求解下面的非光滑方程组：显然,（２）等价于易证,（３）等价于求解下面的非光滑方程…     

单调全局最优化问题的凸化外逼近算法

单调优化是指目标函数与约束函数均为单调函数的全局优化问题．本文提出一种新的凸化变换方法把单调函数化为凸函数，进而把单调优化问题化为等价的凸极大或凹极小问题，然后采用Hoffman的外逼近方法来求得问题的全局最优解．我们把这种凸化方法同Tuy的Polyblock外逼近方法作了比较，通过数值比较可以看出本文提出的凸化的方法在收敛速度上明显优于Polyblock方法．     

On the complexity of scheduling unrelated parallel machines with limited preemptions

We consider the problem of finding a minimum-length preemptive schedule for n jobs on m parallel machines. The problem is solvable in polynomial time, whether the machines are identical, uniform or unrelated. For identical or uniform machines, it is easy to obtain an optimal schedule in which the portion of a job that is assigned to a single machine is processed without interruption. We show that imposing this condition in the case of unrelated machines makes the problem NP-hard.