The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case

The Two-Dimensional Finite Bin Packing Problem (2BP) consists of determining the minimum number of large identical rectangles, bins, that are required for allocating without overlapping a given set of rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. In this paper we describe new lower bounds for the 2BP where the items have a fixed orientation and we show that the new lower bounds dominate two lower bounds proposed in the literature. These lower bounds are extended in Part II (see Boschetti and Mingozzi 2002) for a more general version of the 2BP where some items can be rotated by . Moreover, in Part II a new heuristic algorithm for solving both versions of the 2BP is presented and computational results on test problems from the literature are given in order to evaluate the effectiveness of the proposed lower bounds.     

On efficient computation and asymptotic sharpness of Kalantari's bounds for zeros of polynomials

We study an infinite family of lower and upper bounds on the modulus of zeros of complex polynomials derived by Kalantari. We first give a simple characterization of these bounds which leads to an efficient algorithm for their computation. For a polynomial of degree our algorithm computes the first bounds in Kalantari's family in operations. We further prove that for every complex polynomial these lower and upper bounds converge to the tightest annulus containing the roots, and thus settle a problem raised in Kalantari's paper.

     

Computation of capacity

This article introduces a method for computing upper and lower bounds for the logarithmic capacity of a compact plane set. If the set has the Hölder continuity property, then these bounds converge to the value of the capacity. A number of examples are discussed in detail, including the Cantor middle-third set, for which we estimate .

     

Transition Probabilities for Symmetric Jump Processes

We consider symmetric Markov chains on the integer lattice in dimensions, where and the conductance between and is comparable to . We establish upper and lower bounds for the transition probabilities that are sharp up to constants.

     

Long-term stability of variable stepsize approximations of semigroups

This paper is concerned with the stability of rational one-step approximations of semigroups. Particular emphasis is laid on long-term stability bounds. The analysis is based on a general Banach space framework and allows variable stepsize sequences. Under reasonable assumptions on the stepsize sequence, asymptotic stability bounds for general semigroups are derived. The bounds are typical in the sense that they contain, in general, a factor that grows with the number of steps. Under additional hypotheses on the approximation, more favorable stability bounds are obtained for the subclass of holomorphic semigroups.

     

An estimate for weighted Hilbert transform via square functions

We show that the norm of the Hilbert transform as an operator on the weighted space is bounded by a constant multiple of the power of the constant of , in other words by . We also give a short proof for sharp upper and lower bounds for the dyadic square function.

     

On the condition number of the total least squares problem

This paper concerns singular value decomposition (SVD)-based computable formulas and bounds for the condition number of the total least squares (TLS) problem. For the TLS problem with the coefficient matrix $A$ and the right-hand side $b$ , a new closed formula is presented for the condition number. Unlike an important result in the literature that uses the SVDs of both $A$ and $[A,\ b]$ , our formula only requires the SVD of $[A,\ b]$ . Based on the closed formula, both lower and upper bounds for the condition number are derived. It is proved that they are always sharp and estimate the condition number accurately. A few lower and upper bounds are further established that involve at most the smallest two singular values of $A$ and of $[A,\ b]$ . Tightness of these bounds is discussed, and numerical experiments are presented to confirm our theory and to demonstrate the improvement of our upper bounds over the two upper bounds due to Golub and Van Loan as well as Baboulin and Gratton. Such lower and upper bounds are particularly useful for large scale TLS problems since they require the computation of only a few singular values of $A$ and $[A, \ b]$ other than all the singular values of them.     

New upper bounds for kissing numbers from semidefinite programming

Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases .

     

Global lower bound for the heat kernel of

We obtain global in time and qualitatively sharp lower bounds for the heat kernel of the singular Schrödinger operator with 0$">. Here is either the Laplace-Beltrami operator or the Laplacian on the Heisenberg group. This complements a recent paper by P. D. Milman and Yu. A. Semenov in which an upper bound was found. The above potential is interesting because it is a border line case where both the strong maximum principle and Gaussian bounds fail.

     

Growth of fundamental groups and isoembolic volume and diameter

Some properties of fundamental groups of Riemannian manifolds will be studied without a lower bound assumption on Ricci curvature. The main method is to relate the local packing to global packing instead of using the Bishop-Gromov relative volume comparison. This method allows us to control the volume growth of the universal cover and yields bounds on the number of generators of in terms of some isoembolic geometric invariants of .

     

On the Complexity of Parallel Algorithms for Computing Inverses in GF(2^m) with m Prime

Inversion over a finite field is usually an expensive operation which is a crucial issue in many applications, such as cryptography and error-control codes. In this paper, three different strategies for computing the inverse over binary finite fields , called Eulerian, Gaussian, and Euclidean, respectively, are discussed and compared in terms of time and space complexity. In particular, some new upper and lower bounds to the respective complexities are evaluated.     

Symplectic -handles and transverse links

A standard convexity condition on the boundary of a symplectic manifold involves an induced positive contact form (and contact structure) on the boundary; the corresponding concavity condition involves an induced negative contact form. We present two methods of symplectically attaching -handles to convex boundaries of symplectic -manifolds along links transverse to the induced contact structures. One method results in concave boundaries and depends on a fibration of the link complement over ; in this case the handles can be attached with any framing larger than a lower bound determined by the fibration. The other method results in a weaker convexity condition on the new boundary (sufficient to imply tightness of the new contact structure), and in this case the handles can be attached with any framing less than a certain upper bound. These methods supplement methods developed by Weinstein and Eliashberg for attaching symplectic -handles along Legendrian knots.

     

Dual decompositions of 4-manifolds II: Linear invariants

This paper continues the study of decompositions of a smooth 4-manifold into two handlebodies with handles of index . Part I (Trans. Amer. Math. Soc. 354 (2002), 1373-1392) gave existence results in terms of spines and chain complexes over the fundamental group of the ambient manifold. Here we assume that one side of a decomposition has larger fundamental group, and use this to define algebraic-topological invariants. These reveal a basic asymmetry in these decompositions: subtle changes on one side can force algebraic-topologically detectable changes on the other. A solvable iteration of the basic invariant gives an ``obstruction theory' using lower commutator quotients. By thinking of a 2-handlebody as essentially determined by the links used as attaching maps for its 2-handles, this theory can be thought of as giving ``ambient' link invariants. The moves used are related to the grope cobordism of links developed by Conant-Teichner, and the Cochran-Orr-Teichner filtration of the link concordance groups. The invariants give algebraically sophisticated ``finite type' invariants in the sense of Vassilaev.

     

On the centered Hardy-Littlewood maximal operator

We will study the centered Hardy-Littlewood maximal operator acting on positive linear combinations of Dirac deltas. We will use this to obtain improvements in both the lower and upper bounds or the best constant in the weak inequality for this operator. In fact we will show that .

     

Cusp size bounds from singular surfaces in hyperbolic 3-manifolds

Singular maps of surfaces into a hyperbolic 3-manifold are utilized to find upper bounds on meridian length, -curve length and maximal cusp volume for the manifold. This allows a proof of the fact that there exist hyperbolic knots with arbitrarily small cusp density and that every closed orientable 3-manifold contains a knot whose complement is hyperbolic with maximal cusp volume less than or equal to 9. We also find particular upper bounds on meridian length, -curve length and maximal cusp volume for hyperbolic knots in depending on crossing number. Particular improved bounds are obtained for alternating knots.

     

Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles

We provide a variety of new upper and lower bounds and simpler proof techniques for the efficient construction of binary space partitions (BSPs) of axis-parallel rectangles of various dimensions. (a) We construct a set of $n$ disjoint axis-parallel segments in the plane such that any binary space auto-partition has size at least $2n-o(n)$, almost matching an upper bound of dAmore and Franciosa. (b) We establish a similar lower bound of $7n/3-o(n)$ for disjoint rectangles in the plane. (c) We simplify and improve BSP constructions of Paterson and Yao for disjoint segments in $\reals^d$ and disjoint rectangles in $\reals^3$. (d) We derive a worst-case bound of $\Theta(n^{5/3})$ for the size of BSPs of disjoint $2$-rectangles in $4$-space. (e) For disjoint $k$-rectangles in $d$-space, we prove the worst-case bound $\Theta(n^{d/(d-k)})$, for any $k<d/2$; this bound holds for all $k<d$ if the rectangles are allowed to intersect.     

Many Neighborly Polytopes and Oriented Matroids

In this paper we present a new technique to construct neighborly polytopes, and use it to prove a lower bound of ${\big (( r+d ) ^{( \frac{r}{2}+\frac{d}{2} )^{2}}\big )}\big /{\big ({r}^{{(\frac{r}{2})}^{2}} {d}^{{(\frac{d}{2})}^{2}}{\mathrm{e}^{3\frac{r}{2}\frac{d}{2}}}\big )}$ for the number of combinatorial types of vertex-labeled neighborly polytopes in even dimension d with $r+d+1$ vertices. This improves current bounds on the number of combinatorial types of polytopes. The previous best lower bounds for the number of neighborly polytopes were found by Shemer in 1982 using a technique called the Sewing Construction. We provide a new simple proof that sewing works, and generalize it to oriented matroids in two ways: to Extended Sewing and to Gale Sewing. Our lower bound is obtained by estimating the number of polytopes that can be constructed via Gale Sewing. Combining both new techniques, we are also able to construct many non-realizable neighborly oriented matroids.     

Involutions fixing , I

This paper studies the equivariant cobordism classification of all involutions fixing a disjoint union of an odd-dimensional real projective space with its normal bundle nonbounding and a Dold manifold with 0$"> and 0$">. For odd , the complete analysis of the equivariant cobordism classes of such involutions is given except that the upper and lower bounds on codimension of may not be best possible; for even , the problem may be reduced to the problem for even projective spaces.

     

Global error bounds for the extended vertical LCP

A new necessary and sufficient condition for the row -property is given. By using this new condition and a special row rearrangement, we provide two global error bounds for the extended vertical linear complementarity problem under the row -property, which extend the error bounds given in Chen and Xiang (Math. Program. 106:513–525, 2006) and Mathias and Pang (Linear Algebra Appl. 132:123–136, 1990) for the P-matrix linear complementarity problem, respectively. We show that one of the new error bounds is sharper than the other, and it can be computed easily for some special class of the row -property block matrix. Numerical examples are given to illustrate the error bounds. The work was in part supported by a Grant-in-Aid from Japan Society for the Promotion of Science, and the National Natural Science Foundation of China (10671010).     

Lower bounds and stochastic optimization algorithms for uniform designs with three or four levels

New lower bounds for three- and four-level designs under the centered -discrepancy are provided. We describe necessary conditions for the existence of a uniform design meeting these lower bounds. We consider several modifications of two stochastic optimization algorithms for the problem of finding uniform or close to uniform designs under the centered -discrepancy. Besides the threshold accepting algorithm, we introduce an algorithm named balance-pursuit heuristic. This algorithm uses some combinatorial properties of inner structures required for a uniform design. Using the best specifications of these algorithms we obtain many designs whose discrepancy is lower than those obtained in previous works, as well as many new low-discrepancy designs with fairly large scale. Moreover, some of these designs meet the lower bound, i.e., are uniform designs.