A branch-and-bound method for the minimum k−enclosing ball problem

The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this problem. Our method is able to solve the problem exactly in a short amount of time for small and medium sized datasets.     

Weak convergence of the U-statistic and weak invariance of the one-sample rank order statistic for Markov processes and ARMA models

Harel and Puri (1989, J. Multivariate Anal. 29) studied the asymptotic behavior of the U-statistic and the one-sample rank order statistic for nonstationary absolutely regular processes. In this note, we present some applications of these results for Markov processes as well as ARMA processes.     

INTERSECTION OF PRIME SUBMODULES AND DIMENSION OF MODULES

The aim of this paper is to study the conditions by which a P-prime submodule can be expressed as a finite intersection or union of P-prime submodules. Also corresponding to dimension and rank of modules, some equivalent conditions for a ring to be a Dedekind domain are given.     

Local approximations for maximum partial subgraph problem

We deal with MAXH₀-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ₀+1)/(B+2+ν₀), where B=max_v∈Vd_G(v), δ₀=min_v∈V(H0)d_H0(v) and ν₀=(|V(H₀)|+1)/δ₀. Next, we show that this ratio rises up to 3/(B+1) when H₀=K₃. Finally, we provide hardness results for MAXK₃-FREE PARTIAL SUBGRAPH.     

Weak Multiplication Modules

In this paper we characterize weak multiplication modules.     

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.     

On rank-perfect subclasses of near-bipartite graphs

Shepherd95 proved that the stable set polytopes of near-bipartite graphs are given by constraints associated with the complete join of antiwebs only. For antiwebs, the facet set reduces to rank constraints associated with single antiwebs by Wagler2004. We extend this result to a larger graph class, the complements of fuzzy circular interval graphs, recently introduced in ChudnovskySeymour2004. Received: November 2004 / Revised version: June 2005     

层次分析中广义最小偏差法的性质

广义最小偏差法（GLDM）是层次分析中一种重要的排序方法．本文讨论了广义最小偏差法的性质和灵敏度分析问题．     

Rank, term rank, and chromatic number

Let G be a graph with a nonempty edge set, and with rank rk(G), term rank Rk(G), and chromatic number χ(G). We characterize Rk(G) as being the maximum number of colors in certain proper colorings of G. In particular, we observe that χ(G)Rk(G), with equality holding if and only if (besides isolated vertices) G is either complete or a star. For a twin-free graph G, we observe the bound and we show that this bound is sharp.     

矩阵特征值的几个不等式

研究矩阵特征值的上、下界以及特征值的实部、虚部的不等式 ,给出了特征值一些新的上界和下界