Ambient connections realising conformal Tractor holonomy

For a conformal manifold we introduce the notion of an ambient connection, an affine connection on an ambient manifold of the conformal manifold, possibly with torsion, and with conditions relating it to the conformal structure. The purpose of this construction is to realise the normal conformal Tractor holonomy as affine holonomy of such a connection. We give an example of an ambient connection for which this is the case, and which is torsion free if we start the construction with a C-space, and in addition Ricci-flat if we start with an Einstein manifold. Thus, for a C-space this example leads to an ambient metric in the weaker sense of Čap and Gover, and for an Einstein space to a Ricci-flat ambient metric in the sense of Fefferman and Graham. Current address for first author: Erwin Schr?dinger International Institute for Mathematical Physics (ESI), Boltzmanngasse 9, 1090 Vienna, Austria Current address for second author: Department of Mathematics, University of Hamburg, Bundesstra?e 55, 20146 Hamburg, Germany     

Integrability properties of a generalized reduction of the KdV6 equation

We consider the integrability properties of a generalized version of a similarity reduction of the so-called KdV6 equation, an equation that has recently generated much interest. We give a linear problem for this generalized reduction and show that it satisfies the requirements of the Ablowitz-Ramani-Segur algorithm. In addition we give a Bäcklund transformation to a related equation, giving also an auto-Bäcklund transformation for this last. Our results mirror those for the Korteweg-de Vries equation itself, which has a similarity reduction to an ordinary differential equation which is related by a Bäcklund transformation to the second Painlevé equation, this last having an auto-Bäcklund transformation.     

Potential analysis for a class of diffusion equations: A Gaussian bounds approach

We axiomatically develop a potential analysis for a general class of hypoelliptic diffusion equations under the following basic assumptions: doubling condition and segment property for an underlying distance and Gaussian bounds of the fundamental solution. Our analysis is principally aimed to obtain regularity criteria and uniform boundary estimates for the Perron-Wiener solution to the Dirichlet problem. As an example of application, we also derive an exterior cone criterion of boundary regularity and scale-invariant Harnack inequality and Hölder estimate for an important class of operators in non-divergence form with Hölder continuous coefficients, modeled on Hörmander vector fields.     

Generalized Graded Hecke Algebras of Types B and D

For a root system of type B we study an algebra similar to a graded Hecke algebra, isomorphic to a subalgebra of the rational Cherednik algebra. We introduce principal series modules over it and prove an irreducibility criterion for these modules. We deduce similar results for an algebra associated to a root system of type D.     

Exact algorithms for dominating set

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969ⁿ) time and polynomial space algorithm.     

Fast parallel strong orientation of mixed graphs and related augmentation problems

The strong orientation problem is: Given an undirected graph, G, assign orientations to its edges so that the resulting directed graph is strongly connected. Robbins showed when such an orientation exists. A generalization of this problem is when the input graph is mixed (i.e., contains some directed and some undirected edges). Boesch and Tindell gave necessary and sufficient conditions for a strong orientation to exist in a mixed graph. In this paper we give an NC algorithm for constructing a strong orientation for a given mixed graph after determining if it exists. We also give an NC algorithm for adding a minimum set of arcs to a mixed graph to make it strongly orientable. We give simplified NC algorithms for the following special cases: find minimum augmentations to make a digraph strongly connected and to make an undirected graph bridge-connected. All the algorithms presented run within the time and processor bounds required for computing the transitive closure of a digraph.     

Erlang loss bounds for OT–ICU systems

In hospitals, patients can be rejected at both the operating theater (OT) and the intensive care unit (ICU) due to limited ICU capacity. The corresponding ICU rejection probability is an important service factor for hospitals. Rejection of an ICU request may lead to health deterioration for patients, and for hospitals to costly actions and a loss of precious capacity when an operation is canceled. There is no simple expression available for this ICU rejection probability that takes the interaction with the OT into account. With c the ICU capacity (number of ICU beds), this paper proves and numerically illustrates a lower bound by an M|G|c|c system and an upper bound by an M|G|c-1|c-1 system, hence by simple Erlang loss expressions. The result is based on a product form modification for a special OT–ICU tandem formulation and proved by a technically complicated Markov reward comparison approach. The upper bound result is of particular practical interest for dimensioning an ICU to secure a prespecified service quality. The numerical results include a case study.     

Approximate proximal methods in vector optimization

This paper studies the vector optimization problem of finding weakly efficient points for mappings in a Banach space Y, with respect to the partial order induced by a closed, convex, and pointed cone C ⊂ Y with a nonempty interior. The proximal method in vector optimization is extended to develop an approximate proximal method for this problem by virtue of the approximate proximal point method for finding a root of a maximal monotone operator. In this approximate proximal method, the subproblems consist of finding weakly efficient points for suitable regularizations of the original mapping. We present both an absolute and a relative version, in which the subproblems are solved only approximately. Weak convergence of the generated sequence to a weak efficient point is established. In addition, we also discuss an extension to Bregman-function-based proximal algorithms for finding weakly efficient points for mappings.     

Upper and Lower Bounds for the Stanley Depth of Certain Classes of Monomial Ideals and Their Residue Class Rings

We give an upper bound for the Stanley depth of the edge ideal of a complete k-partite hypergraph and as an application we give an upper bound for the Stanley depth of a monomial ideal in a polynomial ring S. We also give a lower and an upper bound for the cyclic module S/I associated to the complete k-partite hypergraph.     

On the spectrums of frame multiresolution analyses

We first give conditions for a univariate square integrable function to be a scaling function of a frame multiresolution analysis (FMRA) by generalizing the corresponding conditions for a scaling function of a multiresolution analysis (MRA). We also characterize the spectrum of the ‘central space’ of an FMRA, and then give a new condition for an FMRA to admit a single frame wavelet solely in terms of the spectrum of the central space of an FMRA. This improves the results previously obtained by Benedetto and Treiber and by some of the authors. Our methods and results are applied to the problem of the ‘containments’ of FMRAs in MRAs. We first prove that an FMRA is always contained in an MRA, and then we characterize those MRAs that contain ‘genuine’ FMRAs in terms of the unique low-pass filters of the MRAs and the spectrums of the central spaces of the FMRAs to be contained. This characterization shows, in particular, that if the low-pass filter of an MRA is almost everywhere zero-free, as is the case of the MRAs of Daubechies, then the MRA contains no FMRAs other than itself.     

Eigenvector method,consistency test and inconsistency repairing for an incomplete fuzzy preference relation

In this paper, we extend the eigenvector method (EM) to priority for an incomplete fuzzy preference relation. We give a reasonable definition of multiplicative consistency for an incomplete fuzzy preference relation. We also give an approach to judge whether an incomplete fuzzy relation is acceptable or not. We develop the acceptable consistency ratio for an incomplete multiplicative fuzzy preference relation, which is simple and similar to Saaty’s consistency ratio (CR) for the multiplicative preference relation. If the incomplete fuzzy preference relation is not of acceptable consistency, we define a criterion to find the unusual and false element (UFE) in the preference relation, and present an algorithm to repair an inconsistent fuzzy preference relation until its consistency is satisfied with the consistency ratio. As a result, our improvement method cannot only satisfy the consistency requirement, but also preserve the initial preference information as much as possible. Finally, an example is illustrated to show that our method is simple, efficiency, and can be performed on computer easily.     

The <Emphasis Type="Italic">p</Emphasis>-Cockcroft Property of Central Extensions of Groups II

In [6], ?evik defined necessary and sufficient conditions for the presentation of a central extension of a cyclic group by an ordinary group to be p-Cockcroft, where p is a prime or 0. In this paper, as a next step of this above result, we will define the p-Cockcroft property for the presentation of a central extension of an abelian group by any group. Finally, as an application of the main result, we will present an example.     

Stable étale realization and étale cobordism

We show that there is a stable homotopy theory of profinite spaces and use it for two main applications. On the one hand we construct an étale topological realization of the stable A¹-homotopy theory of smooth schemes over a base field of arbitrary characteristic in analogy to the complex realization functor for fields of characteristic zero.On the other hand we get a natural setting for étale cohomology theories. In particular, we define and discuss an étale topological cobordism theory for schemes. It is equipped with an Atiyah-Hirzebruch spectral sequence starting from étale cohomology. Finally, we construct maps from algebraic to étale cobordism and discuss algebraic cobordism with finite coefficients over an algebraically closed field after inverting a Bott element.     

A variant of Newton's method and its application

This paper details an existence and uniqueness theorem for solving an operator equation of the form F(x)=0, where F is a Gateaux differentiable operator defined on an open convex subset of a Banach space proved. From the main theorem, an earlier theorem of Argyros follows as a consequence. Other corollaries constitute the semilocal versions of the theorems due to Ozban and Weerakoon and Fernando in a general Banach space. Our main theorem leads to the existence of solutions for a class of nonlinear Urysohn-type integral equations in the n-dimensional Euclidean space.     

Explicit Construction and Uniqueness for Universal Operator Algebras of Directed Graphs

Given a directed graph, there exist a universal operator algebraand universal C*-algebra associated to the directed graph. Inthis paper we give intrinsic constructions for these objects.We also provide an explicit construction for the maximal C*-algebraof an operator algebra. We discuss uniqueness of the universalalgebras for finite graphs, showing that for finite graphs thegraph is an isomorphism invariant for the universal operatoralgebra of a directed graph. We show that the underlying undirectedgraph is a Banach algebra isomorphism invariant for the universalC*-algebra of a directed graph.     

FACTORIZATION IN MONOID DOMAINS

In this paper, we determine necessary and sufficient conditions for the group ring D[G] to be a BFD (resp., an FFD, an SFFD). Also we give necessary and sufficient conditions for the monoid domain D[S] to be a BFD (resp., an FFD, an SFFD). In addition, we characterize when themonoid domain D[S] is a UFD in terms of 2-factoriality.     

A new class of almost complex structures

The purpose of this paper is to introduce a new class of almost complex structures J on a Riemannian manifold M by using a certain identity for the relationship between the tensor F _i ^j of J and the Riemann curvature tensor R _hijk of M. This class contains the Kählerian structures, and its relationship with some known classes of almost Hermitian structures defined by similar identities is discussed. For convenience we call each structure of this new class an almost C-structure, and a manifold with an almost C-structure an almost C-manifold. We obtain an analogue of F. Schur's theorem concerning the holomorphic sectional curvature of an almost Hermitian C-manifold, and some sufficient conditions for an almost Hermitian C-manifold to be Kählerian. We show that these results are also true for a manifold with a complex structure.     

A fast heuristic algorithm for the maximum concurrent <Emphasis Type="Italic">k</Emphasis>-splittable flow problem

In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules.     

Online Point Location in Planar Arrangements and Its Applications

Recently, Har-Peled [HP2] presented a new randomized technique for online construction of the zone of a curve in a planar arrangement of arcs. In this paper we present several applications of this technique, which yield improved solutions to a variety of problems. These applications include: (i) an efficient mechanism for performing online point-location queries in an arrangement of arcs; (ii) an efficient algorithm for computing an approximation to the minimum weight Steiner tree of a set of points, where the weight is the number of intersections between the tree edges and a given collection of arcs; (iii) a subquadratic algorithm for cutting a set of pseudo-parabolas into pseudo-segments; (iv) an algorithm for cutting a set of line segments (``rods') in 3-space to eliminate all cycles in the vertical depth order; and (v) a near-optimal algorithm for reporting all bichromatic intersections between a set R of red arcs and a set B of blue arcs, where the unions of the arcs in each set are both connected. Received December 22, 1999, and in revised form August 25, 2000. Online publication May 11, 2001.