On Producing Multiple Solutions Using Repeated Trials

The number of trials that is required by an algorithm to produce a given fraction of the problem solutions with a specified level of confidence is analyzed. The analysis indicates that the number of trials required to find a large fraction of the solutions rapidly decreases as the number of solutions obtained on each trial by an algorithm increases. In applications where multiple solutions are sought, this decrease in the number of trials could potentially offset the additional computational cost of algorithms that produce multiple solutions on a single trial. The analysis framework presented is used to compare the efficiency of a homotopy algorithm to that of a Newton method by measuring both the number of trials and the number of calculations required to obtain a specified fraction of the solutions.     

Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

复流形局部q-凸楔形上带权的同伦公式

本文得到复流形局部q-凸楔形上(r,s)型微分形式的带权的同伦公式和(r,s)型的方程的带权的连续解,并给出(r,s)型微分形式的不含边界积分的新的带权的同伦公式和(r,s)型的方程的新的带权的连续解.这些新的带权公式尤其适用于具有非光滑边界的局部q-凸楔形,这时不但可以避免边界积分的复杂估计,而且积分密度也不必在边界有定义,只要在区域上有定义就行.其次,引进权因子,带权的积分公式在应用上(比如在函数的插值方面)具有更大的灵活性.     

Torsors and Stacks

It is shown that the groupoid of G-torsors, suitably defined, can be used to construct a model for the stack associated to G, for arbitrary sheaves of groupoids G. This research was supported by the Natural Sciences and Engineering Research Council of Canada.     

Rational Homotopy Theory and Nonnegative Curvature

in this note, we answer positively a question by Belegradek and Kapovitch about the relation between rational homotopy theory and a problem in Riemannian geometry which asks that total spaces of which vector bundles over compact non-negative curved manifolds admit （complete） metrics with non-negative curvature.     

The free loop space and the algebraic k-theory of spaces

Let A(X) be the space defined by Waldhausen whose homotopy groups define the algebraic K-groups of the space X and let . Here (X) denotes the free loop space of X and Q denotes the functor . For X = Y, the suspension of a connected space Y, we shall prove that the homotopy fibers Ã(X), B(X) of the maps A(X) A (point), B(X) B (point) are equivalent as infinite loop spaces.     

On the cost of approximating all roots of a complex polynomial

This work examines the computational complexity of a homotopy algorithm in approximating all roots of a complex polynomialf. It is shown that, probabilistically, monotonic convergence to each of the roots occurs after a determined number of steps. Moreover, in all subsequent steps, each rootz is approximated by a complex numberx, where ifx ₀ =x, x _j =x _j–1 –f(x _j–1)/f(x _j–1),j = 1, 2,, then |x _j –z| < (1/|x ₀ –z|)|x _j–1–z|².     

Resonant equations with the Neumann p-Laplacian plus an indefinite potential

We consider a nonlinear Neumann problem driven by the p  -Laplacian plus an indefinite potential and a Carathéodory reaction which at ±∞ is resonant with respect to any nonprincipal variational eigenvalue of the differential operator. Using critical point theory and Morse theory (critical groups), we show that the problem has at least three nontrivial smooth solutions, two of which have constant sign. In the process we prove some results of independent interest concerning the unique continuation property of eigenfunctions and the critical groups at infinity of a C¹$C^1$-functionals.