Weighted Hardy inequalities for decreasing sequences and functions

We obtain a complete characterization of the weights for which Hardy's inequality holds on the cone of non-increasing sequences. Our proofs translate immediately to the analogous inequality for non-increasing functions, thereby also completing the investigation in that direction. As an application of our results we characterize the boundedness of the Hardy-Littlewood maximal operator on Lorentz sequence spaces.     

基于邻域信息的社区发现方法

考虑含有节点邻域信息的新模块度函数的社区发现方法和最优分组下标度参数的选择问题,通过谱松弛方法求解模块度函数的最大化问题,最终利用新算法快速求解,并通过真实网络数据验证算法能更好的发现社区.     

Swap-vertex based neighborhood for Steiner tree problems

Steiner tree problems (STPs) are very important in both theory and practice. In this paper, we introduce a powerful swap-vertex move operator which can be used as a basic element of any neighborhood search heuristic to solve many STP variants. Given the incumbent solution tree T, the swap-vertex move operator exchanges a vertex in T with another vertex out of T, and then attempts to construct a minimum spanning tree, leading to a neighboring solution (if feasible). We develop a series of dynamic data structures, which allow us to efficiently evaluate the feasibility of swap-vertex moves. Additionally, in order to discriminate different swap-vertex moves corresponding to the same objective value, we also develop an auxiliary evaluation function. We present a computational assessment based on a number of challenging problem instances (corresponding to three representative STP variants) which clearly shows the effectiveness of the techniques introduced in this paper. Particularly, as a key element of our KTS algorithm which participated in the 11th DIMACS implementation challenge, the swap-vertex operator as well as the auxiliary evaluation function contributed significantly to the excellent performance of our algorithm.     

Minimum and maximum distances between failures in binary sequences

The minimum and maximum distances denoting the extreme numbers of successes between two successive failures in binary sequences, are considered. Exact marginal and joint probability distributions of these statistics are obtained via combinatorial analysis. Applications related to urn models and system reliability are studied and clarify further the theoretical results.     

A variable neighborhood search based matheuristic for nurse rostering problems

A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various requirements. A matheuristic approach is introduced, based on a set of neighborhoods iteratively searched by a commercial integer programming solver within a defined global time limit, relying on a starting solution generated by the solver running on the general integer programming formulation of the problem. Generally speaking, a matheuristic algorithm is a heuristic algorithm that uses non trivial optimization and mathematical programming tools to explore the solutions space with the aim of analyzing large scale neighborhoods. Randomly generated instances, based on the considered nurse rostering problem, were solved and solutions computed by the proposed procedure are compared to the solutions achieved by pure solvers within the same time limit. The results show that the proposed solution approach outperforms the solvers in terms of solution quality. The proposed approach has also been tested on the well known Nurse Rostering Competition instances where several new best results were reached.     

A practical general approximation criterion for methods of multipliers based on Bregman distances

 This paper demonstrates that for generalized methods of multipliers for convex programming based on Bregman distance kernels – including the classical quadratic method of multipliers – the minimization of the augmented Lagrangian can be truncated using a simple, generally implementable stopping criterion based only on the norms of the primal iterate and the gradient (or a subgradient) of the augmented Lagrangian at that iterate. Previous results in this and related areas have required conditions that are much harder to verify, such as ε-optimality with respect to the augmented Lagrangian, or strong conditions on the convex program to be solved. Here, only existence of a KKT pair is required, and the convergence properties of the exact form of the method are preserved. The key new element in the analysis is the use of a full conjugate duality framework, as opposed to mainly examining the action of the method on the standard dual function of the convex program. An existence result for the iterates, stronger than those possible for the exact form of the algorithm, is also included. Received: February 6, 2001 / Accepted: January 25, 2003 Published online: March 21, 2003 Mathematics Subject Classification (1991): 90C25, 90C46, 47H05     

Weighted portfolio selection models based on possibility theory

In this paper, we discuss portfolio selection problem in a fuzzy uncertain environment. Based on the Fullér’s and Zhang’s notations, we discuss some properties of weighted lower and upper possibilistic means and variances as in probability theory. We further present two weighted possibilistic portfolio selection models with bounded constraint, which can be transformed to linear programming problems under the assumption that the returns of assets are trapezoidal fuzzy numbers. At last, a numerical example is given to illustrate our proposed effective means and approaches.     

Nonmonotone projected gradient methods based on barrier and Euclidean distances

We consider nonmonotone projected gradient methods based on non-Euclidean distances, which play the role of barrier for a given constraint set. Our basic scheme uses the resulting projection-like maps that produces interior trajectories, and combines it with the recent nonmonotone line search technique originally proposed for unconstrained problems by Zhang and Hager. The combination of these two ideas leads to produce a nonmonotone scheme for constrained nonconvex problems, which is proven to converge to a stationary point. Some variants of this algorithm that incorporate spectral steplength are also studied and compared with classical nonmonotone schemes based on the usual Euclidean projection. To validate our approach, we report on numerical results solving bound constrained problems from the CUTEr library collection.     

Realization of digraphs by preferences based on distances in graphs

Consider a graph G with two distinguished sets of vertices: the voters and the candidates. A voter v prefers candidate x to candidate y if d(v, x) < d(v, y). This preference relation defines an asymmetric digraph whose vertices are the candidates, in which there is an arc from candidate x to candidate y if and only if more voters prefer x to y than prefer y to x. T. W. Johnson and P. J. Slater (“Realization of Majority Preference Digraphs by Graphically Determined Voting Patterns,” Congressus Numerantium, vol. 67 [1988] 175-186) have shown that each asymmetric digraph of order n can be realized in this way using a graph of order O(n²). We present a new construction reducing the quadratic upper bound to a linear bound. © 1995 John Wiley & Sons, Inc.     

A wide neighborhood interior-point algorithm for linear optimization based on a specific kernel function

This paper presents an interior point algorithm for solving linear optimization problems in a wide neighborhood of the central path introduced by Ai and Zhang (SIAM J Optim 16:400–417, 2005). In each iteration, the algorithm computes the new search directions by using a specific kernel function. The convergence of the algorithm is shown and it is proved that the algorithm has the same iteration bound as the best short-step algorithms. We demonstrate the computational efficiency of the proposed algorithm by testing some Netlib problems in standard form. To best our knowledge, this is the first wide neighborhood path-following interior-point method with the same complexity as the best small neighborhood path-following interior-point methods that uses the kernel function.

     

A variable neighborhood search based algorithm for finite-horizon Markov Decision Processes

This paper considers the application of a variable neighborhood search (VNS) algorithm for finite-horizon (H stages) Markov Decision Processes (MDPs), for the purpose of alleviating the “curse of dimensionality” phenomenon in searching for the global optimum. The main idea behind the VNSMDP algorithm is that, based on the result of the stage just considered, the search for the optimal solution (action) of state x in stage t is conducted systematically in variable neighborhood sets of the current action. Thus, the VNSMDP algorithm is capable of searching for the optimum within some subsets of the action space, rather than over the whole action set. Analysis on complexity and convergence attributes of the VNSMDP algorithm are conducted in the paper. It is shown by theoretical and computational analysis that, the VNSMDP algorithm succeeds in searching for the global optimum in an efficient way.     

On the mean and extreme distances between failures in Markovian binary sequences

This paper is concerned with the mean, minimum and maximum distances between two successive failures in a binary sequence consisting of Markov dependent elements. These random variables are potentially useful for the analysis of the frequency of critical events occurring in certain stochastic processes. Exact distributions of these random variables are derived via combinatorial techniques and illustrative numerical results are presented.     

On the mean and extreme distances between failures in Markovian binary sequences

This paper is concerned with the mean, minimum and maximum distances between two successive failures in a binary sequence consisting of Markov dependent elements. These random variables are potentially useful for the analysis of the frequency of critical events occurring in certain stochastic processes. Exact distributions of these random variables are derived via combinatorial techniques and illustrative numerical results are presented.     

A hierarchical location-allocation model with travel based on expected referral distances

The hierarchical p-median location-allocation model assumes that patrons always travel to the closest facility of appropriate level and that their interests are best served when the distances they must travel to do this are minimized. This assumption about travel behavior is unrealistic, patrons in the real world are known, for instance, to bypass lower level facilities that can serve their needs to attend higher level facilities. We introduce the concept of “expected distance under referral” to deal with such irrationality and incorporate it into a location-allocation model that minimizes the negative effects of such irrational behavior. We demonstrate the model with several types of non-optimal travel behavior.     

Randomized Smolyak algorithms based on digital sequences for multivariate integration

Gunther Leobacher ^{In this paper, we consider Smolyak algorithms based on quasi-MonteCarlo rules for high-dimensional numerical integration. Thequasi-Monte Carlo rules employed here use digital (t, , ß,, d)-sequences as quadrature points. We consider the worst-caseerror for multivariate integration in certain Sobolev spacesand show that our quadrature rules achieve the optimal rateof convergence. By randomizing the underlying digital sequences,we can also obtain a randomized Smolyak algorithm. The boundon the worst-case error holds also for the randomized algorithmin a statistical sense. Further, we also show that the randomizedalgorithm is unbiased and that the integration error can beapproximated as well.}     

Weighted graph based ordering techniques for preconditioned conjugate gradient methods

We describe the basis of a matrix ordering heuristic for improving the incomplete factorization used in preconditioned conjugate gradient techniques applied to anisotropic PDE's. Several new matrix ordering techniques, derived from well-known algorithms in combinatorial graph theory, which attempt to implement this heuristic, are described. These ordering techniques are tested against a number of matrices arising from linear anisotropic PDE's, and compared with other matrix ordering techniques. A variation of RCM is shown to generally improve the quality of incomplete factorization preconditioners.This work was supported by by the Natural Sciences and Engineering Research Council of Canada, and by the Information Technology Research Center, which is funded by the Province of Ontario.     

Weighted approximation of continuous functions by sequences of linear positive operators

In this work we obtain, under suitable conditions, theorems of Korovkin type for spaces with different weight, composed of continuous functions defined on unbounded regions. These results can be seen as an extension of theorems by Gadjiev in [4] and [5].     

Perturbation of fuzzy sets and fuzzy reasoning based on normalized Minkowski distances

In this paper, we extend the concept of the perturbation of fuzzy sets based on normalized Minkowski distances and present some new conclusions on perturbation raised by various operations of fuzzy sets. These operations are induced by triangular norms and conorms. Furthermore, we discuss the perturbation of fuzzy reasoning.     

Harmonic interpolation of Hermite type based on Radon projections with constant distances

We study harmonic interpolation of Hermite type of harmonic functions based on Radon projections with constant distances of chords. We show that the interpolation polynomials are continuous with respect to the angles and the distances. When the chords coalesce to some points on the unit circle, we prove that the interpolation polynomials tend to a Hermite interpolation polynomial at the coalescing points.     

A new closure concept preserving graph Hamiltonicity and based on neighborhood equivalence

A graph is Hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is Hamiltonian is known as an NP-complete problem, and no satisfactory characterization for these graphs has been found.In 1976, Bondy and Chvàtal introduced a way to get round the Hamiltonicity problem complexity by using a closure of the graph. This closure is a supergraph of G which is Hamiltonian iff G is. In particular, if the closure is the complete graph, then G is Hamiltonian. Since this seminal work, several closure concepts preserving Hamiltonicity have been introduced. In particular, in 1997, Ryjá?ek defined a closure concept for claw-free graphs based on local completion.Following a different approach, in 1974, Goodman and Hedetniemi gave a sufficient condition for Hamiltonicity based on the existence of a clique covering of the graph. This condition was recently generalized using the notion of Eulerian clique covering. In this context, closure concepts based on local completion are interesting since the closure of a graph contains more simplicial vertices than the graph itself, making the search for a clique covering easier.In this article, we introduce a new closure concept based on local completion which preserves the Hamiltonicity for every graph. Note that, moreover, the closure may be claw free even when the graph is not.