New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional 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. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

The Two-Dimensional Finite Bin Packing Problem. Part II: New lower and upper bounds

This paper is the second of a two part series and describes new lower and upper bounds for a more general version of the Two-Dimensional Finite Bin Packing Problem (2BP) than the one considered in Part I (see Boschetti and Mingozzi 2002). With each item is associated an input parameter specifying if it has a fixed orientation or it can be rotated by . This problem contains as special cases the oriented and non-oriented 2BP. The new lower bound is based on the one described in Part I for the oriented 2BP. The computational results on the test problems derived from the literature show the effectiveness of the new proposed lower and upper bounds.     

Testing properties of directed graphs: acyclicity and connectivity*

This article initiates the study of testing properties of directed graphs. In particular, the article considers the most basic property of directed graphs—acyclicity . Because the choice of representation affects the choice of algorithm, the two main representations of graphs are studied. For the adjacency‐matrix representation, most appropriate for dense graphs, a testing algorithm is developed that requires query and time complexity of $\widetilde{O}(1/\epsilon^2)$, where ? is a distance parameter independent of the size of the graph. The algorithm, which can probe the adjacency matrix of the graph, accepts every graph that is acyclic, and rejects, with probability at least 2/3, every graph whose adjacency matrix should be modified in at least ? fraction of its entries so that it becomes acyclic. For the incidence list representation, most appropriate for sparse graphs, an Ω(|V|^1/3) lower bound is proved on the number of queries and the time required for testing, where V is the set of vertices in the graph. Along with acyclicity, this article considers the property of strong connectivity. Contrasting upper and lower bounds are proved for the incidence list representation. In particular, if the testing algorithm can query on both incoming and outgoing edges at each vertex, then it is possible to test strong connectivity in $\widetilde{O}(1/\epsilon)$ time and query complexity. On the other hand, if the testing algorithm only has access to outgoing edges, then $\Omega(\sqrt{N})$ queries are required to test for strong connectivity. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 184–205, 2002     

Tight Bounds for Connecting Sites Across Barriers

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines, it is known that there is a spanning tree such that every barrier is crossed by tree edges, and this bound is asymptotically optimal. Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Lower bound constructions are known with 3 crossings per barrier and 2n total cost. We obtain tight bounds on the minimum cost of spanning trees in the special case where the barriers are interior disjoint line segments that form a convex subdivision of the plane and there is a point in every cell of the subdivision. In particular, we show that there is a spanning tree such that every barrier crosses at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are the best possible. Work by Eynat Rafalin and Diane Souvaine was supported by the National Science Foundation under Grant #CCF-0431027. E. Rafalin’s research conducted while at Tufts University.     

Improved Analytical Bounds for Gambler’s Ruin Probabilities

Given integer-valued wagers Feller (1968) has established upper and lower bounds on the probability of ruin, which often turn out to be very close to each other. However, the exact calculation of these bounds depends on the unique non-trivial positive root of the equation () = 1, where is the probability generating function for the wager. In the situation of incomplete information about the distribution of the wager, one is interested in bounds depending only on the first few moments of the wager. Ethier and Khoshnevisan (2002) derive bounds depending explicitly on the first four moments. However, these bounds do not make the best possible use of the available information. Based on the theory of s-convex extremal random variables among arithmetic and real random variables, a substantial improvement can be given. By fixed first four moments of the wager, the obtained new bounds are nearly perfect analytical approximations to the exact bounds of Feller.AMS 2000 Subject Classification: 60E15, 60G40, 91A60     

Generalizations of Polya's urn Problem

We consider generalizations of the classical Polya urn problem: Given finitely many bins each containing one ball, suppose that additional balls arrive one at a time. For each new ball, with probability p, create a new bin and place the ball in that bin; with probability 1–p, place the ball in an existing bin, such that the probability that the ball is placed in a bin is proportional to $ m^\gamma $, where m is the number of balls in that bin. For p=0, the number of bins is fixed and finite, and the behavior of the process depends on whether is greater than, equal to, or less than 1. We survey the known results and give new proofs for all three cases. We then consider the case p>0. When =1, this is equivalent to the so-called preferential attachment scheme which leads to power law distribution for bin sizes. When >1, we prove that a single bin dominates, i.e., as the number of balls goes to infinity, the probability that any new ball either goes into that bin or creates a new bin converges to 1. When p > 0 and < 1, we show that under the assumption that certain limits exist, the fraction of bins having m balls shrinks exponentially as a function of m. We then discuss further generalizations and pose several open problems.AMS Subject Classification: 05D40, 60C05, 60G20, 68R10, 91C99.     

Relations between capacity utilization,minimal bin size and bin number

We consider the two-dimensional bin packing problem given a set of rectangular items, find the minimal number of rectangular bins needed to pack all items. Rotation of the items is not permitted. We show for any integer \({k} \ge 3\) that at most \({k}-1\) bins are needed to pack all items if every item fits into a bin and if the total area of items does not exceed \({k}/4\) -times the bin area. Moreover, this bound is tight. Furthermore, we show that only two bins are necessary to pack all items if the total area of items is not larger than the bin area, and if the height of each item is not larger than a third of the bin height and the width of every item does not exceed half of the bin width.     

When is the Fourier transform of an elementary function elementary?

Let F be a local field, a nontrivial unitary additive character of F, and V a finite dimensional vector space over F. Let us say that a complex function on V is elementary if it has the form , where , Q is a rational function (the phase function), are polynomials, and multiplicative characters of F. For generic , this function canonically extends to a distribution on V (if char(F) = 0). Occasionally, the Fourier transform of an elementary function is also an elementary function (the basic example is the Gaussian integral: k = 0, Q is a nondegenerate quadratic form). It is interesting to determine when exactly this happens. This question is the main subject of our study. In the first part of this paper we show that for or , if the Fourier transform of an elementary function with phase function -Q such that is another elementary function with phase function , then is the Legendre transform of Q (the "semiclassical condition"). We study properties and examples of phase functions satisfying this condition, and give a classification of phase functions such that both Q and are of the form f(x)/t, where f is a homogeneous cubic polynomial and t is an additional variable (this is one of the simplest possible situations). Unexpectedly, the proof uses Zak's classification theorem for Severi varieties.? In the second part of the paper we give a necessary and sufficient condition for an elementary function to have an elementary Fourier transform (in an appropriate "weak" sense) and explicit formulas for such Fourier transforms in the case when Q and are monomials, over any local field F. We also describe a generalization of these results to the case of monomials of norms of finite extensions of F. Finally, we generalize some of the above results (including Fourier integration formulas) to the case when and Q comes from a prehomogeneous vector space.     

An extremal problem for cycles in hamiltonian graphs

For integersp andr with 3 r p – 1, letf(p, r) denote the maximum number of edges in a hamiltonian graph of orderp which does not contain a cycle of lengthr. Results from literature on the determination off(p, r) are collected and a number of new lower bounds, many of which are conjectured to be best possible, are given. The main result presented is the proof thatf(p, 5) = (p – 3)²/4 + 5 for oddp 11.George Hendry died during the publication process.Supported by Deutsche Forschungsgemeinschaft (DFG), Grant We 1265.     

Packing random items of three colors

Consider three colors 1,2,3, and forj3, considern items (X _i,j)in of colorj. We want to pack these items inn bins of equal capacity (the bin size is not fixed, and is to be determined once all the objects are known), subject to the condition that each bin must contain exactly one item of each color, and that the total item sizes attributed to any given bin does not exceed the bin capacity. Consider the stochastic model where the random variables (X _i,jj)in,j3 are independent uniformly distributed over [0,1]. We show that there is a polynomial-time algorithm that produces a packing which has a wasted spaceK logn with overwhelming probability.Work partially supported by an N.S.F. grant.     

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).     

New lower bounds for bin packing problems with conflicts

The bin packing problem with conflicts (BPC) consists of minimizing the number of bins used to pack a set of items, where some items cannot be packed together in the same bin due to compatibility restrictions. The concepts of dual-feasible functions (DFF) and data-dependent dual-feasible functions (DDFF) have been used in the literature to improve the resolution of several cutting and packing problems. In this paper, we propose a general framework for deriving new DDFF as well as a new concept of generalized data-dependent dual-feasible functions (GDDFF), a conflict generalization of DDFF. The GDDFF take into account the structure of the conflict graph using the techniques of graph triangulation and tree-decomposition. Then we show how these techniques can be used in order to improve the existing lower bounds.     

Moment Inequalities for Sums of Dependent Random Variables under Projective Conditions

We obtain precise constants in the Marcinkiewicz-Zygmund inequality for martingales in for p>2 and a new Rosenthal type inequality for stationary martingale differences for p in ]2,3]. The Rosenthal inequality is then extended to stationary and adapted sequences. As in Peligrad et al. (Proc. Am. Math. Soc. 135:541–550, [2007]), the bounds are expressed in terms of -norms of conditional expectations with respect to an increasing field of sigma algebras. Some applications to a particular Markov chain are given.      

Minkowski Arrangements of Spheres

Let be a non-negative number not greater than 1. Consider an arrangement of (not necessarily congruent) spheres with positive homogenity in the n-dimensional Euclidean space, i.e., in which the infimum of the radii of the spheres divided by the supremum of the radii of the spheres is a positive number. With each sphere S of associate a concentric sphere of radius times the radius of S. We call this sphere the -kernel of S. The arrangement is said to be a Minkowski arrangement of order if no sphere of overlaps the -kernel of another sphere. The problem is to find the greatest possible density of n-dimensional Minkowski sphere arrangements of order . In this paper we give upper bounds on for .     

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus

We investigate read-once branching programs for the following search problem: given a Boolean m × n matrix with m > n, nd either an all-zero row, or two 1s in some column. Our primary motivation is that this models regular resolution proofs of the pigeonhole principle , and that for m > n ² no lower bounds are known for the length of such proofs. We prove exponential lower bounds (for arbitrarily large m!) if we further restrict this model by requiring the branching program either to finish one row of queries before asking queries about another row (the row model) or put the dual column restriction (the column model).Then we investigate a special class of resolution proofs for that operate with positive clauses of rectangular shape; we call this fragment the rectangular calculus. We show that all known upper bounds on the size of resolution proofs of actually give rise to proofs in this calculus and, inspired by this fact, also give a remarkably simple rectangular reformulation of the Haken–Buss–Turán lower bound for the case m n ². Finally we show that the rectangular calculus is equivalent to the column model on the one hand, and to transversal calculus on the other hand, where the latter is a natural proof system for estimating from below the transversal size of set families. In particular, our exponential lower bound for the column model translates both to the rectangular and transversal calculi.* Part of the work was done while this author was visiting Special Year on Logic and Algorithms at DIMACS, Princeton. Also supported by Russian Basic Research Foundation grant 96-01-01222. Part of this work was done while on sabbatical leave at the Institute for Advanced Study and Princeton University, Princeton. This work was supported by USA-Israel BSF grant 92-00106 and by a Wolfson research award administered by the Israeli Academy of Sciences, as well as a Sloan Foundation grant. This work was supported in part by National Science Foundation and DARPA under grant CCR-9627819, and by USA-Israel BSF grant 92-00106.     

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.

     

$C^\infty$ regularity of the free boundary for a two-dimensional optimal compliance problem

We study the regularizing effect of perimeter penalties for a problem of optimal compliance in two dimensions. In particular, we consider minimizers of

Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs

Twenty years ago, Ajtai et al. and, independently, Leighton discovered that the crossing number of any graph with v vertices and e > 4v edges is at least ce³/v², where c > 0 is an absolute constant. This result, known as the "Crossing Lemma," has found many important applications in discrete and computational geometry. It is tight up to a multiplicative constant. Here we improve the best known value of the constant by showing that the result holds with c > 1024/31827 > 0.032. The proof has two new ingredients, interesting in their own right. We show that (1) if a graph can be drawn in the plane so that every edge crosses at most three others, then its number of edges cannot exceed 5.5(v-2); and (2) the crossing number of any graph is at least Both bounds are tight up to an additive constant (the latter one in the range ).     

Standing waves with a critical frequency for nonlinear Schrödinger equations,II

For elliptic equations of the form , where the potential V satisfies , we develop a new variational approach to construct localized bound state solutions concentrating at an isolated component of the local minimum of V where the minimum value of V can be positive or zero. These solutions give rise to standing wave solutions having a critical frequency for the corresponding nonlinear Schrödinger equations. Our method allows a fairly general class of nonlinearity f(u) including ones without any growth restrictions at large.Received: 5 July 2002, Accepted: 24 October 2002, Published online: 14 February 2003The research of the first author was supported by Grant No. 1999-2-102-003-5 from the Interdisciplinary Research Program of the KOSEF.