Probabilistic analysis of the next fit decreasing algorithm for bin-packing

We use a simple deterministic inequality to simplify and strengthen previous results on the probabilistic analysis of Next Fit Decreasing for Bin-Packing.     

A linear time bin-packing algorithm

In the bin-packing problem a list L of numbers in (0, 1] is to be packed into unit capacity bins. Let $\text{L}{}^1$ denote the minimum number of bins required. We present a linear time bin-packing algorithm for the off-line version of this problem. The algorithm uses at most $\text{4}\text{3}\text{L1 + 2}$ bins.     

A new proof of the Garsia-Wachs algorithm

A new proof of correctness for the Garsia-Wachs algorithm is presented. Like the well-known Hu-Tucker algorithm, the Garsia-Wachs algorithm constructs minimum cost binary trees in O(n log n) time. The new proof has a simpler structure and is free of the difficult inductions of the original.     

A stochastic analysis of the NFD bin-packing algorithm

We consider the Next-Fit-Decreasing (NFD) algorithm for the one-dimensional bin packing problem. The input consists of n pieces of i.i.d. sizes. Bounds on the first two moments of the number of bins used in the packing are established for arbitrary size distributions. These bounds are asymptotically tight. For the uniform distribution we also exhibit numerical results and examine their dependence on the support of the size distribution.     

A new proof for the correctness of the F5 algorithm

In 2002, Faugère presented the famous F5 algorithm for computing Gröbner basis where two criteria, syzygy criterion and rewritten criterion, were proposed to avoid redundant computations. He proved the correctness of the syzygy criterion, but the proof for the correctness of the rewritten criterion was left. Since then, F5 has been studied extensively. Some proofs for the correctness of F5 were proposed, but these proofs are valid only under some extra assumptions. In this paper, we give a proof for the correctness of F5B, an equivalent version of F5 in Buchberger’s style. The proof is valid for both homogeneous and non-homogeneous polynomial systems. Since this proof does not depend on the computing order of the S-pairs, any strategy of selecting S-pairs could be used in F5B or F5. Furthermore, we propose a natural and non-incremental variant of F5 where two revised criteria can be used to remove almost all redundant S-pairs.     

A new lower bound for the non-oriented two-dimensional bin-packing problem

We propose a new scheme for computing lower bounds for the non-oriented bin-packing problem when the bin is a square. It leads to bounds that theoretically dominate previous results. Computational experiments show that the bounds are tight. We also discuss the case where the bin is not a square.     

A new exact method for the two-dimensional bin-packing problem with fixed orientation

We propose a new exact method for the well-known two-dimensional bin-packing problem. It is based on an iterative decomposition of the set of items into two disjoint subsets. We tested the efficiency of our method against benchmarks of the literature. Computational experiments confirm the efficiency of our method.     

Tighter bounds of the First Fit algorithm for the bin-packing problem

In this paper, we present improved bounds for the First Fit algorithm for the bin-packing problem. We prove for all lists L, and the absolute performance ratio of FF is at most .     

A new area-maximization proof for the circle

Conclusion  Finally, we compare the trianglesT _i with the isosceles triangles which would be obtained by slicing the circle by the same procedure. Since they all have the same short base length and the same angle opposite the base, the isosceles triangles composing the circle have more area than the trianglesT _i. Because the latter triangles cover all ofR ₁ (perhaps even with overlap and/or extension beyondR ₁), we see that the area of the quarter-circle is greater than that ofR ₁, and thus the circle's entire area is greater than that of our original regionR.     

A new proof of the formula for the Bernoulli numbers

This note presents a new proof of Gould's famous formula for the Bernoulli numbers.     

A new existence proof for Steiner quadruple systems

A Steiner quadruple system of order v is an ordered pair ${(X, \mathcal{B})}$ , where X is a set of cardinality v, and ${\mathcal{B}}$ is a set of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in a unique block. Such designs exist if and only if ${v \equiv 2,4\, (\bmod\, 6)}$ . The first and second proofs of this result were given by Hanani in 1960 and in 1963, respectively. All the existing proofs are rather cumbersome, even though simplified proofs have been given by Lenz in 1985 and by Hartman in 1994. To study Steiner quadruple systems, Hanani introduced the concept of H-designs in 1963. The purpose of this paper is to provide an alternative existence proof for Steiner quadruple systems via H-designs of type 2 ⁿ . In 1990, Mills showed that for n > 3, n ≠ 5, an H-design of type g ⁿ exists if and only if ng is even and g(n ? 1)(n ? 2) is divisible by 3, where the main context is the complicated existence proof for H-designs of type 2 ⁿ . However, Mill’s proof was based on the existence result of Steiner quadruple systems. In this paper, by using the theory of candelabra systems and H-frames, we give a new existence proof for H-designs of type 2 ⁿ independent of the existence result of Steiner quadruple systems. As a consequence, we also provide a new existence proof for Steiner quadruple systems.     

A new proof of the rigidity problem

In this short note we give a new proof of the boundary rigidity problem in a Euclidean setting proved by Croke. Our method is based on the differentiability of Busemann functions and the characteristic of Euclidean metric on Riemannian manifolds without conjugate points.

     

A new proof of the Amitsur-Levitski identity

We give a simple proof of the Amitsur-Levitzki identity by analysing the powers of matrices with “differential 1-forms” as entries. Using the fact that 2-forms are central the identity is seen to follow from the Cayley-Hamilton theorem.     

A new proof of the Caffarelli-Kohn-Nirenberg theorem

Here we give a self-contained new proof of the partial regularity theorems for solutions of incompressible Navier-Stokes equations in three spatial dimensions. These results were originally due to Scheffer and Caffarelli, Kohn, and Nirenberg. Our proof is much more direct and simpler. © 1998 John Wiley & Sons, Inc.     

A new proof for the conditions of Novikov and Kazamaki

This paper provides a novel proof for the sufficiency of certain well-known criteria that guarantee the martingale property of a continuous, nonnegative local martingale. More precisely, it is shown that generalizations of Novikov’s condition and Kazamaki’s criterion follow directly from the existence of Föllmer’s measure. This approach allows to extend well-known criteria of martingality from strictly positive to only nonnegative, continuous local martingales.     

A new proof of the Abhyankar-Moh-Suzuki theorem

We give a new proof of the famous result that any two embeddings of the affine lineA ¹ inA ² are equivalent by an automorphism ofA ². We also prove that iff(X,Y) is a polynomial overC with one place at infinity, then for every C,f– also has one place at infinity. The proof uses basic results about algebraic surfaces.