An Improved Extra-Gradient Method for Minimizing a Sum of p-norms—A Variational Inequality Approach

This paper presents a variational inequality (VI) approach to the problem of minimizing a sum of p-norms. First the original problem is reformulated as an equivalent linear VI. Then an improved extra-gradient method is presented to solve the linear VI. Applications to the problem of p-norm Steiner Minimum Trees (SMT) shows that the proposed method is effective. Comparison with the general extra-gradient method is also provided to show the improvements of the new method.     

Efficient computation of 2-medians in a tree network with positive/negative weights

We consider a variant of the classical two median facility location problem on a tree in which vertices are allowed to have positive or negative weights. This problem was proposed by Burkard et al. in 2000 (R.E. Burkard, E. Çela, H. Dollani, 2-medians in trees with pos/neg-weights, Discrete Appl. Math. 105 (2000) 51-71). who looked at two objectives, finding the total minimum weighted distance (MWD) and the total weighted minimum distance (WMD). Their approach finds an optimal solution in O(n²) time and O(n³) time, respectively, with better performance for special trees such as paths and stars. We propose here an O(nlogn) algorithm for the MWD problem on trees of arbitrary shape. We also briefly discuss the WMD case and argue that it can be solved in time. However, a systematic exposition of the later case cannot be contained in this paper.     

Runge–Kutta Methods for Itô Stochastic Differential Equations with Scalar Noise

A general class of stochastic Runge–Kutta methods for Itô stochastic differential equation systems w.r.t. a one-dimensional Wiener process is introduced. The colored rooted tree analysis is applied to derive conditions for the coefficients of the stochastic Runge–Kutta method assuring convergence in the weak sense with a prescribed order. Some coefficients for new stochastic Runge–Kutta schemes of order two are calculated explicitly and a simulation study reveals their good performance.     

On the Intersection Problem for Steiner Triple Systems of Different Orders

A Steiner triple system of order v, or STS(v), is a pair (V, ) with V a set of v points and a set of 3-subsets of V called blocks or triples, such that every pair of distinct elements of V occurs in exactly one triple. The intersection problem for STS is to determine the possible numbers of blocks common to two Steiner triple systems STS(u), (U, ), and STS(v), (V, ), with U⊆V. The case where U=V was solved by Lindner and Rosa in 1975. Here, we let U⊂V and completely solve this question for v−u=2,4 and for v≥2u−3. supported by NSERC research grant #OGP0170220. supported by NSERC postdoctoral fellowship. supported by NSERC research grant #OGP007621.     

A Note on L（2, 1）-labelling of Trees

An L(2,1)-labelling of a graph G is a function from the vertex set V (G) to the set of all nonnegative integers such that |f(u) f(v)| ≥ 2 if d G (u,v)=1 and |f(u) f(v)| ≥ 1 if d G (u,v)=2.The L(2,1)-labelling problem is to find the smallest number,denoted by λ(G),such that there exists an L(2,1)-labelling function with no label greater than it.In this paper,we study this problem for trees.Our results improve the result of Wang [The L(2,1)-labelling of trees,Discrete Appl.Math.154 (2006) 598-603].     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].     

均匀递归树的去点问题(英文)

本文研究了均匀递归树的去点过程.对于任意给定的点i,利用矩母函数,给出了对应子树顶点数的准确分布,推广了A.Panholzer所做的工作.     

On a question of Thas on partial 3‐(qn + 1, q + 1, 1) designs

In this note, we answer a question of JA Thas about partial $3$‐ $\left(q^n+1,q+1,1\right)$ designs. We then extend this answer to a result about the embedding of certain partial $3$‐ $\left(q^2+1,q+1,1\right)$ designs into Möbius planes.