Confidence sets for discrete stochastic optimization

Consider the problem of finding the points of maximum of an expectation functional over a finite setS. Based on statistical estimates at each point ofS, confidence sets for theargmax-set are constructed which guarantee a prespecified probability of correct selection. We review known selection methods and propose a new two-stage procedure that works well for largeS and few global maxima. The performance is compared in a simulation study.     

Computations of eigenpair subsets with the MRRR algorithm

The main advantage of inverse iteration over the QR algorithm and Divide & Conquer for the symmetric tridiagonal eigenproblem is that subsets of eigenpairs can be computed at reduced cost. The MRRR algorithm (MRRR=multiple relatively robust representations) is a clever variant of inverse iteration without the need for reorthogonalization. STEGR, the current version of MRRR in LAPACK 3.0, does not allow for subset computations. The next release of STEGR is designed to compute a (sub‐)set of k eigenpairs with ??(kn) operations. Because of the special way in which eigenvectors are computed, MRRR subset computations are more complicated than when using inverse iteration. Unlike the latter, MRRR sometimes cannot ignore the unwanted part of the spectrum. We describe the problems with what we call ‘false singletons’. These are eigenvalues that appear to be isolated with respect to the wanted eigenvalues but in fact belong to a tight cluster of unwanted eigenvalues. This paper analyses these complications and ways to deal with them. Published in 2006 by John Wiley & Sons, Ltd.     

A dual ascent approach for steiner tree problems on a directed graph

The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that connects a root node to every node in a designated node setV. We give a dual ascent procedure for obtaining lower bounds to the optimal solution value. The ascent information is also used in a heuristic procedure for obtaining feasible solutions to the STDG. Computational results indicate that the two procedures are very effective in solving a class of STDG's containing up to 60 nodes and 240 directed/120 undirected arcs. The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships, we show that our ascent procedure can be viewed as a generalization ofboth the Chu-Liu-Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm.     

一类奇异非线性双调和方程的正整解

该文建立了一类R~2上奇异非线性双调和方程正的径向对称整体解的存在性定理,并给出了解的有关性质,丰富和发展了文[1]」,[2]的理论和应用.     

The minimum spanning tree problem with fuzzy costs

In this paper the minimum spanning tree problem in a given connected graph is considered. It is assumed that the edge costs are not precisely known and they are specified as fuzzy intervals. Possibility theory is applied to characterize the optimality of edges of the graph and to choose a spanning tree under fuzzy costs.     

On the Decomposition of Order-Separable Posets of Countable Width into Chains

Order - A partially ordered set X has countable width if and only if every collection of pairwise incomparable elements of X is countable. It is order-separable if and only if there is a countable...     

Solving the 2-rooted mini-max spanning forest problem by branch-and-bound

The 2-rooted mini-max spanning forest problem is to find a spanning forest with two given root nodes on an undirected graph, such that the maximum tree cost in this forest is minimized. We introduce a branch-and-bound algorithm based on selecting nodes. On test instances up to 50 nodes the algorithm gives much better computational results than a known algorithm that is based on selecting edges. Furthermore the new algorithm can easily solve problem instances up to 80 nodes.     

On the Size of Boolean Combinations of Subgroups of Finite Abelian Groups

The sizes of Boolean combinations of subgroups G _i of a finite abelian group depends only on the Boolean expression, the 0-1-sublattice generated by the G _i , and the size of minimal subquotients from this sublattice. Moreover, they increase, monotonically, with those sizes.