Searching for extensible Korobov rules

Extensible lattice sequences have been proposed and studied in [F.J. Hickernell, H.S. Hong, Computing multivariate normal probabilities using rank-1 lattice sequences, in: G.H. Golub, S.H. Lui, F.T. Luk, R.J. Plemmons (Eds.), Proceedings of the Workshop on Scientific Computing (Hong Kong), Singapore, Springer, Berlin, 1997, pp. 209–215; F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138; F.J. Hickernell, H.Niederreiter, The existence of good extensible rank-1 lattices, J. Complexity 19 (2003) 286–300]. For the special case of extensible Korobov sequences, parameters can be found in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C.Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138]. The searches made to obtain these parameters were based on quality measures that look at several projections of the lattice. Because it is often the case in practice that low-dimensional projections are very important, it is of interest to find parameters for these sequences based on measures that look more closely at these projections. In this paper, we prove the existence of “good” extensible Korobov rules with respect to a quality measure that considers two-dimensional projections. We also report results of experiments made on different problems where the newly obtained parameters compare favorably with those given in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138].     

无K1,r图中的哈密顿圈（英文）

本文借助对图的本质独立集和图的部分平方图的独立集的研究，对于K1,r图中哈密顿圈的存在性给出了八个充分条件。我们将利用T－插点技术对这八个充分条件给出统一的证明，本文的结果从本质上改进了C－Q.Zhang于1988年利用次形条件给出的k-连通无爪图是哈密顿图的次型充分条件，同时。G.Chen和R.H.Schelp在1995年利用次型条件给出的关于k-连通无K1，4图是哈密顿图的充分条件也被我们的结果改进并推广到无K1,r图。     

Euler characteristic and related measures for random geometric sets

By an elementary calculation we obtain the exact mean values of Minkowksi functionals for a standard model of percolating sets. In particular, a recurrence theorem for the mean Euler characteristic recently put forward is shown to be incorrect. Related previous mathematical work is mentioned. We also conjecture bounds for the threshold density of continuum percolation, which are associated with the Euler characteristic.     

Constructions of External Difference Families and Disjoint Difference Families

External difference families (EDFs) are a type of new combinatorial designs originated from cryptography. In this paper, some earlier ideas of recursive and cyclotomic constructions of combinatorial designs are extended, and a number of classes of EDFs and disjoint difference families are presented. A link between a subclass of EDFs and a special type of (almost) difference sets is set up.     

Semiconvergence in distribution of random closed sets with application to random optimization problems

The paper considers upper semicontinuous behavior in distribution of sequences of random closed sets. Semiconvergence in distribution will be described via convergence in distribution of random variables with values in a suitable topological space. Convergence statements for suitable functions of random sets are proved and the results are employed to derive stability statements for random optimization problems where the objective function and the constraint set are approximated simultaneously. The author is grateful to two anonymous referees for helpful suggestions.     

Exact Max-SAT solvers for over-constrained problems

We present a new generic problem solving approach for over-constrained problems based on Max-SAT. We first define a Boolean clausal form formalism, called soft CNF formulas, that deals with blocks of clauses instead of individual clauses, and that allows one to declare each block either as hard (i.e., must be satisfied by any solution) or soft (i.e., can be violated by some solution). We then present two Max-SAT solvers that find a truth assignment that satisfies all the hard blocks of clauses and the maximum number of soft blocks of clauses. Our solvers are branch and bound algorithms equipped with original lazy data structures, powerful inference techniques, good quality lower bounds, and original variable selection heuristics. Finally, we report an experimental investigation on a representative sample of instances (random 2-SAT, Max-CSP, graph coloring, pigeon hole and quasigroup completion) which provides experimental evidence that our approach is very competitive compared with the state-of-the-art approaches developed in the CSP and SAT communities. Research partially supported by projects TIN2004-07933-C03-03 and TIC2003-00950 funded by the Ministerio de Educación y Ciencia. The second author is supported by a grant Ramón y Cajal.     

Some results on quasipolyhedral convexity

The objective of this paper is to analyze under what well-known operations the class of quasipolyhedral convex functions, which can be regarded as an extension of that of polyhedral convex functions, is closed. The operations that will be considered are those that preserve polyhedral convexity, such that the image and the inverse image under linear transformations, right scalar multiplication (including the case where λ=0⁺) and pointwise addition.      

The Exact Hausdorff Measure Function of the Level Sets of Multi-parameter Symmetric Stable Process

In this paper, we investigate the Hausdorff measure for level sets of N-parameter Rd-valued stable processes, and develop a means of seeking the exact Hausdorff measure function for level sets of N-parameter Rd-valued stable processes. We show that the exact Hausdorff measure function of level sets of N-parameter Rd-valued symmetric stable processes of index α is Ф（r） = r^N-d/α （log log l/r）d/α when Nα 〉 d. In addition, we obtain a sharp lower bound for the Hausdorff measure of level sets of general （N, d, α） strictly stable processes.     

Proximality and Chebyshev sets

This paper is a companion to a lecture given at the Prague Spring School in Analysis in April 2006. It highlights four distinct variational methods of proving that a finite dimensional Chebyshev set is convex and hopes to inspire renewed work on the open question of whether every Chebyshev set in Hilbert space is convex.     

Barycentric coordinates for convex sets

In this paper we provide an extension of barycentric coordinates from simplices to arbitrary convex sets. Barycentric coordinates over convex 2D polygons have found numerous applications in various fields as they allow smooth interpolation of data located on vertices. However, no explicit formulation valid for arbitrary convex polytopes has been proposed to extend this interpolation in higher dimensions. Moreover, there has been no attempt to extend these functions into the continuous domain, where barycentric coordinates are related to Green’s functions and construct functions that satisfy a boundary value problem. First, we review the properties and construction of barycentric coordinates in the discrete domain for convex polytopes. Next, we show how these concepts extend into the continuous domain to yield barycentric coordinates for continuous functions. We then provide a proof that our functions satisfy all the desirable properties of barycentric coordinates in arbitrary dimensions. Finally, we provide an example of constructing such barycentric functions over regions bounded by parametric curves and show how they can be used to perform freeform deformations.