An <Emphasis Type="Italic">L</Emphasis>-approach for packing (<Emphasis Type="Italic">ℓ</Emphasis>, <Emphasis Type="Italic">w</Emphasis>)-rectangles into rectangular and <Emphasis Type="Italic">L</Emphasis>-shaped pieces

This paper presents an approach using a recursive algorithm for packing (?, w)-rectangles into larger rectangular and L-shaped pieces. Such a problem has actual applications for non-guillotine cutting and pallet/container loading. Our motivation for developing the L-approach is based on the fact that it can solve difficult pallet loading instances. Indeed, it is able to solve all testing problems (more than 20 000 representatives of infinite equivalence classes of the literature), including the 18 hard instances unresolved by other heuristics. We conjecture that the L-approach always finds optimum packings of (?, w)-rectangles into rectangular pieces. Moreover, the approach may also be useful when dealing with cutting and packing problems involving L-shaped pieces.     

A simple and effective recursive procedure for the manufacturer's pallet loading problem

In this paper we present a simple and effective heuristic to solve the problem of packing the maximum number of rectangles of sizes (l,w) and (w,l) into a larger rectangle (L,W) without overlapping. This problem appears in the loading of identical boxes on pallets, namely the manufacturer's pallet loading (MPL), as well as in package design and truck or rail car loading. Although apparently easy to be optimally solved, the MPL is claimed to be NP-complete and several authors have proposed approximate methods to deal with it. The procedure described in the present paper can be seen as a refinement of Bischoff and Dowsland's heuristic and can easily be implemented on a microcomputer. Using moderate computational resources, the procedure was able to find the optimal solution of 99.9% of more than 20?000 examples analysed.     

Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

We consider the m-Cycle Cover Problem of covering a complete undirected graph by m vertex-nonadjacent cycles of extremal total edge weight. The so-called TSP approach to the construction of an approximation algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the Euclidean Max m-Cycle Cover Problem with deterministic instances (edge weights) in a multidimensional Euclidean space and the Random Min m-Cycle Cover Problem with random instances UNI(0,1) are analyzed. It is shown that both algorithms have time complexity O(n ³) and are asymptotically optimal for the number of covering cycles m = o(n) and \(m \leqslant \frac{{n^{1/3} }}{{\ln n}}\), respectively.     

A vehicle routing problem with multi-trips and time windows for circular items

This article presents a vehicle routing problem with time windows, multiple trips, a limited number of vehicles and loading constraints for circular objects. This is a real problem experienced by a home delivery service company. A linear model is proposed to handle small problems and a two-step heuristic method to solve real size instances: the first step builds an initial solution through the modification of the Solomon I1 sequential insertion heuristic, and the second step improves the initial solution through the Tabu search algorithm proposed; in both steps, the problems related to circle packing with different sizes and bin packing are solved jointly with the use of heuristics. Finally, the computing results for two different sets of instances are presented.     

A note on an <Emphasis Type="Italic">L</Emphasis>-approach for solving the manufacturer's pallet loading problem

An L-approach for packing (l,?w)-rectangles into an (L,?W)-rectangle was introduced in an earlier work by Lins, Lins and Morabito. They conjecture that the L-approach is exact and point out its runtime requirements as the main drawback. In this note it is shown that, by simply using a different data structure, the runtime is considerably reduced in spite of larger (but affordable) memory requirements. This reduction is important for practical purposes since it makes the algorithm much more acceptable for supporting actual decisions in pallet loading. Intensive numerical experiments showing the efficiency and effectiveness of the algorithm are presented.     

Nonmatricial version of the Arveson-Wittstock extension principle,and its generalization

We consider the algebra ? = ?(H) of bounded operators in a Hilbert space H, ?-bimodules, and morphisms of these bimodules into the algebra ?(L ? H), where L is a Hilbert space. We study the problem of extension of a morphism defined on a sub-?-bimodule Y ? Z to Z. This problem is solved for Ruan bimodules.     

Removable singularities of solutions of linear uniformly elliptic second order equations

Let L be a uniformly elliptic linear second order differential operator in divergence form with bounded measurable real coefficients in a bounded domain G ? ?ⁿ (n ? 2). We define classes of continuous functions in G that contain generalized solutions of the equation L? = 0 and have the property that the compact sets removable for such solutions in these classes can be completely described in terms of Hausdorff measures.     

Greedy algorithms for packing unequal circles into a rectangular container

In this paper, we study the problem of packing unequal circles into a two-dimensional rectangular container. We solve this problem by proposing two greedy algorithms. The first algorithm, denoted by B1.0, selects the next circle to place according to the maximum-hole degree rule, that is inspired from human activity in packing. The second algorithm, denoted by B1.5, improves B1.0 with a self-look-ahead search strategy. The comparisons with the published methods on several instances taken from the literature show the good performance of our approach.     

Approach regions for the square root of the Poisson kernel and boundary functions in certain Orlicz spaces

If the Poisson integral of the unit disc is replaced by its square root, it is known that normalized Poisson integrals of L ^p and weak L ^p boundary functions converge along approach regions wider than the ordinary nontangential cones, as proved by Rönning and the author, respectively. In this paper we characterize the approach regions for boundary functions in two general classes of Orlicz spaces. The first of these classes contains spaces L _Φ having the property L ^∞ ? L _Φ L ^p , 1 ? p > ∞. The second contains spaces L _Φ that resemble L ^p spaces.     

Method of sentinels for packing items within arbitrary convex regions

A new method is introduced for packing items in convex regions of the Euclidian n-dimensional space. By means of this approach the packing problem becomes a global finite-dimensional continuous optimization problem. The strategy is based on the new concept of sentinels. Sentinels sets are finite subsets of the items to be packed such that, when two items are superposed, at least one sentinel of one item is in the interior of the other. Minimal sets of sentinels are found in simple two-dimensional cases. Numerical experiments and pictures showing the potentiality of the new technique are presented.     

A unified approach to the weighted Grtzsch and Nitsche problems for mappings of finite distortion

This note deals with the existence and uniqueness of a minimiser of the following Grtzsch-type problem inf f ∈F∫∫_(Q_1)φ(K(z,f))λ(x)dxdyunder some mild conditions,where F denotes the set of all homeomorphims f with finite linear distortion K(z,f)between two rectangles Q_1 and Q_2 taking vertices into vertices,φ is a positive,increasing and convex function,and λ is a positive weight function.A similar problem of Nitsche-type,which concerns the minimiser of some weighted functional for mappings between two annuli,is also discussed.As by-products,our discussion gives a unified approach to some known results in the literature concerning the weighted Grtzsch and Nitsche problems.     

A mapping method in inverse Sturm-Liouville problems with singular potentials

In the space L ₂[0, π], the Sturm-Liouville operator L _D(y) = ?y″ + q(x)y with the Dirichlet boundary conditions y(0) = y(π) = 0 is analyzed. The potential q is assumed to be singular; namely, q = σ′, where σ ∈ L ₂[0, π], i.e., q ∈ W ₂ ^?1 [0, π]. The inverse problem of reconstructing the function σ from the spectrum of the operator L _D is solved in the subspace of odd real functions σ(π/2 ? x) = ?σ(π/2 + x). The existence and uniqueness of a solution to this inverse problem is proved. A method is proposed that allows one to solve this problem numerically.     

On the complexity of the gradient of a rational function

The Baur-Strassen method implies L(?f) ? 4L(f), where L(f) is the complexity of computing a rational function f by arithmetic circuits, and ?f is the gradient of f. We show that L(? f) ? 3L(f) + n, where n is the number of variables in f. In addition, the depth of a circuit for the gradient is estimated.     

On intersections of Sylow 2-subgroups in automorphism groups of finite simple groups of exceptional Lie type

We consider the problem of interpolation of finite sets of numerical data bounded in L _p -norms (1 ≤ p < ∞) by smooth functions that are defined in an n-dimensional Euclidean ball of radius R and vanish on the boundary of the ball. Under some constraints on the location of interpolation nodes, we obtain two-sided estimates with a correct dependence on R for the L _p -norms of the Laplace operators of the best interpolants.     

Squares and their centers

We study the relationship between the size of two sets B, S ? R², when B contains either the whole boundary or the four vertices of a square with axes-parallel sides and center in every point of S. Size refers to cardinality, Hausdorff dimension, packing dimension, or upper or lower box dimension. Perhaps surprisingly, the results vary depending on the notion of size under consideration. For example, we construct a compact set B of Hausdorff dimension 1 which contains the boundary of an axes-parallel square with center in every point in [0, 1]², prove that such a B must have packing and lower box dimension at least 7/4, and show by example that this is sharp. For more general sets of centers, the answers for packing and box counting dimensions also differ. These problems are inspired by the analogous problems for circles that were investigated by Bourgain, Marstrand and Wolff, among others.     

On DP-coloring of graphs and multigraphs

While solving a question on the list coloring of planar graphs, Dvo?ák and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph G reduces the problem of finding a coloring of G from a given list L to the problem of finding a “large” independent set in the auxiliary graph H(G,L) with vertex set {(v, c): v ∈ V (G) and c ∈ L(v)}. It is similar to the old reduction by Plesnevi? and Vizing of the k-coloring problem to the problem of finding an independent set of size |V(G)| in the Cartesian product G□K _k, but DP-coloring seems more promising and useful than the Plesnevi?–Vizing reduction. Some properties of the DP-chromatic number χ _DP (G) resemble the properties of the list chromatic number χ _l (G) but some differ quite a lot. It is always the case that χ _DP (G) ≥ χ _l (G). The goal of this note is to introduce DP-colorings for multigraphs and to prove for them an analog of the result of Borodin and Erd?s–Rubin–Taylor characterizing the multigraphs that do not admit DP-colorings from some DP-degree-lists. This characterization yields an analog of Gallai’s Theorem on the minimum number of edges in n-vertex graphs critical with respect to DP-coloring.     

Global Well-posedness of the Stochastic Generalized Kuramoto-Sivashinsky Equation with Multiplicative Noise

Global well-posedness of the initial-boundary value problem for the stochastic generalized Kuramoto- Sivashinsky equation in a bounded domain D with a multiplicative noise is studied. It is shown that under suitable sufficient conditions, for any initial data u₀ ∈ L₂(D × Ω), this problem has a unique global solution u in the space L₂(Ω, C([0, T], L₂(D))) for any T >0, and the solution map u₀ ? u is Lipschitz continuous.     

Note edge-colourings of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n,n</Emphasis></Subscript> with no long two-coloured cycles

Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K _n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K _n,n with n colours having all two-coloured cycles of length ≤ 2q ², for integers n in a set of density 1 ? 3/(q ? 1). One consequence is that L(n, K _n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n ? 4.     

Kirchberger-type theorems for separation by convex domains

We say that a convex set K in ? ^d strictly separates the set A from the set B if A ? int(K) and B ? cl K = ø. The well-known Theorem of Kirchberger states the following. If A and B are finite sets in ? ^d with the property that for every T ? A?B of cardinality at most d + 2, there is a half space strictly separating T ? A and T ? B, then there is a half space strictly separating A and B. In short, we say that the strict separation number of the family of half spaces in ? ^d is d + 2.In this note we investigate the problem of strict separation of two finite sets by the family of positive homothetic (resp., similar) copies of a closed, convex set. We prove Kirchberger-type theorems for the family of positive homothets of planar convex sets and for the family of homothets of certain polyhedral sets. Moreover, we provide examples that show that, for certain convex sets, the family of positive homothets (resp., the family of similar copies) has a large strict separation number, in some cases, infinity. Finally, we examine how our results translate to the setting of non-strict separation.     

The Cauchy problem for operators with injective symbol in the Lebesgue space <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript> in a domain

Let D be a bounded domain in ? ⁿ (n ≥ 2) with infinitely smooth boundary ?D. We give some necessary and sufficient conditions for the Cauchy problem to be solvable in the Lebesgue space L ²(D) in D for an arbitrary differential operator A having an injective principal symbol. Furthermore, using bases with double orthogonality, we construct Carleman’s formula that restores a (vector-)function in L ²(D) from the Cauchy data given on a relatively open connected set Γ ? ?D and the values Au in D whenever the data belong to L ²(Γ) and L ²(D) respectively.