Tight bounds for NF-based bounded-space online bin packing algorithms

In Zheng et al. (J Comb Optim 30(2):360–369, 2015) modelled a surgery problem by the one-dimensional bin packing, and developed a semi-online algorithm to give an efficient feasible solution. In their algorithm they used a buffer to temporarily store items, having a possibility to lookahead in the list. Because of the considered practical problem they investigated the 2-parametric case, when the size of the items is at most 1 / 2. Using an NF-based online algorithm the authors proved an ACR of \(13/9 = 1.44\ldots \) for any given buffer size not less than 1. They also gave a lower bound of \(4/3=1.33\ldots \) for the bounded-space algorithms that use NF-based rules. Later, in Zhang et al. (J Comb Optim 33(2):530–542, 2017) an algorithm was given with an ACR of 1.4243,  and the authors improved the lower bound to 1.4230. In this paper we present a tight lower bound of \(h_\infty (r)\) for the r-parametric problem when the buffer capacity is 3. Since \(h_\infty (2) = 1.42312\ldots \), our result—as a special case—gives a tight bound for the algorithm-class given in 2017. To prove that the lower bound is tight, we present an NF-based online algorithm that considers the r-parametric problem, and uses a buffer with capacity of 3. We prove that this algorithm has an ACR that is equal to the lower bounds for arbitrary r.     

Online bin packing problem with buffer and bounded size revisited

In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within \((\alpha ,1/2]\) where \(0 \le \alpha < 1/2 \), and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360–369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.     

Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing

In this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d-dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side is no more than 1. These items must be packed without overlapping into d-dimensional hypercubes with unit length on each side. In d-dimensional space, any two dimensions i and j define a space P _ij . When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items, and 90^°-rotation on any plane P _ij is allowed. The objective is to minimize the total number of bins used for packing all these items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. For d-dimensional bin packing, an online algorithm with competitive ratio 4 ^d is given. Moreover, we consider d-dimensional hypercube packing, and give a 2 ^d+1-competitive algorithm. These two results are the first study on 1-space bounded multi dimensional bin packing and hypercube packing.     

On-line bin packing with restricted repacking

Semi-on-line algorithms for the bin-packing problem allow, in contrast to pure on-line algorithms, the use of certain types of additional operations for each step. Examples include repacking, reordering or lookahead before packing the items. Here we define and analyze a semi-on-line algorithm where for each step at most k items can be repacked, for some positive integer k. We prove that the upper bound for the asymptotic competitive ratio of the algorithm is a decreasing function of k, which tends to 3/2 as k goes to infinity. We also establish lower bounds for this ratio and show that the gap between upper and lower bounds is relatively small.     

Online bin packing of fragile objects with application in cellular networks

We study a specific bin packing problem which arises from the channel assignment problems in cellular networks. In cellular communications, frequency channels are some limited resource which may need to share by various users. However, in order to avoid signal interference among users, a user needs to specify to share the channel with at most how many other users, depending on the user’s application. Under this setting, the problem of minimizing the total channels used to support all users can be modeled as a specific bin packing problem as follows: Given a set of items, each with two attributes, weight and fragility. We need to pack the items into bins such that, for each bin, the sum of weight in the bin must be at most the smallest fragility of all the items packed into the bin. The goal is to minimize the total number of bins (i.e., the channels in the cellular network) used. We consider the on-line version of this problem, where items arrive one by one. The next item arrives only after the current item has been packed, and the decision cannot be changed. We show that the asymptotic competitive ratio is at least 2. We also consider the case where the ratio of maximum fragility and minimum fragility is bounded by a constant. In this case, we present a class of online algorithms with asymptotic competitive ratio at most of 1/4+3r/2, for any r>1. A preliminary version of this paper appeared in Proc. of Workshop on Internet and Network Economics (WINE’05, pp. 564–573). The research of W.-T.C. was supported in part by Hong Kong RGC grant HKU5172/03E. The research of F.Y.-L.C. was supported in part by Hong Kong RGC Grant HKU7142/03E. The research of D.Y. was supported by NSFC (10601048). The research of G.Z. was supported in part by NSFC (60573020).     

Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts

This paper presents an approach for solving a new real problem in cutting and packing. At its core is an innovative mixed integer programme model that places irregular pieces and defines guillotine cuts. The two-dimensional irregular shape bin packing problem with guillotine constraints arises in the glass cutting industry, for example, the cutting of glass for conservatories. Almost all cutting and packing problems that include guillotine cuts deal with rectangles only, where all cuts are orthogonal to the edges of the stock sheet and a maximum of two angles of rotation are permitted. The literature tackling packing problems with irregular shapes largely focuses on strip packing i.e. minimizing the length of a single fixed width stock sheet, and does not consider guillotine cuts. Hence, this problem combines the challenges of tackling the complexity of packing irregular pieces with free rotation, guaranteeing guillotine cuts that are not always orthogonal to the edges of the stock sheet, and allocating pieces to bins. To our knowledge only one other recent paper tackles this problem. We present a hybrid algorithm that is a constructive heuristic that determines the relative position of pieces in the bin and guillotine constraints via a mixed integer programme model. We investigate two approaches for allocating guillotine cuts at the same time as determining the placement of the piece, and a two phase approach that delays the allocation of cuts to provide flexibility in space usage. Finally we describe an improvement procedure that is applied to each bin before it is closed. This approach improves on the results of the only other publication on this problem, and gives competitive results for the classic rectangle bin packing problem with guillotine constraints.     

Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width

We study the problems of non-preemptively scheduling and packing malleable and parallel tasks with precedence constraints to minimize the makespan. In the scheduling variant, we allow the free choice of processors; in packing, each task must be assigned to a contiguous subset. Malleable tasks can be processed on different numbers of processors with varying processing times, while parallel tasks require a fixed number of processors. For precedence constraints of bounded width, we resolve the complexity status of the problem with any number of processors and any width bound. We present an FPTAS based on Dilworth’s decomposition theorem for the NP-hard problem variants, and exact efficient algorithms for all remaining special cases. For our positive results, we do not require the otherwise common monotonous penalty assumption on the processing times of malleable tasks, whereas our hardness results hold even when assuming this restriction. We complement our results by showing that these problems are all strongly NP-hard under precedence constraints which form a tree.     

Optimal algorithms for online time series search and one-way trading with interrelated prices

The basic models of online time series search and one-way trading are introduced by El-Yaniv et al. in Algorithmica 30(1), 101–139 (2001) where it is assumed that the prices are bounded within interval [m,M] (0<m<M). In this paper, we consider another case where every two consecutive prices are interrelated, that is, the variation range of each price depends on its preceding price. We present optimal deterministic online algorithms for the two problems, respectively. According to one conclusion in Algorithmica 30(1), 101–139 (2001), we further point out that for the case we considered, an optimal deterministic algorithm for the one-way trading problem can be regarded as an optimal randomized one for the time series search problem, and randomization is useless for the one-way trading problem.     

A tight analysis of Brown-Baker-Katseff sequences for online strip packing

We study certain adversary sequences for online strip packing which were first designed and investigated by Brown, Baker and Katseff (Acta Inform. 18:207–225) and determine the optimal competitive ratio for packing such Brown-Baker-Katseff sequences online. As a byproduct of our result, we get a new lower bound of $\rho \ge 3/2+\sqrt{33}/6 \approx 2.457$ for the competitive ratio of online strip packing.     

Constant factor approximation for the weighted partial degree bounded edge packing problem

In the partial degree bounded edge packing problem (PDBEP), the input is an undirected graph \(G=(V,E)\) with capacity \(c_v\in {\mathbb {N}}\) on each vertex v. The objective is to find a feasible subgraph \(G'=(V,E')\) maximizing \(|E'|\), where \(G'\) is said to be feasible if for each \(e=\{u,v\}\in E'\), \(\deg _{G'}(u)\le c_u\) or \(\deg _{G'}(v)\le c_v\). In the weighted version of the problem, additionally each edge \(e\in E\) has a weight w(e) and we want to find a feasible subgraph \(G'=(V,E')\) maximizing \(\sum _{e\in E'} w(e)\). The problem is already NP-hard if \(c_v = 1\) for all \(v\in V\) (Zhang in: Proceedings of the joint international conference on frontiers in algorithmics and algorithmic aspects in information and management, FAW-AAIM 2012, Beijing, China, May 14–16, pp 359–367, 2012). In this paper, we introduce a generalization of the PDBEP problem. We let the edges have weights as well as demands, and we present the first constant-factor approximation algorithms for this problem. Our results imply the first constant-factor approximation algorithm for the weighted PDBEP problem, improving the result of Aurora et al. (FAW-AAIM 2013) who presented an \(O(\log n)\)-approximation for the weighted case. We also study the weighted PDBEP problem on hypergraphs and present a constant factor approximation if the maximum degree of the hypergraph is bounded above by a constant. We study a generalization of the weighted PDBEP problem with demands where each edge additionally specifies whether it requires at least one, or both its end-points to not exceed the capacity. The objective is to pick a maximum weight subset of edges. We give a constant factor approximation for this problem. We also present a PTAS for the weighted PDBEP problem with demands on H-minor free graphs, if the demands on the edges are bounded by polynomial. We show that the PDBEP problem is APX-hard even for bipartite graphs with \(c_v = 1, \; \forall v\in V\) and having degree at most 3.     

Domination in graphs with bounded propagation: algorithms,formulations and hardness results

We introduce a hierarchy of problems between the Dominating Set problem and the Power Dominating Set (PDS) problem called the ℓ-round power dominating set (ℓ-round PDS, for short) problem. For ℓ=1, this is the Dominating Set problem, and for ℓ≥n−1, this is the PDS problem; here n denotes the number of nodes in the input graph. In PDS the goal is to find a minimum size set of nodes S that power dominates all the nodes, where a node v is power dominated if (1) v is in S or it has a neighbor in S, or (2) v has a neighbor u such that u and all of its neighbors except v are power dominated. Note that rule (1) is the same as for the Dominating Set problem, and that rule (2) is a type of propagation rule that applies iteratively. The ℓ-round PDS problem has the same set of rules as PDS, except we apply rule (2) in “parallel” in at most ℓ−1 rounds. We prove that ℓ-round PDS cannot be approximated better than 2^log1-en2^{\log^{1-\epsilon}{n}} even for ℓ=4 in general graphs. We provide a dynamic programming algorithm to solve ℓ-round PDS optimally in polynomial time on graphs of bounded tree-width. We present a PTAS (polynomial time approximation scheme) for ℓ-round PDS on planar graphs for l = O(\fraclognloglogn)\ell=O(\frac{\log{n}}{\log{\log{n}}}) . Finally, we give integer programming formulations for ℓ-round PDS.     

Separating online scheduling algorithms with the relative worst order ratio

The relative worst order ratio is a measure for the quality of online algorithms. Unlike the competitive ratio, it compares algorithms directly without involving an optimal offline algorithm. The measure has been successfully applied to problems like paging and bin packing. In this paper, we apply it to machine scheduling. We show that for preemptive scheduling, the measure separates multiple pairs of algorithms which have the same competitive ratios; with the relative worst order ratio, the algorithm which is “intuitively better” is also provably better. Moreover, we show one such example for non-preemptive scheduling.     

Online scheduling with rejection and reordering: exact algorithms for unit size jobs

We study an online scheduling problem with rejection on \(m\ge 2\) identical machines, in which we deal with unit size jobs. Each arriving job has a rejection value (a rejection cost or penalty for minimization problems, and a rejection profit for maximization problems) associated with it. A buffer of size \(K\) is available to store \(K\) jobs. A job which is not stored in the buffer must be either assigned to a machine or rejected. Upon the arrival of a new job, the job can be stored in the buffer if there is a free slot (possibly created by evicting other jobs and assigning or rejecting every evicted job). At termination, the buffer must be emptied. We study four variants of the problem, as follows. We study the makespan minimization problem, where the goal is to minimize the sum of the makespan and the penalty of rejected jobs, and the \(\ell _p\) norm minimization problem, where the goal is to minimize the sum of the \(\ell _p\) norm of the vector of machine completion times and the penalty of rejected jobs. We also study two maximization problems, where the goal in the first version is to maximize the sum of the minimum machine load (the cover value of the machines) and the total rejection profit, and in the second version the goal is to maximize a function of the machine completion times (which measures the balance of machine loads) and the total rejection profit. We show that an optimal solution (an exact solution for the offline problem) can always be obtained in this environment, and determine the required buffer size. Specifically, for all four variants we present optimal algorithms with \(K=m-1\) and prove that in each case, using a buffer of size at most \(m-2\) does not allow the design of an optimal algorithm, which makes our algorithms optimal in this respect as well. The lower bounds hold even for the special case where the rejection value is equal for all input jobs.     

A new upper bound for the online square packing problem in a strip

In this paper we consider the online problem of packing a list of squares into one strip of width 1 and infinite length without overlap so as to minimize the required height of the packing. We derive an upper bound 5 on the competitive ratio for this problem.     

Near optimal algorithms for online weighted bipartite matching in adversary model

Bipartite matching is an important problem in graph theory. With the prosperity of electronic commerce, such as online auction and AdWords allocation, bipartite matching problem has been extensively studied under online circumstances. In this work, we study the online weighted bipartite matching problem in adversary model, that is, there is a weighted bipartite graph \(G=(L,R,E)\) and the left side L is known as input, while the vertices in R come one by one in an order arranged by the adversary. When each vertex in R comes, its adjacent edges and relative weights are revealed. The algorithm should irreversibly decide whether to match this vertex to an unmatched neighbor in L with the objective to maximize the total weight of the obtained matching. When the weights are unbounded, the best algorithm can only achieve a competitive ratio \(\varTheta \left( \frac{1}{n}\right) \), where n is the number of vertices coming online. Thus, we mainly deal with two variants: the bounded weight problem in which all weights are in the range \([\alpha , \beta ]\), and the normalized summation problem in which each vertex in one side has the same total weights. We design algorithms for both variants with competitive ratio \(\varTheta \left( \max \left\{ \frac{1}{\log \frac{\beta }{\alpha }},\frac{1}{n}\right\} \right) \) and \(\varTheta \left( \frac{1}{\log n}\right) \) respectively. Furthermore, we show these two competitive ratios are tight by providing the corresponding hardness results.     

A two-phase algorithm for bin stretching with stretching factor 1.5

Online Bin Stretching is a semi-online variant of bin packing in which the algorithm has to use the same number of bins as an optimal packing, but is allowed to slightly overpack the bins. The goal is to minimize the amount of overpacking, i.e., the maximum size packed into any bin.We give an algorithm for Online Bin Stretching with a stretching factor of 1.5 for any number of bins. We build on previous algorithms and use a two-phase approach. However, our analysis is technically more complicated and uses amortization over the bins with the help of two weight functions.