共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
Stephen G. Walker 《Linear and Multilinear Algebra》2013,61(7):755-760
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. 相似文献
5.
Zilla Sinuany-Stern 《Annals of Operations Research》2014,221(1):357-376
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. 相似文献
6.
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. 相似文献
7.
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. 相似文献
8.
《European Journal of Operational Research》2020,280(2):730-740
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. 相似文献
9.
Stephanie Vance 《Advances in Mathematics》2011,227(5):2144
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. 相似文献
10.
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. 相似文献
11.
图的最大亏格、支配数和围长 总被引:3,自引:0,他引:3
一个连图G的最大亏格γM(G)=(β(G)-ξ(G)/2,其中β(G)=E(G)-V(G 1是G的圈秩,ξ(G)是G的Betti亏数,本文利用G的支配数和围长给出了G的Betti亏数ξ(G)的一个上界,从而也给出了最大亏格γ(M(G)的一个下界,而且它是可达的,对于某些图类,该下界比黄元秋(2000)所给下界更好。 相似文献
12.
I.E. Shparlinski 《Linear algebra and its applications》2010,432(1):155-160
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. 相似文献
13.
14.
Robert Gallant Bert L. Hartnell Douglas F. Rall 《Discrete Applied Mathematics》2010,158(12):1357-1113
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. 相似文献
15.
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. 相似文献
16.
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. 相似文献
17.
M.A.Marco A. Boschetti 《Discrete Applied Mathematics》2004,140(1-3):241-258
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. 相似文献
18.
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 相似文献
19.
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. 相似文献
20.
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. 相似文献