A goal-driven approach to the 2D bin packing and variable-sized bin packing problems

In this paper, we examine the two-dimensional variable-sized bin packing problem (2DVSBPP), where the task is to pack all given rectangles into bins of various sizes such that the total area of the used bins is minimized. We partition the search space of the 2DVSBPP into sets and impose an order on the sets, and then use a goal-driven approach to take advantage of the special structure of this partitioned solution space. Since the 2DVSBPP is a generalization of the two-dimensional bin packing problem (2DBPP), our approach can be adapted to the 2DBPP with minimal changes. Computational experiments on the standard benchmark data for both the 2DVSBPP and 2DBPP shows that our approach is more effective than existing approaches in literature.     

Partition of Triples of Order 6k+5 into 6k+3 Optimal Packings and One Packing of Size 8k+4

A (2,3)-packing on X is a pair (X,), where is a set of 3-subsets (called blocks) of X, such that any pair of distinct points from X occurs together in at most one block. For a (6k+5)-set X, an optimal partition of triples (denoted by OPT(6k+5)) is a set of 6k+3 optimal (2,3)-packings and a (2,3)-packing of size 8k+4 on X. Etzion conjectured that there exists an OPT(6k+5) for any positive integer k. In this paper, we construct such a system for any k≥1. This complete solution is based on the known existence results of S(3,4,v)s by Hanani and that of special S(3,{4,6},6m)s by Mills. Partitionable candelabra systems also play an important role together with an OPT(11) and a holey OPT(11). Research supported by Natural Science Foundation of Universities of Jiangsu Province under Grant 05KJB110111     

A Note on a Packing Problem in Transitive Tournaments

Let TT_n be a transitive tournament on n vertices. We show that for any directed acyclic graph G of order n and of size not greater than two directed graphs isomorphic to G are arc disjoint subgraphs of TT_n. Moreover, this bound is generally the best possible. The research partially supported by KBN grant 2 P03A 016 18     

Perfect simulation and moment properties for the Matérn type III process

In a seminal work, Bertil Matérn introduced several types of processes for modeling repulsive point processes. In this paper an algorithm is presented for the perfect simulation of the Matérn III process within a bounded window in R^d${\mathbb{R}}^d$, fully accounting for edge effects. A simple upper bound on the mean time needed to generate each point is computed when interaction between points is characterized by balls of fixed radius R$R$. This method is then generalized to handle interactions resulting from use of random grains about each point. This includes the case of random radii as a special case. In each case, the perfect simulation method is shown to be provably fast, making it a useful tool for analysis of such processes.     

Heuristics for container loading of furniture

We consider a container loading problem that occurs at a typical furniture manufacturer. Each furniture item has an associated profit. Given container dimensions and a set of furniture items, the problem is to determine a subset of items with maximal profit sum that is loadable in the container. In the studied company, the problem arises hundreds of times daily during transport planning. Instances may contain more than one hundred different items with irregular shapes. To solve this complex problem we apply a set of heuristics successively that each solve one part of the problem. Large items are combined in specific structures to ensure proper protection of the items during transportation and to simplify the problem. The solutions generated by the heuristic has an average loading utilization of 91.3% for the most general instances with average running times around 100 seconds.     

Synthese und Kristallstrukturen von heteronuklearen AgI/FeII‐Koordinationspolymeren: (Me3PhN)2[Ag2Fe(SCN)6], (Me3PhN)6[Ag6Fe3(ECN)18] (E = S,Se) und (Me3PhN)4[Ag2Fe(SCN)8]

The reaction of AgSCN with (Me₃PhN)₃[Fe(NCS)₆] in DMF yields two‐dimensional polymeric, heteronuclear complexes (Me₃PhN)₂[Ag₂Fe(SCN)₆] ( 1 ) and (Me₃PhN)₆[Ag₆Fe₃(SCN)₁₈] · CH₂Cl₂·DMF ( 2a ) with bridging SCN^? ligands, whereas additional (Me₃PhN)(SCN) leads to (Me₃PhN)₄[Ag₂Fe(SCN)₈] ( 3 ) with a one‐dimensional structure. The selenocyanato complex 2b , homologous to 2a , could also be prepared. Single crystal X‐ray structure determinations show, that the Ag⁺ ions in 1 and 2a are coordinated tetrahedrally by four S atoms, in 3 by one N and three S atoms of the bridging SCN^? ligands; six N atoms of the SCN^? or SeCN^? ligands bind to Fe²⁺ in an octahedral arrangement.     

The max-flow min-cut property of two-dimensional affine convex geometries

In a matroid, (X,e) is a rooted circuit if X is a set not containing element e and X∪{e} is a circuit. We call X a broken circuit of e. A broken circuit clutter is the collection of broken circuits of a fixed element. Seymour [The matroids with the max-flow min-cut property, J. Combinatorial Theory B 23 (1977) 189-222] proved that a broken circuit clutter of a binary matroid has the max-flow min-cut property if and only if it does not contain a minor isomorphic to Q₆. We shall present an analogue of this result in affine convex geometries. Precisely, we shall show that a broken circuit clutter of an element e in a convex geometry arising from two-dimensional point configuration has the max-flow min-cut property if and only if the configuration has no subset forming a ‘Pentagon’ configuration with center e.Firstly we introduce the notion of closed set systems. This leads to a common generalization of rooted circuits both of matroids and convex geometries (antimatroids). We further study some properties of affine convex geometries and their broken circuit clutters.     

Asymptotic order of quantization for Cantor distributions in terms of Euler characteristic, Hausdorff and Packing measure

For homogeneous one-dimensional Cantor sets, which are not necessarily self-similar, we show under some restrictions that the Euler exponent equals the quantization dimension of the uniform distribution on these Cantor sets. Moreover for a special sub-class of these sets we present a linkage between the Hausdorff and the Packing measure of these sets and the high-rate asymptotics of the quantization error.     

On set systems with a threshold property

For n,k and t such that 1<t<k<n, a set F of subsets of [n] has the (k,t)-threshold property if every k-subset of [n] contains at least t sets from F and every (k-1)-subset of [n] contains less than t sets from F. The minimal number of sets in a set system with this property is denoted by m(n,k,t). In this paper we determine m(n,4,3)exactly for n sufficiently large, and we show that m(n,k,2) is asymptotically equal to the generalized Turán number T_k-1(n,k,2).     

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2+?, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs.