Optimally Cutting a Surface into a Disk

We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard in general, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n ^O(g+k), where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log² g)-approximation of the minimum cut graph in O(g ² n log n) time.     

Explicit exact solutions for a new generalized Hamiltonian amplitude equation with nonlinear terms of any order

Making use of a proper transformation and a generalized ansatz, we consider a new generalized Hamiltonian amplitude equation with nonlinear terms of any order, iu_x + u_tt + (|u|^p + |u|^2p)u + u_xt = 0. As a result, many explicit exact solutions, which include kink-shaped soliton solutions, bell-shaped soliton solutions, periodic wave solutions, the combined formal solitary wave solutions and rational solutions, are obtained.Received: April 4, 2002     

The optimal rate of convergence of the <Emphasis Type="Italic">p</Emphasis>-version of the boundary element method in two dimensions

Summary. We introduce the Jacobi-weighted Besov and Sobolev spaces in the one-dimensional setting. In the framework of these spaces, we analyze lower and upper bounds for approximation errors in the p-version of the boundary element method for hypersingular and weakly singular integral operators on polygons. We prove the optimal rate of convergence for the p-version in the energy norms of and respectively.Mathematics Subject Classification (2000): 65N38This author is supported by NSERC of Canada under Grant OGP0046726 and partially supported by the FONDAP Program (Chile) on Numerical Analysis during his visit of the Universidad de Concepción in 2001.This author is supported by Fondecyt project no. 1010220 and by the FONDAP Program (Chile) on Numerical Analysis.Revised version received January 28, 2004     

Completeness theorem for propositional probabilistic models whose measures have only finite ranges

A propositional logic is defined which in addition to propositional language contains a list of probabilistic operators of the form P_s (with the intended meaning the probability is at least s). The axioms and rules syntactically determine that ranges of probabilities in the corresponding models are always finite. The completeness theorem is proved. It is shown that completeness cannot be generalized to arbitrary theories.This research was supported by Ministarstvo za nauku, tehnologije i razvoj Republike Srbije, through Matematiki institut, under grant 1379Mathematics Subject Classification (2000): 03C70, 03B48     

A MIP approach for some practical packing problems: Balancing constraints and tetris-like items

This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach is proposed. The three-dimensional single bin packing problem is considered. It consists of orthogonally placing, with possibility of rotation, the maximum number of parallelepipeds into a given parallelepiped. A MIP formulation of the problem is reported together with a MIP-based heuristic approach. Balancing conditions are furthermore examined, as well as the orthogonal placement (with rotation) of tetris-like items into a rectangular domain.Received: September 2003, Revised: February 2004, AMS classification: 90B99, 05B40, 90C90, 90C59Thanks are due to T. A. Ciriani for the important suggestions given for the whole paper and to S. Gliozzi (IBM, Business Consulting Services) for the significant support offered, in particular in discussing the topics presented in Sect. 2.1.     

Higher-order energy expansions and spike locations

We consider the following singularly perturbed semilinear elliptic problem: where is a bounded domain in R ^N with smooth boundary , is a small constant and f is some superlinear but subcritical nonlinearity. Associated with (I) is the energy functional defined by where . Ni and Takagi ([29, 30]) proved that for a single boundary spike solution , the following asymptotic expansion holds: where c ₁ > 0 is a generic constant, is the unique local maximum point of and is the boundary mean curvature function at . In this paper, we obtain a higher-order expansion of where c ₂, c ₃ are generic constants and is the scalar curvature at . In particular c ₃ > 0. Some applications of this expansion are given.Received: 14 January 2003, Accepted: 28 July 2003, Published online: 15 October 2003Mathematics Subject Classification (2000): Primary 35B40, 35B45; Secondary 35J25     

Rotations of Hypercyclic and Supercyclic Operators

Let T B(X) be a hypercyclic operator and a complex number of modulus 1. Then T is hypercyclic and has the same set of hypercyclic vectors as T. A version of this results gives for a wide class of supercyclic operators that x X is supercyclic for T if and only if the set {tTⁿ x : t > 0, n = 0, 1, ...} is dense in X. This gives answers to several questions studied in the literature.     

Maximal ergodic theorems and applications to Riemannian geometry

We prove new ergodic theorems in the context of infinite ergodic theory, and give some applications to Riemannian and Kähler manifolds without conjugate points. One of the consequences of these ideas is that a complete manifold without conjugate points has nonpositive integral of the infimum of Ricci curvatures, whenever this integral makes sense. We also show that a complete Kähler manifold with nonnegative holomorphic curvature is flat if it has no conjugate points.     

Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph

The accumulation of the Jacobian matrix F of a vector function can be regarded as a transformation of its linearized computational graph into a subgraph of the directed complete bipartite graph K_n,m. This transformation can be performed by applying different elimination techniques that may lead to varying costs for computing F. This paper introduces face elimination as the basic technique for accumulating Jacobian matrices by using a minimal number of arithmetic operations. Its superiority over both edge and vertex elimination methods is shown. The intention is to establish the conceptual basis for the ongoing development of algorithms for optimizing the computation of Jacobian matrices.     

The -conjecture and equivariant <Emphasis Type="Italic">e</Emphasis><Subscript><Emphasis Type="Italic">C</Emphasis></Subscript>-invariants

Let X be a smooth closed oriented non-spin 4-manifold with even intersection form kE₈nH (n1). The -conjecture states that n is greater than or equal to |k|. In this paper we give a proof of the -conjecture. The strategy of this paper is to use the finite dimensional approximation of the map induced from the Seiberg-Witten equations and equivariant e_C-invariants as in the paper of M. Furuta and Y. Kametani.Mathematics Subject Classification (1991): 57R55This work was supported by Korea Research Foundation Grant (KRF–2002–003–C00011).