Counting dissections into integral squares

A squared rectangle is a rectangle dissected into squares. Similarly a rectangled rectangle is a rectangle dissected into rectangles. The classic paper ‘The dissection of rectangles into squares’ of Brooks, Smith, Stone and Tutte described a beautiful connection between squared rectangles and harmonic functions. In this paper we count dissections of a rectangle into a set of integral squares or a set of integral rectangles. Here, some squares and rectangles may have the same size. We introduce a method involving a recurrence relation of large sized matrices to enumerate squared and rectangled rectangles of a given sized rectangle and propose the asymptotic behavior of their growth rates.     

Estimates for eigenvalues of stochastic matrices

It is well-known that the eigenvalues of stochastic matrices lie in the unit circle and at least one of them has the value one. Let {1, r 2 , ··· , r N } be the eigenvalues of stochastic matrix X of size N × N . We will present in this paper a simple necessary and sufficient condition for X such that |r j | < 1, j = 2, ··· , N . Moreover, such condition can be very quickly examined by using some search algorithms from graph theory.     

Expected wasted space of optimal simple rectangle packing

A simple packing of a collection of rectangles contained in [0,1]² is a disjoint subcollection such that each vertical line meets at most one rectangle of the packing. The wasted space of the packing is the surface of the area of the part of [0,1]² not covered by the packing. We prove that for a certain number L, for all N2, the wasted space W_N in an optimal simple packing of N independent uniformly distributed rectangles satisfiesWork partially supported by an N.S.F. grant.Mathematics Subject Classification (2000): 60D05     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Nearly magic rectangles

Magic squares have been extremely useful and popular in combinatorics and statistics. One generalization of magic squares is magic rectangles which are useful for designing experiments in statistics. A necessary and sufficient condition for the existence of magic rectangles restricts the number of rows and columns to be either both odd or both even. In this paper, we generalize magic rectangles to even by odd nearly magic rectangles. We also prove necessary and sufficient conditions for the existence of a nearly magic rectangle, and construct one for each parameter set for which they exist.     

Finding squares and rectangles in sets of points

A number of problems concerning sets of points in the plane are studied, e.g. establishing whether it contains a subset of size 4, which are the vertices of a square or rectangle. Both the problems of finding axis-parallel squares and rectangles, and arbitrarily oriented squares and rectangles are studied. Efficient algorithms are obtained for all of them. Furthermore, we investigate the generalizations tod-dimensional space, where the problem is to find hyperrectangles and hypercubes. Also, upper and lower bounds are given for combinatorial problems on the maxium number of subsets of size 4, of which the points are the vertices of a square or rectangle. Then we state an equivalence between the problem of finding rectangles, and the problem of findingK _{2, 2} subgraphs in bipartite graphs. Thus we immediately have an efficient algorithm for this graph problem.This work was partially supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). Work of the second author was also supported by the Dutch Organisation for Scientific Research (N.W.O.).     

Covering Arrays of Strength Three

A covering array of size N, degree k, order v and strength t is a k × N array with entries from a set of v symbols such that in any t × N subarray every t × 1 column occurs at least once. Covering arrays have been studied for their applications to drug screening and software testing. We present explicit constructions and give constructive upper bounds for the size of a covering array of strength three.     

Admission control with advance reservations in simple networks

In the admission control problem we are given a network and a set of connection requests, each of which is associated with a path, a time interval, a bandwidth requirement, and a weight. A feasible schedule is a set of connection requests such that at any given time, the total bandwidth requirement on every link in the network is at most 1. Our goal is to find a feasible schedule with maximum total weight.We consider the admission control problem in two simple topologies: the line and the tree. We present a 12c-approximation algorithm for the line topology, where c is the maximum number of requests on a link at some time instance. This result implies a 12c-approximation algorithm for the rectangle packing problem, where c is the maximum number of rectangles that cover simultaneously a point in the plane. We also present an O(logt)-approximation algorithm for the tree topology, where t is the size of the tree. We consider the loss minimization version of the admission control problem in which the goal is to minimize the weight of unscheduled requests. We present a c-approximation algorithm for loss minimization problem in the tree topology. This result is based on an approximation algorithm for a generalization of set cover, in which each element has a covering requirement, and each set has a covering potential. The approximation ratio of this algorithm is Δ, where Δ is the maximum number of sets that contain the same element.     

Resource augmentation in two-dimensional packing with orthogonal rotations

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90^° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems.     

Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.     

Upper Bound on the Packing Density of Regular Tetrahedra and Octahedra

Aristotle contended that (regular) tetrahedra tile space, an opinion that remained widespread until it was observed that non-overlapping tetrahedra cannot subtend a solid angle of 4π around a point if this point lies on a tetrahedron edge. From this 15th century argument, we can deduce that tetrahedra do not tile space but, more than 500 years later, we are unaware of any known non-trivial upper bound to the packing density of tetrahedra. In this article, we calculate such a bound. To this end, we show the existence, in any packing of regular tetrahedra, of a set of disjoint spheres centered on tetrahedron edges, so that each sphere is not fully covered by the packing. The bound on the amount of space that is not covered in each sphere is obtained in a recursive way by building on the solid angle argument. The argument can be readily modified to apply to other polyhedra. The resulting lower bound on the fraction of empty space in a packing of regular tetrahedra is 2.6…×10⁻²⁵ and reaches 1.4…×10⁻¹² for regular octahedra.     

Computation of the ε entropy of the space of continuous functions with the Hausdorff metric

The number K_p,q, i.e., the number of (p, q) corridors of closed domains which are convex in the vertical direction, consist of elementary squares of the integral lattice, are situated within a rectangle of the size q × p, and completely cover the side of length p of this rectangle under projection is computed. The asymptotic (K_p,q/q²)^1/p → λ, as p, q → ∞, where λ = 0.3644255… is the maximum root of the equation₁F₁(-1/2 − 1/(16λ), 1/2, 1/(4λ)) = 0,₁F₁ being the confluence hypergeometric function, is established. These results allow us to compute the ε entropy of the space of continuous functions with the Hausdorff metric. Translated from Matematicheskie Zametki, Vol. 21, No. 1, pp. 39–50, January, 1977.     

Minimal Time Functions and the Smallest Intersecting Ball Problem with Unbounded Dynamics

The smallest enclosing circle problem introduced in the nineteenth century by Sylvester asks for the circle of smallest radius enclosing a given set of finite points in the plane. An extension of this problem, called the smallest intersecting ball problem, was also considered recently: given a finite number of nonempty closed subsets of a normed space, find a ball with the smallest radius that intersects all of the sets. In this paper, we initiate the study of minimal time functions generated by unbounded dynamics and discuss their applications to further extensions of the smallest enclosing circle problem. This approach continues our effort in applying convex and nonsmooth analysis to the well-established field of facility location.     

Probabilistic analysis of a new class of strip packing algorithms

A new class of algorithms for online packing of rectangles into a strip is proposed and studied. It is proved that the expectation of the unfilled area for this class of algorithms is O(N ^2/3) in the standard (for this type of problems) probabilistic model for N random rectangles.     

Lightly mixing is closed under countable products

Given any countable familyT ₁,T ₂, … of lightly mixing transformations, we answer a question of Friedman by showing that their direct productT ₁×T ₂×… is lightly mixing. Also, if a transformation has a generating tower of lightly mixing factors then it itself is lightly mixing. Partially supported by NSF grant DMS8501519. Nowadays calledsweeping out.     

The symmetry of the partition function of some square ice models

We consider the partition function Z(N; x ₁ , …, x_N, y ₁ , …, y_N) of the square ice model with domain wall boundary conditions. We give a simple proof that Z is symmetric with respect to all its variables when the global parameter a of the model is set to the special value a = e^iπ/3 . Our proof does not use any determinant interpretation of Z and can be adapted to other situations (e.g., to some symmetric ice models).     

货物尺寸相同的2维装箱问题的等价类(英文)

在生产与储运领域,把小长方体货物（盒子）装入大长方体箱子是一项重要的工作.本文涉及的问题是:把相同尺寸（a×b×c）的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子（a×b）填装到一个2维箱子X×Y中.本文讨论当盒子尺寸（a×b包括 b×a）给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.     

Optimal grid holey packings with block size 3 and 4

The notion of a grid holey packing (GHP) was first proposed for the construction of constant composite codes. For a GHP (k, 1; n ×  g) of type [w ₁, . . . , w _g ], where , the fundamental problem is to determine the packing number N([w ₁, . . . , w _g ], 1; n ×  g), that is, the maximum number of blocks in such a GHP. In this paper we determine completely the values of N([w ₁, . . . , w _g ], 1; n ×  g) in the case of block size .