Exact and approximation algorithms for a soft rectangle packing problem

We consider the problem of finding an arrangement of rectangles with given areas that minimizes the total length of all inner and outer border lines. We present a polynomial time approximation algorithm and derive an upper bound estimation on its approximation ratio. Furthermore, we give a formulation of the problem as mixed-integer nonlinear program and show that it can be approximatively reformulated as linear mixed-integer program. On a test set of problem instances, we compare our approximation algorithm with another one from the literature. Using a standard numerical mixed-integer linear solver, we show that adding the solutions from the approximation algorithm as advanced starter helps to reduce the overall solution time for proven global optimality, or gives better primal and dual bounds if a certain time-limit is reached before.     

Convergence of optimal stochastic bin packing

Consider independent identically distributed random variables (X_i) valued in [0,1]. Let B(n) be the optimal (minimum) number of unit size bins needed to pack n items of size X₁, X₂,…,X_n. We prove that there exists a numerical constant C such that for t > 0,

$\text{Pr(∣B(n)?E(B(n))∣>t}\text{n}\text{)≤ C exp(? t).}$

The constant C does not depend on the distribution of X.     

Exact packing dimension in random recursive constructions

We explore the exact packing dimension of certain random recursive constructions. In case of polynomial decay at 0 of the distribution function of random variable X, associated with the construction, we prove that it does not exist, and in case of exponential decay it is t|log|logt||, where is the fractal dimension of the limit set and 1/ is the rate of exponential decay.Research supported by the Department of Mathematics and Statistics (Mathematics) at University of Jyväskylä.Mathematics Subject Classification (2000):Primary 28A78, 28A80; Secondary 60D05, 60J80     

A reduction approach for solving the rectangle packing area minimization problem

In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.     

Construction of optimal supersaturated designs by the packing method

A supersaturated design is essentially a factorial design with the equal occurrence of levels property and no fully aliased factors in which the number of main effects is greater than the number of runs. It has received much recent interest because of its potential in factor screening experiments. A packing design is an important object in combinatorial design theory. In this paper, a strong link between the two apparently unrelated kinds of designs is shown. Several criteria for comparing supersaturated designs are proposed, their properties and connections with other existing criteria are discussed. A combinatorial approach, called the packing method, for constructing optimal supersaturated designs is presented, and properties of the resulting designs are also investigated. Comparisons between the new designs and other existing designs are given, which show that our construction method and the newly constructed designs have good properties.     

Golay code and random packing

Summary A random sequential packing by Hamming distance is applied to study Golay code. The probability of getting Golay code is estimated by computer simulation. A histogram of number of packed points is given to show the existence of several remarkable clusters. The Institute of Statistical Mathematics     

An optimal packing problem for satellites in geosynchronous orbit

This paper describes a physical system for which an optimization method is needed. First, the physical nature of the problem is described, and then a mathematical model is developed. The purpose of this paper is to encourage mathematical and control systems analysts to tackle this problem.     

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.We present a complete solution to this problem: For every bin size b1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.     

On packing of rectangles in a rectangle

It is known that ${\sum }_{i=1}^{\infty }1∕\left(i(i+1)\right)=1$. In 1968, Meir and Moser (1968) asked for finding the smallest $?$ such that all the rectangles of sizes $1∕i\times 1∕(i+1)$, $i\in \{1,2,\dots \}$, can be packed into a square or a rectangle of area $1+?$. First we show that in Paulhus (1997), the key lemma, as a statement, in the proof of the smallest published upper bound of the minimum area is false, then we prove a different new upper bound. We show that $?\le 1.26?10^{?9}$ if the rectangles are packed into a square and $?\le 6.878?10^{?10}$ if the rectangles are packed into a rectangle.     

有向Kirkman填充设计的谱

§ 1　IntroductionLet X be a set of v points.A packing(directed packing) of X is a collection of subsets(ordered subsets) of X(called blocks) such that any pair(ordered pair) of distinct pointsfrom X occur together in atmostone block in the collection.A packing(directed packing)is called resolvable ifitsblock setadmitsa partition into parallel classes,each parallel classbeing a partition of the pointset X.A Kirkman triple system KTS(v) is a collection Tof3 -subsets of X(triples) suchthat …     

Several classes of optimal ternary cyclic codes with minimal distance four

In this paper, by analyzing the solutions of certain equations over ${\mathbb{F}}_{3^m}$, we present four classes of optimal ternary cyclic codes with parameters $[3^m-1,3^m-1-2m,4]$. It is shown that some recent work on this class of optimal ternary cyclic codes are special cases of our results.     

On a posterior evaluation of a simple greedy method for set packing

We consider an approach for ex post evaluation of approximate solutions obtained by a well known simple greedy method for set packing. A performance bound is derived that is a function of the highest average reward per item over subsets as well as the number of allocated subsets and ground items. This a posterior bound can enable much revelation of optimality when the solution is near optimal. One of the advantages of the ex post analysis is that it does not require computing the optimal solution to the LP relaxation. The ex post bound will not be guaranteed to reveal substantial levels of optimality for all problem instances but can be a useful tool that is complementary to other traditional methods for ex post evaluation for the set packing problem.     

Further combinatorial constructions for optimal frequency-hopping sequences

Frequency-hopping multiple-access (FHMA) spread-spectrum communication systems employing multiple frequency shift keying as data modulation technique were investigated by Fuji-Hara, Miao and Mishima [R. Fuji-Hara, Y. Miao, M. Mishima, Optimal frequency hopping sequences: A combinatorial approach, IEEE Trans. Inform. Theory 50 (2004) 2408-2420] from a combinatorial approach, where a correspondence between frequency-hopping (FH) sequences and partition-type cyclic difference packings was established, and several combinatorial constructions were provided for FHMA systems with a single optimal FH sequence. In this paper, by means of this correspondence, we describe more combinatorial constructions for such optimal FH sequences. As a consequence, more new infinite series of optimal FH sequences are obtained.     

Constrained retarded nonlinear optimal control problems in Banach state space

Necessary conditions are proved for the optimal control of solutions of ordinary and retarded differential equations in a Banach state space, with mixed and pure state restrictions. The treatment includes the possibility of point targets. A generalization of earlier results for finite-dimensional or Hilbert state spaces is obtained.     

About a new class of matroid-inducing packing families

Let T be a family of graphs. A T-packing of a graph G is a subgraph of G, components of which are isomorphic to members of T. We are concerned with families T, such that in every graph G, the subsets of vertices that can be saturated by some T-packing form a collection of independent sets of a matroid. The main purpose of this paper is to introduce a new class of families with this property.     

Analysis for the end of block wasted space

The problem examined in this report is the calculation of the average wasted space at the end of the block when variable length records are inserted in the file. Previous efforts are based in approximations. Here, a detailed analysis based on Markov chains gives the exact solution. A framework is presented which shows the relations between the previous approaches. The proposed model includes the previous models as special limiting cases. Simulation results close to the analytic results are also presented.This research was sponsored partially by the National Science Foundation under the grants DCR-86-16833, IRI-8719458 and IRI-8958546 and by the Air Force Office of Scientific Research under grant AFOSR-89-0303.     

A proof of a general maximum principle for optimal controls via a multiplier rule on metric space

A unified proof is given of the maximum principle for optimal control with various kinds of constraints by using a multiplier rule on metric spaces.     

Constructions for optimal cyclic ternary constant-weight codes of weight four and distance six

A cyclic ${(n,d,w)}_q$ code is a $q$-ary cyclic code of length $n$, minimum Hamming distance $d$ and weight $w$. In this paper, we investigate cyclic ${(n,6,4)}_3$ codes. A new upper bound on $C{A}_3(n,6,4)$, the largest possible number of codewords in a cyclic ${(n,6,4)}_3$ code, is given. Two new constructions for optimal cyclic ${(n,6,4)}_3$ codes based on cyclic $(n,4,1)$ difference packings are presented. As a consequence, the exact value of $C{A}_3(n,6,4)$ is determined for any positive integer $n\equiv 0,6,18(mod24)$. We also obtain some other infinite classes of optimal cyclic ${(n,6,4)}_3$ codes.     

Application of the method of multipliers to state space constrained optimal control problems with discrete time

The paper deals with convergence conditions of multiplier algorithms for solving optimal control problems with discrete time suggested by J. Bjbvonek in some earlier papers. In this approach the original state space constrained problem is converted into a control-constrained problem by introducing an additional control variable and an equality constraint which is taken into consideration by a multiplier method. Convergence conditions for the multiplier Iteration of global and local nature are given for exact and inexact solution of the subproblems.