Solving of second order nonlinear PDE problems by using artificial controls with controlled error

In this paper, we find the approximate solution of a second order nonlinear partial differential equation on a simple connected region inR ². We transfer this problem to a new problem of second order nonlinear partial differential equation on a rectangle. Then, we transformed the later one to an equivalent optimization problem. Then we consider the optimization problem as a distributed parameter system with artificial controls. Finally, by using the theory of measure, we obtain the approximate solution of the original problem. In this paper also the global error inL ₁ is controlled.     

Many L-Shaped Polyominoes Have Odd Rectangular Packings

A polyomino is called odd if it can tile a rectangle using an odd number of copies. We give a very general family of odd polyominoes. Specifically, consider an L-shaped polyomino, i.e., a rectangle that has a rectangular piece removed from one corner. For some of these polyominoes, two copies tile a rectangle, called a basic rectangle. We prove that such a polyomino is odd if its basic rectangle has relatively prime side lengths. This general family encompasses several previously known families of odd polyominoes, as well as many individual examples. We prove a stronger result for a narrower family of polyominoes. Let L _n denote the polyomino formed by removing a 1 ×  (n?2) corner from a 2 ×  (n?1) rectangle. We show that when n is odd, L _n tiles all rectangles both of whose sides are at least 8n ³, and whose area is a multiple of n. If we only allow L _n to be rotated, but not reflected, then the same is true, provided that both sides of the rectangle are at least 16n ⁴. We also give several isolated examples of odd polyominoes.     

Rectilinear line segment intersection,layered segment trees,and dynamization

The aim of the present paper is to provide an efficient solution to the following problem: “Given a family of n rectilinear line segments in two-space report all intersections in the family with a query consisting of an arbitrary rectilinear line segment.” We provide an algorithm which takes O(nlog₂n) preprocessing time, o(nlog₂n) space and O(log₂n + k) query time, where k is the number of reported intersections. This solution serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest. Second it yields, by way of recent dynamization techniques, a solution to the on-line version of the above problem, that is the operations INSERT and DELETE and QUERY with a line segment are allowed. Third it also yields a new nonscanning solution to the batched version of the above problem. Finally we apply these techniques to the problem obtained by replacing “line segment” by “rectangle” in the above problem, giving an efficient solution in this case also.     

An algorithm for the difference between set covers

A set cover for a set S is a collection C of special subsets whose union is S. Given covers A and B for two sets, the set-cover difference problem is to construct a new cover for the elements covered by A but not B. Applications include testing equivalence of set covers and maintaining a set cover dynamically. In this paper, we solve the set-cover difference problem by defining a difference operation A-B, which turns out to be a pseudocomplement on a distributive lattice. We give an algorithm for constructing this difference, and show how to implement the algorithm for two examples with applications in computer science: face covers on a hypercube, and rectangle covers on a grid. We derive an upper bound on the time complexity of the algorithm, and give upper and lower bounds on complexity for face covers and rectangle covers.     

On the maximum empty rectangle problem

Given a rectangle A and a set S of n points in A, we consider the problem, called the maximum empty rectangle problem, of finding a maximum area rectangle that is fully contained in A and does not contain any point of S in its interior. An O(n²) time algorithm is presented. Furthermore, it is shown that if the points of S are drawn randomly and independently from A, the problem can be solved in O(n(log n)²) expected time.     

On some properties of generalized solutions of the wave equation in the classes L p and W p 1 for p ≥ 1

For each p ≥ 1, in closed analytic form, we establish the existence of a unique generalized solution in L _p of the mixed problem for the wave equation in the rectangle [0 ≤ x ≤ 1] × [0 ≤ t ≤ T] with zero initial conditions and with boundary conditions of the first kind, one of which is homogeneous. Next, we derive necessary conditions for this solution to belong to W _p ¹ . We present examples showing that these necessary conditions are not sufficient for any p ≥ 1.     

An improved algorithm for the rectangle enclosure problem

Given a set of n rectangles in the plane, with sides parallel to the coordinate axes, the rectangle enclosure problem consists of finding all q pairs of rectangles such that one rectangle of the pair encloses the other. In this note we present an alternative algorithm to the one by Vaishnavi and Wood; while both techniques have worst-case running time O(nlog²n + q), ours uses optimal storage O(n) rather than O(nlog²n) of Vaishnavi and Wood. Our algorithm works entirely in-place and uses very conventional data structures.     

Rectangles as sums of squares

In this paper we examine generalisations of the following problem posed by Laczkovich: Given an n×m rectangle with n and m integers, it can be written as a disjoint union of squares; what is the smallest number of squares that can be used? He also asked the corresponding higher dimensional analogue. For the two dimensional case Kenyon proved a tight logarithmic bound but left open the higher dimensional case. Using completely different methods we prove good upper and lower bounds for this case as well as some other variants.     

On a quasi-reversibility regularization method for a Cauchy problem of the Helmholtz equation

In this paper, we consider the Cauchy problem for the Helmholtz equation in a rectangle, where the Cauchy data is given for y=0 and boundary data are for x=0 and x=π. The solution is sought in the interval 0<y≤1. A quasi-reversibility method is applied to formulate regularized solutions which are stably convergent to the exact one with explicit error estimates.     

Strip generation algorithms for constrained two-dimensional two-staged cutting problems

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate of length L and width W, as to maximize the sum of the profits of the pieces to be cut. Each piece type i, i = 1, …, n, is characterized by a length l_i, a width w_i, a profit (or weight) c_i and an upper demand value b_i. The upper demand value is the maximum number of pieces of type i which can be cut on rectangle (L, W). In this paper, we study the two-staged fixed orientation C_TDC, noted FC_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two guillotine cuts, and each piece has a fixed orientation. We solve the FC_2TDC problem using several approximate algorithms, that are mainly based upon a strip generation procedure. We evaluate the performance of these algorithms on instances extracted from the literature.     

Some extensions of the Laplace problem

Let ?₁(a,b) be a regular lattice with the fundamental cell a rectangle with sides a,b, let ?₂(a,b,?) be a regular lattice with the fundamental cell a parallelogram with sides a,b and angle ? and let ?₃(a,b,c) be a regular lattice with the fundamental cell \(C_{0}^{( 3) }\) as in Fig. 7. In this paper we compute the probability that a random rectangle r of constant side l,m intersects a side of the lattice. In particular when the rectangle r becomes a segment of length l, (m=0) we obtain the Laplace probability.     

L1 cheapest paths in “Fjord Scenery”

We show a simple proof of the existence of a path on the “border of water and rocks” based on combinatorial induction procedure and we present an algorithm for computing L₁ shortest path in “Fjord Scenery”. The proposed algorithm is a version of the Dijkstra technique adapted to a rectangle map with a square network. A few pre-processing modifications of the algorithm following from the combinatorial procedure are included. The validity of this approach is shown by numerical calculations for an example.     

On the Minimum Sum Coloring of P 4-Sparse Graphs

In this paper, we study the minimum sum coloring (MSC) problem on P ₄-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P ₄-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P ₄-sparse graphs.     

The sign matrix and the separation of matrix eigenvalues

The sign matrices uniquely associated with the matrices (M ? ζ_jI)², where ζ_j are the corners of a rectangle oriented at π/4 to the axes of a Cartesian coordinate system, may be used to compute the number of eigenvalues of the arbitrarily chosen matrix M which lie within the rectangle, and to determine the left and right invariant subspaces of M associated with these eigenvalues. This paper is concerned with the proof of this statement, and with the details of the computation of the required sign matrices.     

On the convergence of the Dirichlet grid problem with a singularity for a singularly perturbed convection–diffusion equation

The Dirichlet problem for a singulary perturbed convection–diffusion equation in a rectangle when a discontinuity at the flow exit the first derivative of the boundary condition gives rise to an inner layer for the solution. On piecewise-uniform Shishkin grids that condense near regular and characteristic layers, the solution obtained using the classical five-point difference scheme with a directed difference is shown to converge with respect to the small parameter to solve the original problem in the grid norm L _∞ ^h almost with the first order. This theoretical result is confirmed via numerical analysis.     

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.).     

The number of additional variables required for the integer programming formulation

It is known that a minimization problem having a finite feasible region with k elements can be formulated as an integer programming problem by introducing at most [log₂k] additional integer variables. In this note, we show that this bound is best possible in the sense that some minimization problem actually requires [log₂k] additional variables.     

Two-dimensional cargo overbooking models

This paper introduces two-dimensional (weight and volume) overbooking problems arising mainly in the cargo revenue management, and compares them with one-dimensional problems. It considers capacity spoilage and cargo offloading costs, and minimizes their sum. For one-dimensional problems, it shows that the optimal overbooking limit does not change with the magnitude of the booking requests. In two-dimensional problems, the overbooking limit is replaced by a curve. The curve, along with the volume and weight axes, encircles the acceptance region. The booking requests are accepted if they fall within this region. We present Curve (Cab) and Rectangle (Rab) models. The boundary of the acceptance region in the Cab (resp. Rab) model is a curve (resp. rectangle). The optimal curve for the Cab model is shown to be unique and continuous. Moreover, it can be obtained by solving a series of simple equations. Finding the optimal rectangle for the Rab model is more challenging, so we propose an approximate rectangle. The approximate rectangle is a limiting solution in the sense that it converges to the optimal rectangle as the booking requests increase. The approximate rectangle is numerically shown to yield costs that are very close to the optimal costs.     

Solving a combinatorial problem with network flows

In this paper we present an algorithm based on network flow techniques which provides a solution for a combinatorial problem. Then, in order to provide all the solutions of this problem, we make use of an algorithm that given the bipartite graphG=(V ₁ ∪V ₂,E, w) outputs the enumeration of all bipartite matchings of given cardinalityv and costc.     

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.