New upper bounds for online strip packing

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.     

A note on online hypercube packing

In this paper, we study an online multi-dimensional bin packing problem where all items are hypercubes. Hypercubes of different size arrive one by one, and we are asked to pack each of them without knowledge of the next pieces so that the number of bins used is minimized. Based on the techniques from one dimensional bin packing and specifically the algorithm Super Harmonic by Seiden (J ACM 49:640–671, 2002), we extend the framework for online bin packing problems developed by Seiden to the hypercube packing problem. To the best of our knowledge, this is the first paper to apply a version of Super Harmonic (and not of the Improved Harmonic algorithm) for online square packing, although the Super Harmonic has been already known before. Note that the best previous result was obtained by Epstein and van Stee (Acta Inform 41(9):595–606, 2005b) using an instance of Improved Harmonic. In this paper we show that Super Harmonic is more powerful than Improve Harmonic for online hypercube packing, and then we obtain better upper bounds on asymptotic competitive ratios. More precisely, we get an upper bound of 2.1187 for square packing and an upper bound of 2.6161 for cube packing, which improve upon the previous upper bounds 2.24437 and 2.9421 (Epstein and van Stee in Acta Inform 41(9):595–606, 2005b) for the two problems, respectively.     

New lower bounds for the three-dimensional orthogonal bin packing problem

In this paper, we consider the three-dimensional orthogonal bin packing problem, which is a generalization of the well-known bin packing problem. We present new lower bounds for the problem from a combinatorial point of view and demonstrate that they theoretically dominate all previous results from the literature. The comparison is also done concerning asymptotic worst-case performance ratios. The new lower bounds can be more efficiently computed in polynomial time. In addition, we study the non-oriented model, which allows items to be rotated.     

Bounds for the second largest eigenvalue of a transition matrix

We find an upper bound, with general form, for the second largest eigenvalue of a transition matrix; special cases of which have previously been proposed as upper bounds and others which are new improvements.     

Quadratic model for allocating operational budget in public and nonprofit organizations

We develop a quadratic model for allocating operational budgets in public and nonprofit organizations. The allocations for each organizational unit have lower and upper bounds. The objective function is to minimize the weighted sum of the quadratic deviations of each allocation from its bounds. The optimal allocations are mostly around the midpoint between the bounds. A simple algorithm is presented to derive the solution. The new quadratic model is compared to the familiar linear model for budget allocation, which almost always, provides extreme allocations on the bounds: for some units on the upper bound, while for others, on the lower bound. We perform sensitivity analyses, and resolve special cases of the model with closed form solution. Moreover, we show various properties of the quadratic budget allocation model and prove that its fairness index is higher than that of the linear model. The model, with its variants, was actually used for allocating budgets in various university setups; some examples are presented here.     

Complementary column generation and bounding approaches for set partitioning formulations

We present a complementary column generation feature that produces tight upper bounds, thereby enhancing heuristic and exact column generation approaches for (minimization) set partitioning formulations that possess dense column structures. We also introduce a duality-based lower bound that prompts a useful termination criterion, which can be utilized to mitigate the tailing-off effect induced by column generation approaches. Computations are presented for the one-dimensional bin packing problem and a joint vehicle assembly-routing problem.     

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.     

Recursive lower and dual upper bounds for Bermudan-style options

Although Bermudan options are routinely priced by simulation and least-squares methods using lower and dual upper bounds, the latter are hardly optimized. In this paper, we optimize recursive upper bounds, which are more tractable than the original/nonrecursive ones, and derive two new results: (1) An upper bound based on (a martingale that depends on) stopping times is independent of the next-stage exercise decision and hence cannot be optimized. Instead, we optimize the recursive lower bound, and use its optimal recursive policy to evaluate the upper bound as well. (2) Less time-intensive upper bounds that are based on a continuation-value function only need this function in the continuation region, where this continuation value is less nonlinear and easier to fit (than in the entire support). In the numerical exercise, both upper bounds improve over state-of-the-art methods (including standard least-squares and pathwise optimization). Specifically, the very small gap between the lower and the upper bounds derived in (1) implies the recursive policy and the associated martingale are near optimal, so that these two specific lower/upper bounds are hard to improve, yet the upper bound is tighter than the lower bound.     

Improved sphere packing lower bounds from Hurwitz lattices

In this paper we prove an asymptotic lower bound for the sphere packing density in dimensions divisible by four. This asymptotic lower bound improves on previous asymptotic bounds by a constant factor and improves not just lower bounds for the sphere packing density, but also for the lattice sphere packing density and, in fact, the Hurwitz lattice sphere packing density.     

Fulfilling orders for steel plates from existing inventory

This paper investigates the steel plate order fulfilment problem from existing inventory, which is a generalization of one-dimensional cutting and packing problems. Semi-processed inventory of steel slabs can be burned, heated, rolled, and sheared to meet customer order requirements. This problem is an integral part of the day-to-day operations of steel plate manufacturing. A 0–1 integer programming formulation is presented and two heuristics, based on single-order formulations, are presented to quickly generate lower and upper bounds. The bounds are improved using Lagrangian relaxation and subgradient optimization, producing average optimality gaps of 2.12% on 17 real-world data sets. The upper bound improvements represent actual savings over the current solution method of 1.94%, or an average of about $230?000 over a 3-week period. An economic interpretation of the Lagrange multipliers is also discussed and shown to be useful for handling rush orders.     

图的最大亏格、支配数和围长

一个连图G的最大亏格γM（G）=（β（G）-ξ（G）/2,其中β（G）=E（G）-V（G 1是G的圈秩,ξ（G）是G的Betti亏数,本文利用G的支配数和围长给出了G的Betti亏数ξ（G）的一个上界,从而也给出了最大亏格γ（M（G）的一个下界,而且它是可达的,对于某些图类,该下界比黄元秋（2000）所给下界更好。     

Some counting questions for matrices with restricted entries

We obtain upper bounds for the number of arbitrary and symmetric matrices with integer entries in a given box (in an arbitrary location) and a given determinant. We then apply these bounds to estimate the number of matrices in such boxes which have an integer eigenvalues. Finally, we outline some open questions.     

Limited packings in graphs

We define a k-limited packing in a graph, which generalizes a 2-packing in a graph, and give several bounds on the size of a k-limited packing. One such bound involves the domination number of the graph, and here we show all trees attaining the bound can be built via a simple sequence of operations. We consider graphs where every maximal 2-limited packing is a maximum 2-limited packing, and characterize their structure in a number of cases.     

The minimum size instance of a Pallet Loading Problem equivalence class

The Pallet Loading Problem (PLP) maximizes the number of identical rectangular boxes placed within a rectangular pallet. Boxes may be rotated 90° so long as they are packed with edges parallel to the pallet’s edges, i.e., in an orthogonal packing. This paper defines the Minimum Size Instance (MSI) of an equivalence class of PLP, and shows that every class has one and only one MSI. We develop bounds on the dimensions of box and pallet for the MSI of any class. Applying our new bounds on MSI dimensions, we present an algorithm for MSI generation and use it to enumerate all 3,080,730 equivalence classes with an area ratio (pallet area divided by box area) smaller than 101 boxes. Previous work only provides bounds on the ratio of box dimensions and only considers a subset of all classes presented here.     

Analysis of transient queues with semidefinite optimization

We derive upper bounds on the tail distribution of the transient waiting time in the GI/GI/1 queue, given a truncated sequence of the moments of the service time and that of the interarrival time. Our upper bound is given as the objective value of the optimal solution to a semidefinite program (SDP) and can be calculated numerically by solving the SDP. We also derive the upper bounds in closed form for the case when only the first two moments of the service time and those of the interarrival time are given. The upper bounds in closed form are constructed by formulating the dual problem associated with the SDP. Specifically, we obtain the objective value of a feasible solution of the dual problem in closed from, which turns out to be the upper bound that we derive. In addition, we study bounds on the maximum waiting time in the first busy period.     

New lower bounds for the three-dimensional finite bin packing problem

The three-dimensional finite bin packing problem (3BP) consists of determining the minimum number of large identical three-dimensional rectangular boxes, bins, that are required for allocating without overlapping a given set of three-dimensional rectangular items. The items are allocated into a bin with their edges always parallel or orthogonal to the bin edges. The problem is strongly NP-hard and finds many practical applications. We propose new lower bounds for the problem where the items have a fixed orientation and then we extend these bounds to the more general problem where for each item the subset of rotations by 90° allowed is specified. The proposed lower bounds have been evaluated on different test problems derived from the literature. Computational results show the effectiveness of the new lower bounds.     

New classes of fast lower bounds for bin packing problems

The bin packing problem is one of the classical NP-hard optimization problems. In this paper, we present a simple generic approach for obtaining new fast lower bounds, based on dual feasible functions. Worst-case analysis as well as computational results show that one of our classes clearly outperforms the previous best “economical” lower bound for the bin packing problem by Martello and Toth, which can be understood as a special case. In particular, we prove an asymptotic worst-case performance of 3/4 for a bound that can be computed in linear time for items sorted by size. In addition, our approach provides a general framework for establishing new bounds. Received: August 11, 1998 / Accepted: February 1, 2001?Published online September 17, 2001     

Upper and Lower Bounds for the Lengths of Steiner Trees in 3-Space

We present a method of determining upper and lower bounds for the length of a Steiner minimal tree in 3-space whose topology is a given full Steiner topology, or a degenerate form of that full Steiner topology. The bounds are tight, in the sense that they are exactly satisfied for some configurations. This represents the first nontrivial lower bound to appear in the literature. The bounds are developed by first studying properties of Simpson lines in both two and three dimensional space, and then introducing a class of easily constructed trees, called midpoint trees, which provide the upper and lower bounds. These bounds can be constructed in quadratic time. Finally, we discuss strategies for improving the lower bound.Supported by a grant from the Australia Research Council.     

Bounding the spectrum of large Hermitian matrices

Estimating upper bounds of the spectrum of large Hermitian matrices has long been a problem with both theoretical and practical significance. Algorithms that can compute tight upper bounds with minimum computational cost will have applications in a variety of areas. We present a practical algorithm that exploits k-step Lanczos iteration with a safeguard step. The k is generally very small, say 5-8, regardless of the large dimension of the matrices. This makes the Lanczos iteration economical. The safeguard step can be realized with marginal cost by utilizing the theoretical bounds developed in this paper. The bounds establish the theoretical validity of a previous bound estimator that has been successfully used in various applications. Moreover, we improve the bound estimator which can now provide tighter upper bounds with negligible additional cost.