Search

We study three two-stage optimization problems with a similar structure and different objectives. In the first stage of each problem, the goal is to assign input jobs of positive sizes to unsplittable bags. After this assignment is decided, the realization of the number of identical machines that will be available is revealed. Then, in the second stage, the bags are assigned to machines. The probability vector of the number of machines in the second stage is known to the algorithm as part of the input before making the decisions of the first stage. Thus, the vector of machine completion times is a random variable. The goal of the first problem is to minimize the expected value of the makespan of the second stage schedule, while the goal of the second problem is to maximize the expected value of the minimum completion time of the machines in the second stage solution. The goal of the third problem is to minimize the \ell_p norm for a fixed p>1, where the norm is applied on machines' completion times vectors. Each one of the first two problems admits a PTAS as Buchem et al. showed recently. Here we significantly improve all their results by designing an EPTAS for each one of these problems. We also design an EPTAS for \ell_p norm minimization for any p>1.

We study ordinal makespan scheduling on small numbers of identical machines, with respect to two parallel solutions. In ordinal scheduling, it is known that jobs are sorted by non-increasing sizes, but the specific sizes are not known in advance. For problems with two parallel solutions, it is required to design two solutions, and the performance of algorithm is tested for each input using the best solution of the two. We find tight results for makespan minimization on two and three machines, and algorithms that have strictly better competitive ratios than the best possible algorithm with a single solution also for four and five machines. To prove upper bounds, we use a new approach of considering pairs of machines from the two solutions.

We consider online preemptive scheduling of jobs arriving one by one, to be assigned to two identical machines, with the goal of makespan minimization. We study the effect of selecting the best solution out of two independent solutions constructed in parallel in an online fashion. Two cases are analyzed, where one case is purely online, and in the other one jobs are presented sorted by non-increasing sizes. We show that using two solutions rather than one improves the performance significantly, but that an optimal solution cannot be obtained for any constant number of solutions constructed in parallel. Our algorithms have the best possible competitive ratios out of algorithms for each one of the classes.

In this paper, we consider semi-online scheduling with migration on two hierarchical machines, with the purpose of minimizing the makespan. The meaning of two hierarchical machines is that one of the machines can run any job, while the other machine can only run specific jobs. Every instance also has a fixed parameter M \geq 0, known as the migration factor. Jobs are presented one by one. Each new job has to be assigned to a machine when it arrives, and at the same time it is possible to modify the assignment of previously assigned jobs, such that the moved jobs have a total size not exceeding M times the size of the new job. The semi-online variant studied here is called bin stretching. In this problem, the optimal makespan is provided to the scheduler in advance. This is still a non-trivial variant for any migration factor M \geq 0. We prove tight bounds on the competitive ratio for any migration factor M, where the design and analysis is split into several cases, based on the value of M, and the resulting competitive ratio. Unlike the online variant with migration for two hierarchical machines, this case allows an online approximation scheme.

We prove new lower bounds for suitable competitive ratio measures of two relaxed online packing problems: online removable multiple knapsack, and a recently introduced online minimum peak appointment scheduling problem. The high level objective in both problems is to pack arriving items of sizes at most 1 into bins of capacity 1 as efficiently as possible, but the exact formalizations differ. In the appointment scheduling problem, every item has to be assigned to a position, which can be seen as a time interval during a workday of length 1. That is, items are not assigned to bins, but only once all the items are processed, the optimal number of bins subject to chosen positions is determined, and this is the cost of the online algorithm. On the other hand, in the removable knapsack problem there is a fixed number of bins, and the goal of packing items, which consists in choosing a particular bin for every packed item (and nothing else), is to pack as valuable a subset as possible. In this last problem it is possible to reject items, that is, deliberately not pack them, as well as to remove packed items at any later point in time, which adds flexibility to the problem.

Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham's famous list scheduling algorithm dating back to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the algorithm needs to assign the job to a machine. The goal is to minimize the makespan, that is, the maximum machine load. In this paper, we consider the variant with an additional cardinality constraint: The algorithm may assign at most $k$ jobs to each machine where $k$ is part of the input. While the offline (strongly NP-hard) variant of cardinality constrained scheduling is well understood and an EPTAS exists here, no non-trivial results are known for the online variant. We fill this gap by making a comprehensive study of various different online models. First, we show that there is a constant competitive algorithm for the problem and further, present a lower bound of $2$ on the competitive ratio of any online algorithm. Motivated by the lower bound, we consider a semi-online variant where upon arrival of a job of size $p$, we are allowed to migrate jobs of total size at most a constant times $p$. This constant is called the migration factor of the algorithm. Algorithms with small migration factors are a common approach to bridge the performance of online algorithms and offline algorithms. One can obtain algorithms with a constant migration factor by rounding the size of each incoming job and then applying an ordinal algorithm to the resulting rounded instance. With this in mind, we also consider the framework of ordinal algorithms and characterize the competitive ratio that can be achieved using the aforementioned approaches., Comment: An extended abstract will appear in the proceedings of STACS'22

We consider a known variant of bin packing called {\it cardinality constrained bin packing}, also called {\it bin packing with cardinality constraints} (BPCC). In this problem, there is a parameter k\geq 2, and items of rational sizes in [0,1] are to be packed into bins, such that no bin has more than k items or total size larger than 1. The goal is to minimize the number of bins. A recently introduced concept, called the price of clustering, deals with inputs that are presented in a way that they are split into clusters. Thus, an item has two attributes which are its size and its cluster. The goal is to measure the relation between an optimal solution that cannot combine items of different clusters into bins, and an optimal solution that can combine items of different clusters arbitrarily. Usually the number of clusters may be large, while clusters are relatively small, though not trivially small. Such problems are related to greedy bin packing algorithms, and to batched bin packing, which is similar to the price of clustering, but there is a constant number of large clusters. We analyze the price of clustering for BPCC, including the parametric case with bounded item sizes. We discuss several greedy algorithms for this problem that were not studied in the past, and comment on batched bin packing.

In the d-dimensional online bin packing problem, d-dimensional cubes of positive sizes no larger than 1 are presented one by one to be assigned to positions in d-dimensional unit cube bins. In this work, we provide improved upper bounds on the asymptotic competitive ratio for square and cube bin packing problems, where our bounds do not exceed 2.0885 and 2.5735 for square and cube packing, respectively. To achieve these results, we adapt and improve a previously designed harmonic-type algorithm, and apply a different method for defining weight functions. We detect deficiencies in the state-of-the-art results by providing counter-examples to the current best algorithms and the analysis, where the claimed bounds were 2.1187 for square packing and 2.6161 for cube packing., Comment: WADS 2021

We analyze a recently introduced concept, called the price of clustering, for variants of bin packing called open-end bin packing problems (OEBP). Input items have sizes, and they also belong to a certain number of types. The new concept deals with the comparison of optimal solutions for the cases where items of distinct types can and cannot be packed together, respectively. The problem is related to greedy bin packing algorithms and to batched bin packing, and we discuss some of those concepts as well. We analyze max-OEBP, where a packed bin is valid if by excluding its largest item, the total size of items is below 1. For this variant, we study the case of general item sizes, and the parametric case with bounded item sizes, which shows the effect of small items. Finally, we briefly discuss min-OEBP, where a bin is valid if the total size of its items excluding the smallest item is below 1, which is known to be an entirely different problem.

We consider the Ordered Open End Bin Packing problem. Items of sizes in $(0,1]$ are presented one by one, to be assigned to bins in this order. An item can be assigned to any bin for which the current total size strictly below $1$. This means also that the bin can be overloaded by its last packed item. We improve lower and upper bounds on the asymptotic competitive ratio in the online case. Specifically, we design the first algorithm whose asymptotic competitive ratio is strictly below $2$ and it is close to the lower bound. This is in contrast to the best possible absolute approximation ratio, which is equal to $2$. We also study the offline problem where the sequence of items is known in advance, while items are still assigned to bins based on their order in the sequence. For this scenario we design an asymptotic polynomial time approximation scheme.

In this work, we consider online vector bin packing. It is known that no algorithm can have a competitive ratio of $o(d/\log^2 d)$ in the absolute sense, though upper bounds for this problem were always shown in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure and since the two measures are different, we focus on the asymptotic measure and prove new lower bounds on the asymptotic competitive ratio. The existing lower bounds prior to this work were much smaller than $3$ even for very large dimensions. We significantly improve the best known lower bounds on the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with $d \geq 3$ dimensions, for every such dimension $d$. To obtain these results, we use several different constructions, one of which is an adaptive construction showing a lower bound of $\Omega(\sqrt{d})$. Our main result is that the lower bound of $\Omega(d/\log^2 d)$ on the competitive ratio holds also in the asymptotic sense. The last result requires a careful adaptation of constructions for online coloring rather than simple black-box reductions., Comment: Submitted to SODA 2021

We continue the study of two recently introduced bin packing type problems, called bin packing with clustering, and online bin packing with delays. A bin packing input consists of items of sizes not larger than 1, and the goal is to partition or pack them into bins, where the total size of items of every valid bin cannot exceed 1. In bin packing with clustering, items also have colors associated with them. A globally optimal solution can combine items of different colors in bins, while a clustered solution can only pack monochromatic bins. The goal is to compare a globally optimal solution to an optimal clustered solution, under certain constraints on the coloring provided with the input. We show close bounds on the worst-case ratio between these two costs, called "the price of clustering", improving and simplifying previous results. Specifically, we show that the price of clustering does not exceed 1.93667, improving over the previous upper bound of 1.951, and that it is at least 1.93558, improving over the previous lower bound of 1.93344. In online bin packing with delays, items are presented over time. Items may wait to be packed, and an algorithm can create a new bin at any time, packing a subset of already existing unpacked items into it, under the condition that the bin is valid. A created bin cannot be used again in the future, and all items have to be packed into bins eventually. The objective is to minimize the number of used bins plus the sum of waiting costs of all items, called delays. We build on previous work and modify a simple phase-based algorithm. We combine the modification with a careful analysis to improve the previously known competitive ratio from 3.951 to below 3.1551.

Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor $\beta$: When an object $o$ of size $s(o)$ arrives, the decisions for objects of total size at most $\beta\cdot s(o)$ may be revoked. Usually $\beta$ should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classic problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective. In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small $\eps$). We therefore resolve the competitiveness of the bin covering problem with migration.

We slightly improve the known lower bound on the asymptotic competitive ratio for online bin packing of rectangles. We present a complete proof for the new lower bound, whose value is above 1.91.

We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403.

We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lower bound for the asymptotic competitive ratio of online square packing significantly, raising it from roughly 1.68 to above 1.75., Comment: WAOA 2017

We revisit the classic online bin packing problem. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called "bins" of total sizes no larger than 1, such that every item is assigned to a bin before the next item is presented. We use online partitioning of items into classes based on sizes, as in previous work, but we also apply a new method where items of one class can be packed into more than two types of bins, where a bin type is defined according to the number of such items grouped together. Additionally, we allow the smallest class of items to be packed in multiple kinds of bins, and not only into their own bins. We combine this with the approach of packing of sufficiently big items according to their exact sizes. Finally, we simplify the analysis of such algorithms, allowing the analysis to be based on the most standard weight functions. This simplified analysis allows us to study the algorithm which we defined based on all these ideas. This leads us to the design and analysis of the first algorithm of asymptotic competitive ratio strictly below 1.58, specifically, we break this barrier and provide an algorithm AH (Advanced Harmonic) whose asymptotic competitive ratio does not exceed 1.5783.

In graph coloring problems, the goal is to assign a positive integer color to each vertex of an input graph such that adjacent vertices do not receive the same color assignment. For classic graph coloring, the goal is to minimize the maximum color used, and for the sum coloring problem, the goal is to minimize the sum of colors assigned to all input vertices. In the offline variant, the entire graph is presented at once, and in online problems, one vertex is presented for coloring at each time, and the only information is the identity of its neighbors among previously known vertices. In batched graph coloring, vertices are presented in k batches, for a fixed integer k > 1, such that the vertices of a batch are presented as a set, and must be colored before the vertices of the next batch are presented. This last model is an intermediate model, which bridges between the two extreme scenarios of the online and offline models. We provide several results, including a general result for sum coloring and results for the classic graph coloring problem on restricted graph classes: We show tight bounds for any graph class containing trees as a subclass (e.g., forests, bipartite graphs, planar graphs, and perfect graphs), and a surprising result for interval graphs and k = 2, where the value of the (strict and asymptotic) competitive ratio depends on whether the graph is presented with its interval representation or not.

Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k \geq 2, items having sizes in (0,1] associated with them are presented one by one to be packed into unit capacity bins, such that the capacities of bins are not exceeded, and no bin receives more than k items. We resolve the online problem in the sense that we prove a lower bound of 2 on the overall asymptotic competitive ratio. This closes this long standing open problem, since an algorithm of an absolute competitive ratio 2 is known. Additionally, we significantly improve the known lower bounds on the asymptotic competitive ratio for every specific value of k. The novelty of our constructions is based on full adaptivity that creates large gaps between item sizes. Thus, our lower bound inputs do not follow the common practice for online bin packing problems of having a known in advance input consisting of batches for which the algorithm needs to be competitive on every prefix of the input.

Though competitive analysis is often a very good tool for the analysis of online algorithms, sometimes it does not give any insight and sometimes it gives counter-intuitive results. Much work has gone into exploring other performance measures, in particular targeted at what seems to be the core problem with competitive analysis: the comparison of the performance of an online algorithm is made to a too powerful adversary. We consider a new approach to restricting the power of the adversary, by requiring that when judging a given online algorithm, the optimal offline algorithm must perform as well as the online algorithm, not just on the entire final request sequence, but also on any prefix of that sequence. This is limiting the adversary's usual advantage of being able to exploit that it knows the sequence is continuing beyond the current request. Through a collection of online problems, including machine scheduling, bin packing, dual bin packing, and seat reservation, we investigate the significance of this particular offline advantage., Comment: IMADA-preprint-cs

A two-dimensional grid consists of vertices of the form (i,j) for 1 \leq i \leq m and 1 \leq j \leq n, for fixed m,n > 1. Two vertices are adjacent if the \ell_1 distance between their vectors is equal to 1. A landmark set is a subset of vertices L \subseteq V, such that for any distinct pair of vertices u,v \in V, there exists a vertex of L whose distances to u and v are not equal. We design an efficient algorithm for finding a minimum landmark set with respect to total cost in a grid graph with non-negative costs defined on the vertices.

Let T=(V,E) be a tree graph with non-negative weights defined on the vertices. A vertex z is called a separating vertex for u and v if the distances of z to u and v are not equal. A set of vertices L\subseteq V is a feasible solution for the non-landmarks model (NL), if for every pair of distinct vertices, u,v \in V\setminus L, there are at least two vertices of L separating them. Such a feasible solution is called a "landmark set". We analyze the structure of landmark sets for trees and design a linear time algorithm for finding a minimum cost landmark set for a given tree graph.

For an undirected graph G=(V,E), a vertex x \in V separates vertices u and v (where u,v \in V, u \neq v) if their distances to x are not equal. Given an integer parameter k \geq 1, a set of vertices L \subseteq V is a feasible solution if for every pair of distinct vertices, u,v, there are at least k distinct vertices x_1,x_2,...,x_k \in L each separating u and v. Such a feasible solution is called a "landmark set", and the k-metric dimension of a graph is the minimal cardinality of a landmark set for the parameter k. The case k=1 is a classic problem, where in its weighted version, each vertex v has a non-negative weight, and the goal is to find a landmark set with minimal total weight. We generalize the problem for k \geq 2, introducing two models, and we seek for solutions to both the weighted version and the unweighted version of this more general problem. In the model of all-pairs (AP), k separations are needed for every pair of distinct vertices of V, while in the non-landmarks model (NL), such separations are required only for pairs of distinct vertices in V \setminus L. We study the weighted and unweighted versions for both models (AP and NL), for path graphs, complete graphs, complete bipartite graphs, and complete wheel graphs, for all values of k \geq 2. We present algorithms for these cases, thus demonstrating the difference between the two new models, and the differences between the cases k=1 and k \geq 2.

We study a variant of online bin packing, called colorful bin packing. In this problem, items that are presented one by one are to be packed into bins of size 1. Each item i has a size s_i \in [0,1] and a color c_i \in C, where C is a set of colors (that is not necessarily known in advance). The total size of items packed into a bin cannot exceed its size, thus an item i can always be packed into a new bin, but an item cannot be packed into a non-empty bin if the previous item packed into that bin has the same color, or if the occupied space in it is larger than 1-s_i. This problem generalizes standard online bin packing and online black and white bin packing (where |C|=2). We prove that colorful bin packing is harder than black and white bin packing in the sense that an online algorithm for zero size items that packs the input into the smallest possible number of bins cannot exist for C \geq 3, while it is known that such an algorithm exists for |C|=2. We show that natural generalizations of classic algorithms for bin packing fail to work for the case |C| \geq 3 and moreover, algorithms that perform well for black and white bin packing do not perform well either, already for the case |C|=3. Our main results are a new algorithm for colorful bin packing that we design and analyze, whose absolute competitive ratio is 4, and a new lower bound of 2 on the asymptotic competitive ratio of any algorithm, that is valid even for black and white bin packing., Comment: To appear in SWAT 2014

Bin packing with cardinality constraints is a bin packing problem where an upper bound k \geq 2 on the number of items packed into each bin is given, in addition to the standard constraint on the total size of items packed into a bin. We study the online scenario where items are presented one by one. We analyze it with respect to the absolute competitive ratio and prove tight bounds of 2 for any k \geq 4. We show that First Fit also has an absolute competitive ratio of 2 for k=4, but not for larger values of k, and we present a complete analysis of its asymptotic competitive ratio for all values of k \geq 5. Additionally, we study the case of small $k$ with respect to the asymptotic competitive ratio and the absolute competitive ratio.

We study classic scheduling problems on uniformly related machines. Efficient polynomial time approximation schemes (EPTAS's) are fast and practical approximation schemes. New methods and techniques are essential in developing such improved approximation schemes, and their design is a primary goal of this research agenda. We present EPTAS's for the scheduling problem of a set of jobs on uniformly related machines so as to minimize the total weighted completion time, both for the case with release dates and its special case without release dates. These problems are NP-hard in the strong sense, and therefore EPTAS's are the best possible approximation schemes unless P=NP. Previously, only PTAS's were known for these two problems, while an EPTAS was known only for the special case of identical machines without release dates.

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 l_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. 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+epsilon for every epsilon>0.

When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight. The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by preemptive online algorithms: 1. We provide a lower bound of 1+ln 2~1.693 on the competitive ratio of any randomized algorithm for the maximum cardinality matching problem, thus improving on the currently best known bound of e/(e-1)~1.581 due to Karp, Vazirani, and Vazirani [STOC'90]. 2. We devise a randomized algorithm that achieves an expected competitive ratio of 5.356 for maximum weight matching. This finding demonstrates the power of randomization in this context, showing how to beat the tight bound of 3 +2\sqrt{2}~5.828 for deterministic algorithms, obtained by combining the 5.828 upper bound of McGregor [APPROX'05] and the recent 5.828 lower bound of Varadaraja [ICALP'11].