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.     

Parallel greedy algorithms for packing unequal circles into a strip or a rectangle

Given a finite set of circles of different sizes we study the strip packing problem (SPP) as well as the Knapsack Problem (KP). The SPP asks for a placement of all circles within a rectangular strip of fixed width so that the variable length of the strip is minimized. The KP requires packing of a subset of the circles in a given rectangle so that the wasted area is minimized. To solve these problems some greedy algorithms were developed which enhance the algorithms proposed by Huang et al. (J Oper Res Soc 56:539–548, 2005). Furthermore, the new greedy algorithms were parallelized using a master slave approach. The resulting parallel methods were tested using the instances introduced by Stoyan and Yaskov (Eur J Oper Res 156:590–600, 2004). Additionally, two sets of 128 instances each for the SPP and for the KP were generated and results for these new instances are also reported.     

带多重选择的最短路问题:复杂性和算法

本文提出了带出重选择的是短路问题,建立了该问题的数学模型,利用背包问题的一个变形问题－带限制选择的背包问题,证明了该问题是ＮＰ－Ｃ的,最后利用动态规则给出了一个伪多项式算法,其时间复杂性Ｏ（Ｃｈｍｎ）,其中ｈ是最大的选择重数。     

解带有二次约束非凸二次规划问题的一个分枝缩减方法

在这篇论文里,有机地把外逼近方法与分枝定界技术结合起来,提出了解带有二次约束非凸二次规划问题的一个分枝缩减方法;给出了原问题的一个新的线性规划松弛,以便确定它在超矩形上全局最优值的一个下界;利用超矩形的一个深度二级剖分方法,以及超矩形的缩减和删除技术,提高算法的收敛速度;证明了在知道原问题可行点的条件下,该算法在有限步里就可以获得原问题的一个全局最优化解,并且用一个例子说明了该算法是有效的.     

A ramsey-type bound for rectangles

It is proved that for any rectangle T and for any 2-coloring of the points of the 5-dimensional Euclidean space, one can always find a rectangle T′ congruent to T, all of whose vertices are of the same color. We also show that for any k-coloring of the k² + o(k²)-dimensional space, there is a monochromatic rectangle congruent to any given rectangle. © 1996 John Wiley & Sons, Inc.     

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.     

The KP hierarchy, branched covers, and triangulations

The KP hierarchy is a completely integrable system of quadratic, partial differential equations that generalizes the KdV hierarchy. A linear combination of Schur functions is a solution to the KP hierarchy if and only if its coefficients satisfy the Plücker relations from geometry. We give a solution to the Plücker relations involving products of variables marking contents for a partition, and thus give a new proof of a content product solution to the KP hierarchy, previously given by Orlov and Shcherbin. In our main result, we specialize this content product solution to prove that the generating series for a general class of transitive ordered factorizations in the symmetric group satisfies the KP hierarchy. These factorizations appear in geometry as encodings of branched covers, and thus by specializing our transitive factorization result, we are able to prove that the generating series for two classes of branched covers satisfies the KP hierarchy. For the first of these, the double Hurwitz series, this result has been previously given by Okounkov. The second of these, that we call the m-hypermap series, contains the double Hurwitz series polynomially, as the leading coefficient in m. The m-hypermap series also specializes further, first to the series for hypermaps and then to the series for maps, both in an orientable surface. For the latter series, we apply one of the KP equations to obtain a new and remarkably simple recurrence for triangulations in a surface of given genus, with a given number of faces. This recurrence leads to explicit asymptotics for the number of triangulations with given genus and number of faces, in recent work by Bender, Gao and Richmond.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

Enumeration of polyominoes inscribed in a rectangle

We develop a number of formulas and generating functions for the enumeration of general polyominoes inscribed in a rectangle of given size according to their area. These formulae are then used for the enumeration of lattice trees inscribed in a rectangle with minimum area plus one.     

Elliptic solutions of nonlinear integrable equations and related topics

The theory of elliptic solitons for the Kadomtsev-Petviashvili (KP) equation and the dynamics of the corresponding Calogero-Moser system is integrated. It is found that all the elliptic solutions for the KP equation manifest themselves in terms of Riemann theta functions which are associated with algebraic curves admitting a realization in the form of a covering of the initial elliptic curve with some special properties. These curves are given in the paper by explicit formulae. We further give applications of the elliptic Baker-Akhiezer function to generalized elliptic genera of manifolds and to algebraic 2-valued formal groups.Dedicated to the memory of J.-L. Verdier     

Rectangular drawings of plane graphs without designated corners

This paper addresses the problem of finding rectangular drawings of plane graphs, in which each vertex is drawn as a point, each edge is drawn as a horizontal or a vertical line segment, and the contour of each face is drawn as a rectangle. A graph is a 2–3 plane graph if it is a plane graph and each vertex has degree 3 except the vertices on the outer face which have degree 2 or 3. A necessary and sufficient condition for the existence of a rectangular drawing has been known only for the case where exactly four vertices of degree 2 on the outer face are designated as corners in a 2–3 plane graph G. In this paper we establish a necessary and sufficient condition for the existence of a rectangular drawing of G for the general case in which no vertices are designated as corners. We also give a linear-time algorithm to find a rectangular drawing of G if it exists.     

On the zeros of the Riemann zeta function of large multiplicity

We obtain a new upper bound for the number of zeros of the Riemann zeta function of a given multiplicity lying in a given rectangle of the critical strip.     

The Kadomtsev–Petviashvili (KP), MKP,and coupled KP equations for two-ion-temperature dusty plasmas

It is well known that the Korteweg–de Vires (KdV) equation can describe small but finite amplitude dust acoustic waves in a dusty plasmas. In this paper, we use the reductive perturbation method and derive a Kadomtsev–Petviashvili (KP) equation, a modified KP (MKP) equation and a coupled KP equation for unmagnetized, collisionless, cold, and two-ion-temperature dusty plasmas with N different species of dust grains. We find that if a solitary wave exist in this system, the smaller grains have larger velocities and propagate longer distances than that of larger particles. The comparisons are given between the dusty plasma composed by different dust particles and the mono-sized dusty plasma.     

KP reductions and various soliton solutions to the Fokas–Lenells equation under nonzero boundary condition

In this paper, we clarify the connection of the Fokas–Lenells (FL) equation to the Kadomtsev–Petviashvili (KP)–Toda hierarchy by using a set of bilinear equations as a bridge and confirm multidark soliton solution to the FL equation previously given by Matsuno (J. Phys. A 2012 45 (475202). We also show that the set of bilinear equations in the KP–Toda hierarchy can be generated from a single discrete KP equation via Miwa transformation. Based on this finding, we further deduce the multibreather and general rogue wave solutions to the FL equation. The dynamical behaviors and patterns for both the breather and rogue wave solutions are illustrated and analyzed.     

On the geometry of conjugacy classes in classical groups

Summary We study closures of conjugacy classes in the Lie algebras of the orthogonal and symplectic groups and determine which ones are normal varieties. Furthermore we give a complete classification of the minimal singularities which arise in this context, i.e. the singularities which occur in the open classes in the boundary of a given conjugacy class. In contrast to the results for the general linear group ([KP1], [KP2]) there are classes with non normal closure; they are branched in a class of codimension two and give rise to normal minimal singularities. The methods used are (classical) invariant theory and algebraic geometry. Supported in part by the SFB Theoretische Mathematik, University of Bonn, and by the University of Hamburg     

离散几何的两个铺砌问题

利用图论和代数的方法研究离散几何中的两个铺砌问题:1)给出1×2长方形铺砌多米诺骨牌的充分必要条件;2)对高维空间盒子的情形,给出m_1×m_2×…×m_n砖能够铺砌a_1×a_2×…×a_n盒子的一些必要条件和充要条件.     

An inverse problem for an equation of elliptic-hyperbolic type with a nonlocal boundary condition

We examine a mixed type equation with the Lavrent??ev-Bitsadze operator and an unknown right-hand side in a rectangle and study a nonlocal boundary value problem in which the values of the stream function on the lateral sides of the rectangle are equal. The solution is given as a sum of a biorthogonal series. The uniqueness criterion and stability of solutions with respect to the boundary data are established.     

Rectangle exchange transformations

We define rectangle exchange transformations analogously to interval exchange transformations. An interval exchange transformation is a mapping of the unit interval onto itself obtained by cutting the interval up into a finite number of subintervals and rearranging the pieces. A rectangle exchange transformation is a mapping of the unit square onto itself obtained by cutting the square up into a finite number of rectangular pieces and rearranging the pieces. We give a minimality condition for rectangle exchange transformations. We deal with various examples of ergodic rectangle exchange transformations. Related questions are discussed.With 2 Figures     

Soliton-like structures and the connection between the Bq and KP equations

We study the (2+1)-dimensional model proposed by Kadomtsev and Petviashvili (KP) to describe slowly varying nonlinear waves in a dispersive medium. Applying an appropriate Lie transformation and following the method introduced by Tajiri et al., the KP equation is reduced to a one-dimensional equation, that is, to a certain version of the Boussinesq equation (BqE). Then, we solve the BqE by the Hirota method, and finally we use the inverse transformation in order to obtain de KP solutions. We Analyze some remarkable properties of the solutions found in this work.     

Non-isospectral flows of noncommutative differential-difference KP equation

We present master symmetries of noncommutative differential-difference KP equation by considering Sato approach, where the field variables are defined over associative algebras. The Lie algebraic structures of generalized and master symmetries are given. They form a Virasoro Lie algebraic structure.