A greedy algorithm for multicut and integral multiflow in rooted trees

We present an O(min(Kn,n²)) algorithm to solve the maximum integral multiflow and minimum multicut problems in rooted trees, where K is the number of commodities and n is the number of vertices. These problems are NP-hard in undirected trees but polynomial in directed trees. In the algorithm we propose, we first use a greedy procedure to build the multiflow then we use duality properties to obtain the multicut and prove the optimality.     

Stability Conditions of the MMAP [ K ]/ G [ K ]/1/ LCFS Preemptive Repeat Queue

In this paper, we study the stability conditions of the MMAP[K]/G[K]/1/LCFS preemptive repeat queue. We introduce an embedded Markov chain of matrix M/G/1 type with a tree structure and identify conditions for the Markov chain to be ergodic. First, we present three conventional methods for the stability problem of the queueing system of interest. These methods are either computationally demanding or do not provide accurate information for system stability. Then we introduce a novel approach that develops two linear programs whose solutions provide sufficient conditions for stability or instability of the queueing system. The new approach is numerically efficient. The advantages and disadvantages of the methods introduced in this paper are analyzed both theoretically and numerically.     

Hyperspaces of Normed Linear Spaces with the Attouch–Wets Topology

Let Cld _AW (X) be the hyperspace of nonempty closed subsets of a normed linear space X with the Attouch–Wets topology. It is shown that the space Cld _AW (X) and its various subspaces are AR's. Moreover, if X is an infinite-dimensional Banach space with weight w(X) then Cld _AW (X) is homeomorphic to a Hilbert space with weight 2 ^w(X).     

The linear polarization constant of R n

Summary He present work deals with estimations of the n-th linear polarization constant c(H)_n of an n-dimensional real Hilbert space H. We provide some new lower bounds on the value of sup_║y║=1 │1,y> ... n,y>│, where x₁, ... ,x_n are unit vectors in H. In particular, the results improve an earlier estimate of Marcus. However, the intriguing conjecture c(H) _n= n^n/2 remains open.     

Compact Matrix Expressions for Generalized Wald Tests of Equality of Moment Vectors

Asymptotic chi-squared test statistics for testing the equality of moment vectors are developed. The test statistics proposed are generalized Wald test statistics that specialize for different settings by inserting an appropriate asymptotic variance matrix of sample moments. Scaled test statistics are also considered for dealing with nonstandard conditions. The specialization will be carried out for testing the equality of multinomial populations, and the equality of variance and correlation matrices for both normal and nonnormal data. When testing the equality of correlation matrices, a scaled version of the normal theory chi-squared statistic is proven to be an asymptotically exact chi-squared statistic in the case of elliptical data.     

A Survey on Explicit Representation Formulae for Fundamental Solutions of Linear Partial Differential Operators

In the present article, we aim at treating the existence of fundamental solutions of linear partial differential operators with constant coefficients from the viewpoint of setting up explicit formulae yielding fundamental solutions.     

A Note on Geometric Structures of Linear Ordered Orthogonal Arrays and (T,M,S)-Nets of Low Strength

The equivalent geometrical configurations of linear ordered orthogonal arrays are determined when their strengths are 3 and 4. Existence of such geometrical configurations is investigated. They are also useful in the study of (T, M, S)-nets.     

Balance constraints reduction of large-scale linear programming problems

This paper describes a method and the corresponding algorithms for simplification of large-scale linear programming models. It consists of the elimination of the balance constraints (i.e. constraints with zero RHS term). The idea is to apply some linear transformations to the original problem in order to nullify the balance constraints. These transformations are able to simultaneously eliminate more balance rows. The core of this contribution is the introduction of the reduction matrix and the associated theorems on the equivalent linear programs (original and reduced). The numerical experiments with this method of simplification proved this approach to be beneficial for a large class of LP problems.This research work was done while the first author was at Duisburg University, Mess-, Steuer und Regelungstechnik, Germany, under the greatly appreciated financial assistance given by the Alexander-von-Humboldt Foundation.     

Extended convergence results for the method of multipliers for nonstrictly binding inequality constraints

In this paper, we extend the classical convergence and rate of convergence results for the method of multipliers for equality constrained problems to general inequality constrained problems, without assuming the strict complementarity hypothesis at the local optimal solution. Instead, we consider an alternative second-order sufficient condition for a strict local minimum, which coincides with the standard one in the case of strict complementary slackness. As a consequence, new stopping rules are derived in order to guarantee a local linear rate of convergence for the method, even if the current Lagrangian is only asymptotically minimized in this more general setting. These extended results allow us to broaden the scope of applicability of the method of multipliers, in order to cover all those problems admitting loosely binding constraints at some optimal solution. This fact is not meaningless, since in practice this kind of problem seems to be more the rule rather than the exception.In proving the different results, we follow the classical primaldual approach to the method of multipliers, considering the approximate minimizers for the original augmented Lagrangian as the exact solutions for some adequate approximate augmented Lagrangian. In particular, we prove a general uniform continuity property concerning both their primal and their dual optimal solution set maps, a property that could be useful beyond the scope of this paper. This approach leads to very simple proofs of the preliminary results and to a straight-forward proof of the main results.The author gratefully acknowledges the referees for their helpful comments and remarks. This research was supported by FONDECYT (Fondo Nacional de Desarrollo Científico y Technológico de Chile).     

谐振子薛定谔方程的简单解法

物质的许多物理与化学性质都可以用线性谐振子模型解释，本文用简单的数学运算求解线性谐振子的薛定谔方程，避免了特殊函数等复杂的数学运算，得出了量子力学教材完全相同的结果。