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.     

Improved lower bounds for the online bin stretching problem

We use game theory techniques to automatically compute improved lower bounds on the competitive ratio for the bin stretching problem. Using these techniques, we improve the best lower bound for this problem to 19/14. We explain the technique and show that it can be generalized to compute lower bounds for any online or semi-online packing or scheduling problem.     

A note on a variant of the online open end bin packing problem

We study the minimum variant of the online open end bin packing problem. Items are presented one by one, and an item can be packed into a bin while the resulting total size of items excluding the minimum size item of the bin will be below 1. We design an improved online algorithm whose asymptotic competitive ratio does not exceed 1.180952381, and we prove a new lower bound of 1.1666666 on the asymptotic competitive ratio of any online algorithm.     

Online strip packing with modifiable boxes

In the strip packing problem the goal is to pack a set of rectangles into a vertical strip so as to minimize the total height of the strip needed. We consider a modified version of the strip packing problem. In this version it is allowed to change the form of the rectangles by lengthening them, keeping the area fixed. We introduce online algorithms to solve this modified problem. Moreover a lower bound is presented, as well.     

Analysis of queueing policies in QoS switches

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the “best effort” approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst-case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.     

Worst-case analysis of a dynamic channel assignment strategy

We consider the problem of channel assignment in cellular networks with arbitrary reuse distance. We show upper and lower bounds for the competitive ratio of a previously proposed and widely studied version of dynamic channel assignment, which we refer to as the greedy algorithm. We study two versions of this algorithm: one that performs reassignment of channels, and one that never reassigns channels to calls. For reuse distance 2, we show tight bounds on the competitive ratio of both versions of the algorithm. For reuse distance 3, we show non-trivial lower bounds for both versions of the algorithm.     

Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case

We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not included in the class of monotone Boolean functions. For the particular case of symmetric functions our bounds are matching and we exactly characterize the best possible competitiveness achievable by a deterministic algorithm. Our upper bound is obtained by a simple polynomial time algorithm.     

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     

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.     

Analysis of upper bounds for the Pallet Loading Problem

This paper is concerned with upper bounds for the well-known Pallet Loading Problem (PLP), which is the problem of packing identical boxes into a rectangular pallet so as to maximize the number of boxes fitted. After giving a comprehensive review of the known upper bounds in the literature, we conduct a detailed analysis to determine which bounds dominate which others. The result is a ranking of the bounds in a partial order. It turns out that two of the bounds dominate all others: a bound due to Nelissen and a bound obtained from the linear programming relaxation of a set packing formulation. Experiments show that the latter is almost always optimal and can be computed quickly.     

On minimum k-modal partitions of permutations

Partitioning a permutation into a minimum number of monotone subsequences is -hard. We extend this complexity result to minimum partitioning into k-modal subsequences; here unimodal is the special case k=1. Based on a network flow interpretation we formulate both, the monotone and the k-modal version, as mixed integer programs. This is the first proposal to obtain provably optimal partitions of permutations. LP rounding gives a 2-approximation for minimum monotone partitions and a (k+1)-approximation for minimum (upper) k-modal partitions. For the online problem, in which the permutation becomes known to an algorithm sequentially, we derive a logarithmic lower bound on the competitive ratio for minimum monotone partitions, and we analyze two (bin packing) online algorithms. These immediately apply to online cocoloring of permutation graphs.     

The variable-width strip packing problem

Here, we focus on a generalized version of the strip packing problem; namely we have several open-end strips with different widths, and we wish to pack rectangular items into these strips without overlapping such that we have to minimize either the makespan (i.e. the top of the topmost item), or the total area used. We investigate the online variant of the problem, where the items are arriving one-by-one, and we have to make irrevocable decisions on their packing. A similar framework was proposed by Ye and Mei (On-line scheduling of parallel jobs in heterogeneous multiple clusters. Frontiers in algorithmics and algorithmic aspects in information and management, Springer, Berlin, pp 139–148, 2012. https://doi.org/10.1007/978-3-642-29700-7_13) for scheduling models, and they studied the absolute competitive ratio of their algorithm. Our contribution is to define a new objective function and several algorithms by combining so-called shelf algorithms with techniques taken from the areas of the variable-sized bin packing problem and scheduling. We analyzed the asymptotic competitive ratio of our algorithms.

     

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.     

Finding maxmin allocations in cooperative and competitive fair division

We define a subgradient algorithm to compute the maxmin value of a completely divisible good in both competitive and cooperative strategic contexts. The algorithm relies on the construction of upper and lower bounds for the optimal value which are based on the convexity properties of the range of utility vectors associated to all possible divisions of the good. The upper bound always converges to the optimal value. Moreover, if two additional hypotheses hold: that the preferences of the players are mutually absolutely continuous, and that there always exists relative disagreement among the players, then also the lower bound converges, and the algorithm finds an approximately optimal allocation.     

Estimates of the rate of convergence of a dynamic reconstruction algorithm under incomplete information about the phase state

In this paper, we study a dynamic reconstruction algorithm which reconstructs the unknown unbounded input and all unobservable phase coordinates from the results of measurements of part of the coordinates. An upper and a lower bound for the accuracy of the reconstruction is obtained. We determine the class of inputs for which the upper bound is uniform. We give a condition for optimally matching the algorithm parameters, ensuring the highest order of the upper bound and equating the orders of the upper and lower bounds. Thus, we establish the sharpness of the upper bound.     

Resource augmented semi-online bounded space bin packing

We study on-line bounded space bin-packing in the resource augmentation model of competitive analysis. In this model, the on-line bounded space packing algorithm has to pack a list L of items with sizes in (0, 1], into a minimum number of bins of size b, b≥1. A bounded space algorithm has the property that it only has a constant number of active bins available to accept items at any point during processing. The performance of the algorithm is measured by comparing the produced packing with an optimal offline packing of the list L into bins of size 1. The competitive ratio then becomes a function of the on-line bin size b. Csirik and Woeginger studied this problem in [J. Csirik, G.J. Woeginger, Resource augmentation for online bounded space bin packing, Journal of Algorithms 44(2) (2002) 308-320] and proved that no on-line bounded space algorithm can perform better than a certain bound ρ(b) in the worst case. We relax the on-line condition by allowing a complete repacking within the active bins, and show that the same lower bound holds for this problem as well, and repacking may only allow one to obtain the exact best possible competitive ratio of ρ(b) having a constant number of active bins, instead of achieving this bound in the limit. We design a polynomial time on-line algorithm that uses three active bins and achieves the exact best possible competitive ratio ρ(b) for the given problem.     

Competitive online algorithms for resource allocation over the positive semidefinite cone

We consider a new and general online resource allocation problem, where the goal is to maximize a function of a positive semidefinite (PSD) matrix with a scalar budget constraint. The problem data arrives online, and the algorithm needs to make an irrevocable decision at each step. Of particular interest are classic experiment design problems in the online setting, with the algorithm deciding whether to allocate budget to each experiment as new experiments become available sequentially. We analyze two greedy primal-dual algorithms and provide bounds on their competitive ratios. Our analysis relies on a smooth surrogate of the objective function that needs to satisfy a new diminishing returns (PSD-DR) property (that its gradient is order-reversing with respect to the PSD cone). Using the representation for monotone maps on the PSD cone given by Löwner’s theorem, we obtain a convex parametrization of the family of functions satisfying PSD-DR. We then formulate a convex optimization problem to directly optimize our competitive ratio bound over this set. This design problem can be solved offline before the data start arriving. The online algorithm that uses the designed smoothing is tailored to the given cost function, and enjoys a competitive ratio at least as good as our optimized bound. We provide examples of computing the smooth surrogate for D-optimal and A-optimal experiment design, and demonstrate the performance of the custom-designed algorithm.     

A sequential elimination algorithm for computing bounds on the clique number of a graph

We consider the problem of determining the size of a maximum clique in a graph, also known as the clique number. Given any method that computes an upper bound on the clique number of a graph, we present a sequential elimination algorithm which is guaranteed to improve upon that upper bound. Computational experiments on DIMACS instances show that, on average, this algorithm can reduce the gap between the upper bound and the clique number by about 60%. We also show how to use this sequential elimination algorithm to improve the computation of lower bounds on the clique number of a graph.     

Computing closely matching upper and lower bounds on textile nesting problems

We consider an industrial cutting problem in textile manufacturing and report on algorithms for computing cutting images and lower bounds on waste for this problem. For the upper bounds we use greedy strategies based on hodographs and global optimization based on simulated annealing. For the lower bounds we use branch-and-bound methods for computing optimal solutions of placement subproblems that determine the performance of the overall subproblem. The upper bounds are computed in less than an hour on a common-day workstation and are competitive in quality with results obtained by human nesters. The lower bounds take a few hours to compute and are within 0.4% of the upper bound for certain types of clothing (e.g., for pants).