We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its right, and the packet arrives at the next router one time step later. Packets are forwarded until they reach their destination. The flow time of a packet is the elapsed time between its release and its arrival at its destination. The goal is to minimize the maximum flow time. This problem was introduced by Antoniadis et al. in 2014, with a focus on line networks. They proposed several natural algorithms. For one, they proved that it is not O(1)-competitive; for others, they claimed analogous lower bounds, seemingly leaving no natural candidate for an O(1)-competitive algorithm. In this paper, we study a natural algorithm not considered in that work. Our algorithm, simply called Greedy, selects packets according to their projected flow time under the assumption that they are not delayed any further. We focus on the special case in which each packet needs to be forwarded by one or two routers; this case captures core difficulties. We show that Greedy achieves a competitive ratio of exactly 2-2^{1-k}, where k is the number of active routers in the network. We also give the first nontrivial general lower bound, which applies even to randomized algorithms: using the same type of instances as in our lower bound for Greedy, we show that no algorithm can be (4/3-ε)-competitive for any ε > 0.

Abstract We consider the problem of minimizing the total completion time on a single online machine using restarts. Although restarts can potentially be very beneficial in the context of online scheduling, there has been relatively little research on this topic up until now. We present a very simple online algorithm which is better than 1.4568-competitive. The basic rule of the algorithm is to run jobs in order of increasing size. For possible restarts, the algorithm only considers whether the completion time of an incoming job is more than a factor of 1.4568 higher if we first let the running job finish compared to the case where we start the new job immediately. If this is the case, we interrupt the running job and start running the new job. All other existing or past jobs are ignored for this decision. The analysis of the algorithm has become significantly easier and shorter than for the previous best result which was 3/2. We hope that this result can lead to further research in this interesting topic.

We break the barrier of $3/2$ for the problem of online load balancing with known makespan, also known as bin stretching. In this problem, $m$ identical machines and the optimal makespan are given. The load of a machine is the total size of all the jobs assigned to it and the makespan is the maximum load of all the machines. Jobs arrive online and the goal is to assign each job to a machine while staying within a small factor (the competitive ratio) of the optimal makespan. We present an algorithm that maintains a competitive ratio of $139/93<1.495$ for sufficiently large values of $m$, improving the previous bound of $3/2$. The value 3/2 represents a natural bound for this problem: as long as the online bins are of size at least $3/2$ of the offline bin, all items that fit at least two times in an offline bin have two nice properties. They fit three times in an online bin and a single such item can be packed together with an item of any size in an online bin. These properties are now both lost, which means that putting even one job on a wrong machine can leave some job unassigned at the end. It also makes it harder to determine good thresholds for the item types. This was one of the main technical issues in getting below $3/2$. The analysis consists of an intricate mixture of size and weight arguments.

In the discrete bamboo garden trimming problem we are given n bamboo that grow at rates v1, . . ., vn per day. Each day a robotic gardener cuts down one bamboo to height 0. The goal is to find a schedule that minimizes the height of the tallest bamboo that ever exists. We present a 10/7-approximation algorithm that is based on a reduction to the pinwheel problem. This is consistent with the approach of earlier algorithms, but some new techniques are used that lead to a better approximation ratio. We also consider the continuous version of the problem where the gardener travels in a metric space between plants and cuts down a plant each time he reaches one. We show that on the star graph the previously proposed algorithm Reduce-Fastest is a 6-approximation and the known Deadline-Driven Strategy is a (3 + 2√2)-approximation. The Deadline-Driven Strategy is also a (9 + 2√5)-approximation on star graphs with multiple plants on each branch.

One of the most significant algorithmic challenges in the "big data era" is handling instances that are too large to be processed by a single machine. The common practice in this regard is to partition the massive problem instance into smaller ones and process each one of them separately. In some cases, the solutions for the smaller instances are later on assembled into a solution for the whole instance, but in many cases this last stage cannot be pursued (e.g., because it is too costly, because of locality issues, or due to privacy considerations). Motivated by this phenomenon, we consider the following natural combinatorial question: Given a bin-packing instance (namely, a set of items with sizes in (0, 1] that should be packed into unit capacity bins) I and a partition Ii \ i of I into clusters, how large is the ratio ∑i Øpt(Ii) / Øpt(I), where Øpt(J) denotes the optimal number of bins into which the items in J can be packed? In this paper, we investigate the supremum of this ratio over all instances I and partitions Ii \ i, referred to as the bin-packing price of clustering (¶oC ). It is trivial to observe that if each cluster contains only one tiny item (and hence, Øpt(Ii) = 1), then the ¶oC is unbounded. On the other hand, a relatively straightforward argument shows that under the constraint that Øpt(Ii) ≥ 2, the ¶oC is 2. Our main challenge was to determine whether the ¶oC drops below 2 when Øpt(Ii) > 2. In addition, one may hope that łimk -> ∞ ¶oC(k) = 1, where ¶oC(k) denotes the ¶oC under the restriction to clusters Ii with Øpt(Ii) ≥ k. We resolve the former question affirmatively and the latter one negatively: Our main results are that ¶oC(k) łeq 1.951 for any k ≥ 3 and łimk -> ∞ ¶oC(k) = 1.691... Moreover, the former bound cannot be significantly improved as ¶oC(3) > 1.933. In addition to the immediate contribution of this combinatorial result to "big data" kind of applications, it turns out that it is useful also for an interesting online problem called bin-packing with delays.

In the online bin packing problem, items of sizes in (0,1] arrive online to be packed into bins of size 1. The goal is to minimize the number of used bins. Harmonic++ achieves a competitive ratio of 1.58889 and belongs to the Super Harmonic framework [Seiden, J. ACM, 2002]; a lower bound of Ramanan et al. shows that within this framework, no competitive ratio below 1.58333 can be achieved [Ramanan et al., J. Algorithms, 1989]. In this paper, we present an online bin packing algorithm with asymptotic performance ratio of 1.5815, which constitutes the first improvement in fifteen years and reduces the gap to the lower bound by roughly 15%. We make two crucial changes to the Super Harmonic framework. First, some of the decisions of the algorithm will depend on exact sizes of items, instead of only their types. In particular, for item pairs where the size of one item is in (1/3,1/2] and the other is larger than 1/2 (a large item), when deciding whether to pack such a pair together in one bin, our algorithm does not consider their types, but only checks whether their total size is at most 1. Second, for items with sizes in (1/3,1/2] (medium items), we try to pack the larger items of every type in pairs, while combining the smallest items with large items whenever possible. To do this, we postpone the coloring of medium items (i.e., the decision which items to pack in pairs and which to pack alone) where possible, and later select the smallest ones to be reserved for combining with large items. Additionally, in case such large items arrive early, we pack medium items with them whenever possible. This is a highly unusual idea in the context of Harmonic-like algorithms, which initially seems to preclude analysis (the ratio of items combined with large items is no longer a fixed constant). For the analysis, we carefully mark medium items depending on how they end up packed, enabling us to add crucial constraints to the linear program used by Seiden. We consider the dual, eliminate all but one variable and then solve it with the ellipsoid method using a separation oracle. Our implementation uses additional algorithmic ideas to determine previously hand set parameters automatically and gives certificates for easy verification of the results. We give a lower bound of 1.5766 for algorithms like ours. This shows that fundamentally different ideas will be required to make further improvements

We consider online preemptive scheduling of jobs with fixed starting times revealed at those times on $$m$$ uniformly related machines, with the goal of maximizing the total weight of completed jobs. Every job has a size and a weight associated with it. A newly released job must be either assigned to start running immediately on a machine or otherwise it is dropped. It is also possible to drop an already scheduled job, but only completed jobs contribute their weights to the profit of the algorithm. In the most general setting, no algorithm has bounded competitive ratio, and we consider a number of standard variants. We give a full classification of the variants into cases which admit constant competitive ratio (weighted and unweighted unit jobs, and C-benevolent instances, which is a wide class of instances containing proportional-weight jobs), and cases which admit only a linear competitive ratio (unweighted jobs and D-benevolent instances). In particular, we give a lower bound of $$m$$ on the competitive ratio for scheduling unit weight jobs with varying sizes, which is tight. For unit size and weight we show that a natural greedy algorithm is $$4/3$$ -competitive and optimal on $$m=2$$ machines, while for large $$m$$ , its competitive ratio is between $$1.56$$ and $$2$$ . Furthermore, no algorithm is better than $$1.5$$ -competitive.

We present an online bin packing algorithm with absolute competitive ratio 5/3, which is optimal.

We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTAS's) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the ℓp norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it. The key idea of our novel method is to show that for goal functions that are sufficiently well-behaved functions of the machine loads, it is possible to compute in polynomial time a highly structured nearly optimal schedule. An interesting aspect of our approach is that, in contrast to all known approximation schemes, we avoid rounding any job sizes or speeds throughout. We can therefore find the exact best structured schedule using dynamic programming. The state space encodes a sufficient amount of information such that no postprocessing is needed, allowing an elegant and relatively simple analysis without any special cases. The monotonicity is a consequence of the fact that we find the best schedule in a specific collection of schedules. Monotone approximation schemes have an important role in the emerging area of algorithmic mechanism design. In the game-theoretical setting of these scheduling problems there is a social goal, which is one of the objective functions that we study. Each machine is controlled by a selfish single-parameter agent, where its private information is its cost of processing a unit sized job, which is also the inverse of the speed of its machine. Each agent wishes to maximize its own profit, defined as the payment it receives from the mechanism minus its cost for processing all jobs assigned to it, and places a bid which corresponds to its private information. For each one of the problems, we show that we can calculate payments that guarantee truthfulness in an efficient manner. Thus, there exists a dominant strategy where agents report their true speeds, and we show the existence of a truthful mechanism which can be implemented in polynomial time, where the social goal is approximated within a factor of 1 + ε for every ε > 0.

We consider a memory allocation problem. This problem can be modeled as a version of bin packing where items may be split, but each bin may contain at most two (parts of) items. This problem was recently introduced by Chung et al. (Theory Comput. Syst. 39(6):829–849, 2006). We give a simple $\frac{3}{2}$ -approximation algorithm for this problem which is in fact an online algorithm. This algorithm also has good performance for the more general case where each bin may contain at most k parts of items. We show that this general case is strongly NP-hard for any k≥3. Additionally, we design an efficient approximation algorithm, for which the approximation ratio can be made arbitrarily close to $\frac{7}{5}$ .

We consider online scheduling so as to maximize the minimum load, using a reordering buffer that can store some of the jobs before they are assigned irrevocably to machines. For [Formula: see text] identical machines, we show an upper bound of [Formula: see text] for a buffer of size [Formula: see text]. A competitive ratio below [Formula: see text] is not possible with any fixed buffer size, and it requires a buffer of size [Formula: see text] to get a ratio of [Formula: see text]. For uniformly related machines, we show that a buffer of size [Formula: see text] is sufficient to get a competitive ratio of [Formula: see text], which is best possible for any fixed sized buffer. We show similar results (but with different constructions) for the restricted assignment model. We give tight bounds for two machines in all the three models. These results sharply contrast to the (previously known) results, which can be achieved without the usage of a reordering buffer, where it is not possible to get a competitive ratio below [Formula: see text] already for identical machines, and it is impossible to obtain an algorithm of finite competitive ratio in the other two models, even for [Formula: see text]. Our results strengthen the previous conclusion that a reordering buffer is a powerful tool and that it allows a significant decrease in the competitive ratio of online algorithms for scheduling problems. Another interesting aspect of our results is that our algorithm for identical machines imitates the behavior of a greedy algorithm on (a specific set of) related machines, whereas our algorithm for related machines completely ignores the speeds until all jobs have arrived, and then only uses the relative order of the speeds.

We continue the study of the online unit clustering problem, introduced by Chan and Zarrabi-Zadeh ( Workshop on Approximation and Online Algorithms 2006 , LNCS 4368, p. 121--131. Springer, 2006). We design a deterministic algorithm with a competitive ratio of 7/4 for the one-dimensional case. This is the first deterministic algorithm that beats the bound of 2. It also has a better competitive ratio than the previous randomized algorithms. Moreover, we provide the first non-trivial deterministic lower bound, improve the randomized lower bound, and prove the first lower bounds for higher dimensions.

We consider online scheduling of splittable tasks on parallel machines, where the goal is to minimize the last completion time (the makespan). In our model, each task can be split into a limited number of parts, that can then be scheduled independently and in parallel. We consider both the case where the machines are identical and the case where some subset of the machines have a (fixed) higher speed than the others. We design a class of algorithms that allows us to give tight bounds for a large class of cases where tasks may be split into relatively many parts. For identical machines, we also improve upon the natural greedy algorithm in other classes of cases.

We consider two- and three-dimensional bin-packing problems where 90° rotations are allowed. We improve all known asymptotic performance bounds for these problems. In particular, we show how to combine ideas from strip packing and two-dimensional bin packing to give a new algorithm for the three-dimensional strip packing problem where boxes can only be rotated sideways. We propose to call this problem “This side up”. Our algorithm has an asymptotic performance bound of 9/4.

We present an asymptotic fully polynomial time approximation scheme for two-dimensional strip packing with rotations. In this problem, a set of rectangles need to be packed into a rectangle (strip) of fixed width and minimum height, and these rectangles can be rotated by 90°. Additionally, we present a simple asymptotic polynomial time approximation scheme, and give an improved algorithm for two-dimensional bin packing with rotations.

We solve an open problem in the literature by providing an online algorithm for multidimensional bin packing that uses only bounded space. To achieve this, we introduce a new technique for classifying the items to be packed. We show that our algorithm is optimal among bounded space algorithms for any dimension $d>1$. Its asymptotic performance ratio is $(\Pi_{\infty})^d$, where $\Pi_{\infty}\approx1.691$ is the asymptotic performance ratio of the one-dimensional algorithm \harm. A modified version of this algorithm for thecase where all items are hypercubes is also shown to be optimal. Its asymptotic performance ratio is sublinear in d. Furthermore, we extend the techniques used in these algorithms to give optimal algorithms for online bounded space variable-sized packing and resource augmented packing.

In the variable-sized online bin packing problem, one has to assign items to bins one by one. The bins are drawn from some fixed set of sizes, and the goal is to minimize the sum of the sizes of the bins used. We present new algorithms for this problem and show upper bounds for them which improve on the best previous upper bounds. We also show the first general lower bounds for this problem. The case in which bins of two sizes, 1 and $\alpha \in (0,1)$, are used is studied in detail. This investigation leads us to the discovery of several interesting fractal-like curves.