Three-dimensional packings with rotations

We present approximation algorithms for the three-dimensional strip packing problem, and the three-dimensional bin packing problem. We consider orthogonal packings where 90 degrees rotations are allowed. The algorithms we show for these problems have asymptotic performance bounds 2.64, and 4.89, respectively. These algorithms are for the more general case in which the bounded dimensions of the bin given in the input are not necessarily equal (that is, we consider bins for which the length. the width and the height are not necessarily equal). Moreover, we show that these problems-in the general version-are as hard to approximate as the corresponding oriented version. (C) 2009 Elsevier Ltd. All rights reserved.

Efficient solutions to factored MDPs with imprecise transition probabilities

When modeling real-world decision-theoretic planning problems in the Markov Decision Process (MDP) framework, it is often impossible to obtain a completely accurate estimate of transition probabilities. For example, natural uncertainty arises in the transition specification due to elicitation of MOP transition models from an expert or estimation from data, or non-stationary transition distributions arising from insufficient state knowledge. In the interest of obtaining the most robust policy under transition uncertainty, the Markov Decision Process with Imprecise Transition Probabilities (MDP-IPs) has been introduced to model such scenarios. Unfortunately, while various solution algorithms exist for MDP-IPs, they often require external calls to optimization routines and thus can be extremely time-consuming in practice. To address this deficiency, we introduce the factored MDP-IP and propose efficient dynamic programming methods to exploit its structure. Noting that the key computational bottleneck in the solution of factored MDP-IPs is the need to repeatedly solve nonlinear constrained optimization problems, we show how to target approximation techniques to drastically reduce the computational overhead of the nonlinear solver while producing bounded, approximately optimal solutions. Our results show up to two orders of magnitude speedup in comparison to traditional ""flat"" dynamic programming approaches and up to an order of magnitude speedup over the extension of factored MDP approximate value iteration techniques to MDP-IPs while producing the lowest error of any approximation algorithm evaluated. (C) 2011 Elsevier B.V. All rights reserved.

Billiards in a General Domain with Random Reflections

We study stochastic billiards on general tables: a particle moves according to its constant velocity inside some domain D R(d) until it hits the boundary and bounces randomly inside, according to some reflection law. We assume that the boundary of the domain is locally Lipschitz and almost everywhere continuously differentiable. The angle of the outgoing velocity with the inner normal vector has a specified, absolutely continuous density. We construct the discrete time and the continuous time processes recording the sequence of hitting points on the boundary and the pair location/velocity. We mainly focus on the case of bounded domains. Then, we prove exponential ergodicity of these two Markov processes, we study their invariant distribution and their normal (Gaussian) fluctuations. Of particular interest is the case of the cosine reflection law: the stationary distributions for the two processes are uniform in this case, the discrete time chain is reversible though the continuous time process is quasi-reversible. Also in this case, we give a natural construction of a chord ""picked at random"" in D, and we study the angle of intersection of the process with a (d - 1) -dimensional manifold contained in D.

Homeomorphisms of the annulus with a transitive lift

Let f be a homeomorphism of the closed annulus A that preserves the orientation, the boundary components and that has a lift (f) over tilde to the infinite strip (A) over tilde which is transitive. We show that, if the rotation numbers of both boundary components of A are strictly positive, then there exists a closed nonempty unbounded set B(-) subset of (A) over tilde such that B(-) is bounded to the right, the projection of B to A is dense, B - (1, 0) subset of B and (f) over tilde (B) subset of B. Moreover, if p(1) is the projection on the first coordinate of (A) over tilde, then there exists d > 0 such that, for any (z) over tilde is an element of B(-), lim sup (n ->infinity) p1((f) over tilde (n)((z) over tilde)) - p(1) ((z) over tilde)/n < - d. In particular, using a result of Franks, we show that the rotation set of any homeomorphism of the annulus that preserves orientation, boundary components, which has a transitive lift without fixed points in the boundary is an interval with 0 in its interior.

On the Derived Categories and Quasitilted Algebras

In this paper, we present some results on the bounded derived category of Artin algebras, and in particular on the indecomposable objects in these categories, using homological properties. Given a complex X*, we consider the set J(X*) = {i is an element of Z vertical bar H(i)(X*) not equal 0} and we define the application l(X*) = maxJ(X*) - minJ(X*) + 1. We give relationships between some homological properties of an algebra and the respective application l. On the other hand, using homological properties again, we determine two subcategories of the bounded derived category of an algebra, which turn out to be the bounded derived categories of quasi-tilted algebras. As a consequence of these results we obtain new characterizations of quasi-tilted and quasi-tilted gentle algebras.

Finite-dimensional non-associative algebras and codimension growth

Let A be a (non-necessarily associative) finite-dimensional algebra over a field of characteristic zero. A quantitative estimate of the polynomial identities satisfied by A is achieved through the study of the asymptotics of the sequence of codimensions of A. It is well known that for such an algebra this sequence is exponentially bounded. Here we capture the exponential rate of growth of the sequence of codimensions for several classes of algebras including simple algebras with a special non-degenerate form, finite-dimensional Jordan or alternative algebras and many more. In all cases such rate of growth is integer and is explicitly related to the dimension of a subalgebra of A. One of the main tools of independent interest is the construction in the free non-associative algebra of multialternating polynomials satisfying special properties. (C) 2010 Elsevier Inc. All rights reserved.

The Gauss-Kronecker curvature of minimal hypersurfaces in four-dimensional space forms

LetQ(4)( c) be a four-dimensional space form of constant curvature c. In this paper we show that the infimum of the absolute value of the Gauss-Kronecker curvature of a complete minimal hypersurface in Q(4)(c), c <= 0, whose Ricci curvature is bounded from below, is equal to zero. Further, we study the connected minimal hypersurfaces M(3) of a space form Q(4)( c) with constant Gauss-Kronecker curvature K. For the case c <= 0, we prove, by a local argument, that if K is constant, then K must be equal to zero. We also present a classification of complete minimal hypersurfaces of Q(4)( c) with K constant.

On a formula for the spectral flow and its applications

We consider a continuous path of bounded symmetric Fredholm bilinear forms with arbitrary endpoints on a real Hilbert space, and we prove a formula that gives the spectral flow of the path in terms of the spectral flow of the restriction to a finite codimensional closed subspace. We also discuss the case of restrictions to a continuous path of finite codimensional closed subspaces. As an application of the formula, we introduce the notion of spectral flow for a periodic semi-Riemannian geodesic, and we compute its value in terms of the Maslov index. (C) 2010 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim

Curvature Estimates for Submanifolds in Warped Products

We give estimates of the intrinsic and the extrinsic curvature of manifolds that are isometrically immersed as cylindrically bounded submanifolds of warped products. We also address extensions of the results in the case of submanifolds of the total space of a Riemannian submersion.

Examples from trees, related to discrete subsets, pseudo-radiality and omega-boundedness

We construct some examples using trees. Some of them are consistent counterexamples for the discrete reflection of certain topological properties. All the properties dealt with here were already known to be non-discretely reflexive if we assume CH and we show that the same is true assuming the existence of a Suslin tree. In some cases we actually get some ZFC results. We construct also, using a Suslin tree, a compact space that is pseudo-radial but it is not discretely generated. With a similar construction, but using an Aronszajn tree, we present a ZFC space that is first countable, omega-bounded but is not strongly w-bounded, answering a question of Peter Nyikos. (C) 2008 Elsevier B.V. All rights reserved.