An approximation scheme for the two-stage,two-dimensional knapsack problem

We present an approximation scheme for the two-dimensional version of the knapsack problem which requires packing a maximum-area set of rectangles in a unit square bin, with the further restrictions that packing must be orthogonal without rotations and done in two stages. Achieving a solution which is close to the optimum modulo a small additive constant can be done by taking wide inspiration from an existing asymptotic approximation scheme for two-stage two-dimensional bin packing. On the other hand, getting rid of the additive constant to achieve a canonical approximation scheme appears to be widely nontrivial.     

The two-dimensional cutting stock problem revisited

In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k=2 stages cannot guarantee any bounded asymptotic performance ratio. k=3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k=4 stages yield asymptotic performance ratios arbitrarily close to 1.Steve Seiden died in a tragic accident on June 11, 2002. This paper resulted from a number of email discussions between the authors in spring 2002.     

Exact algorithms for the two-dimensional strip packing problem with and without rotations

We propose exact algorithms for the two-dimensional strip packing problem (2SP) with and without 90° rotations. We first focus on the perfect packing problem (PP), which is a special case of 2SP, wherein all given rectangles are required to be packed without wasted space, and design branch-and-bound algorithms introducing several branching rules and bounding operations. A combination of these rules yields an algorithm that is especially efficient for feasible instances of PP. We then propose several methods of applying the PP algorithms to 2SP. Our algorithms succeed in efficiently solving benchmark instances of PP with up to 500 rectangles and those of 2SP with up to 200 rectangles. They are often faster than existing exact algorithms specially tailored for problems without rotations.     

Tilings,packings, coverings,and the approximation of functions

A packing (resp. covering) ? of a normed space X consisting of unit balls is called completely saturated (resp. completely reduced) if no finite set of its members can be replaced by a more numerous (resp. less numerous) set of unit balls of X without losing the packing property (resp. covering property) of ?. We show that a normed space X admits completely saturated packings with disjoint closed unit balls as well as completely reduced coverings with open unit balls, provided that there exists a tiling of X with unit balls. Completely reduced coverings by open balls are of interest in the context of an approximation theory for continuous real‐valued functions that rests on so‐called controllable coverings of compact metric spaces. The close relation between controllable coverings and completely reduced coverings allows an extension of the approximation theory to non‐compact spaces. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Mixed Laguerre–Legendre Spectral Method for Incompressible Flow in an Infinite Strip

This paper concerns the mixed Laguerre–Legendre spectral approximation and its application to numerical simulation of incompressible flow in an infinite strip. Some approximation results in weighted Sobolev spaces are given. A Laguerre–Legendre spectral scheme for the stream function form of Navier–Stokes equations is constructed. The stability and the convergence of the proposed scheme are proved. The numerical experiments show the high accuracy of this method. The main techniques used in this paper are also applicable to other nonlinear partial differential equations in an infinite strip.     

Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.     

Resource augmentation in two-dimensional packing with orthogonal rotations

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90^° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems.     

A block-based layer building approach for the 2D guillotine strip packing problem

We examine the 2D strip packing problems with guillotine-cut constraint, where the objective is to pack all rectangles into a strip with fixed width and minimize the total height of the strip. We combine three most successful ideas for the orthogonal rectangular packing problems into a single coherent algorithm: (1) packing a block of rectangles instead of a single rectangle in each step; (2) dividing the strip into layers and pack layer by layer; and (3) unrolling and repacking the top portion of the solutions where usually wasted space occurs. Computational experiments on benchmark test sets suggest that our approach rivals existing approaches.     

Quadratic Hermite–Padé Approximation to the Exponential Function: A Riemann–Hilbert Approach

We investigate the asymptotic behavior of the polynomials p, q, r of degrees n in type I Hermite–Padé approximation to the exponential function, defined by p(z)e^-z + q(z) + r(z) e^z = O(z³ⁿ⁺²) as z 0. These polynomials are characterized by a Riemann–Hilbert problem for a 3 × 3 matrix valued function. We use the Deift–Zhou steepest descent method for Riemann–Hilbert problems to obtain strong uniform asymptotics for the scaled polynomials p(3nz), q(3nz), and r(3nz) in every domain in the complex plane. An important role is played by a three-sheeted Riemann surface and certain measures and functions derived from it. Our work complements the recent results of Herbert Stahl.     

Bin packing with general cost structures

Following the work of Anily et?al., we consider a variant of bin packing called bin packing with general cost structures (GCBP) and design an asymptotic fully polynomial time approximation scheme (AFPTAS) for this problem. In the classic bin packing problem, a set of one-dimensional items is to be assigned to subsets of total size at most 1, that is, to be packed into unit sized bins. However, in GCBP, the cost of a bin is not 1 as in classic bin packing, but it is a non-decreasing and concave function of the number of items packed in it, where the cost of an empty bin is zero. The construction of the AFPTAS requires novel techniques for dealing with small items, which are developed in this work. In addition, we develop a fast approximation algorithm which acts identically for all non-decreasing and concave functions, and has an asymptotic approximation ratio of 1.5 for all functions simultaneously.     

Prediction of multivariate time series by autoregressive model fitting

Suppose the stationary r-dimensional multivariate time series {y_t} is generated by an infinite autoregression. For lead times h≥1, the linear prediction of y_t+h based on y_t, y_t−1,… is considered using an autoregressive model of finite order k fitted to a realization of length T. Assuming that k → ∞ (at some rate) as T → ∞, the consistency and asymptotic normality of the estimated autoregressive coefficients are derived, and an asymptotic approximation to the mean square prediction error based on this autoregressive model fitting approach is obtained. The asymptotic effect of estimating autoregressive parameters is found to inflate the minimum mean square prediction error by a factor of (1 + kr/T).     

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

We present NC-approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar graphs. We also define the concept of λ-precision unit disk graphs and show that for such graphs the approximation schemes have a better time versus performance trade-off than the approximation schemes for arbitrary unit disk graphs. Moreover, compared to unit disk graphs, we show that for λ-precision unit disk graphs many more graph problems have efficient approximation schemes.Our NC-approximation schemes can also be extended to obtain efficient NC-approximation schemes for several PSPACE-hard problems on unit disk graphs specified using a restricted version of the hierarchical specification language of Bentley, Ottmann, and Widmayer. The approximation schemes for hierarchically specified unit disk graphs presented in this paper are among the first approximation schemes in the literature for natural PSPACE-hard optimization problems.     

Two-Parametric Compound Binomial Approximations

We consider two-parametric compound binomial approximation of the generalized Poisson binomial distribution. We show that the accuracy of approximation essentially depends on the symmetry or shifting of distributions and construct asymptotic expansions. For the proofs, we combine the properties of norms with the results for convolutions of symmetric and shifted distributions. In the lattice case, we use the characteristic function method. In the case of almost binomial approximation, we apply Steins method.__________Published in Lietuvos Matematikos Rinkinys, Vol. 44, No. 4, pp. 443–466, October–December, 2004.     

May Leonard systems

In this paper we study the asymptotic behavior of a class of n-dimensional competing Lotka–Volterra systems which includes the celebrated May–Leonard examples.     

Two-dimensional packing problems: A survey

We consider problems requiring to allocate a set of rectangular items to larger rectangular standardized units by minimizing the waste. In two-dimensional bin packing problems these units are finite rectangles, and the objective is to pack all the items into the minimum number of units, while in two-dimensional strip packing problems there is a single standardized unit of given width, and the objective is to pack all the items within the minimum height. We discuss mathematical models, and survey lower bounds, classical approximation algorithms, recent heuristic and metaheuristic methods and exact enumerative approaches. The relevant special cases where the items have to be packed into rows forming levels are also discussed in detail.     

On routing in VLSI design and communication networks

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. First we propose new and realistic models for both problems. In the global routing problem in VLSI design, we are given a lattice graph and subsets of the vertex set. The goal is to generate trees spanning these vertices in the subsets to minimize a linear combination of overall wirelength (edge length) and the number of bends of trees with respect to edge capacity constraints. In the multicast routing problem in communication networks, a graph is given to represent the network, together with subsets of the vertex set. We are required to find trees to span the given subsets and the overall edge length is minimized with respect to capacity constraints. Both problems are APX-hard. We present the integer linear programming (LP) formulation of both problems and solve the LP relaxations by the fast approximation algorithms for min-max resource-sharing problems in [K. Jansen, H. Zhang, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Math. Programming, to appear, doi:10.1007/s10107-007-0106-8] (which is a generalization of the approximation algorithm proposed by Grigoriadis and Khachiyan [Coordination complexity of parallel price-directive decomposition, Math. Oper. Res. 2 (1996) 321-340]). For the global routing problem, we investigate the particular property of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally, we develop asymptotic approximation algorithms for both problems with ratios depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for the problems of minimizing the total costs (including both the edge and the bend costs) while spanning all given subsets of vertices.     

Fundamental frequency of a circular membrane with a strip of small length

A circular membrane with an arbitrarily placed internal strip of small length is concerned in this article. A two-term asymptotic expansion for the fundamental frequency of the membrane, as the length of the strip approaching to zero, is specified. Comparing it with the one [8] derived for the membrane with an internal circular core, it is found that the position of the internal constraint has more effect than the shape of the internal constraint on the fundamental frequency. The asymptotic approximation is also compared with the numerical data computed by the dual boundary element method [2] for a circular membrane of radius 1 with a radially placed internal strip of length 2c. These two sets of data are in good agreement. The relative error is less than 3 % as c is less than or equal to 0.1, for all positions of the strip. Moreover, the relative error is less than 1 % as c is less than or equal to 0.01.     

Fundamental frequency of a circular membrane with a strip of small length

A circular membrane with an arbitrarily placed internal strip of small length is concerned in this article. A two-term asymptotic expansion for the fundamental frequency of the membrane, as the length of the strip approaching to zero, is specified. Comparing it with the one [8] derived for the membrane with an internal circular core, it is found that the position of the internal constraint has more effect than the shape of the internal constraint on the fundamental frequency. The asymptotic approximation is also compared with the numerical data computed by the dual boundary element method [2] for a circular membrane of radius 1 with a radially placed internal strip of length 2c. These two sets of data are in good agreement. The relative error is less than 3 % as c is less than or equal to 0.1, for all positions of the strip. Moreover, the relative error is less than 1 % as c is less than or equal to 0.01.     

Bogolyubov averaging and normalization procedures in nonlinear mechanics. IV

In this paper, we apply the theory developed in parts I-III [Ukr. Math. Zh.,46, No. 9, 1171–1188; No. 11, 1509–1526; No. 12, 1627–1646 (1994)] to some classes of problems. We consider linear systems in zero approximation and investigate the problem of invariance of integral manifolds under perturbations. Unlike nonlinear systems, linear ones have centralized systems, which are always decomposable. Moreover, restrictions connected with the impossibility of diagonalization of the coefficient matrix in zero approximation are removed. In conclusion, we apply the method of local asymptotic decomposition to some mechanical problems.Published in Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 8, pp. 1044–1068, August, 1995.This research was partially supported by the International Science Foundation, grant No. UB2000.