Search

We present a new generalization of the bin covering problem that is known to be a strongly NP-hard problem. In our generalization there is a positive constant Δ , and we are given a set of items each of which has a positive size. We would like to find a partition of the items into bins. We say that a bin is near exact covered if the total size of items packed into the bin is between 1 and 1 + Δ . Our goal is to maximize the number of near exact covered bins. If Δ = 0 or Δ > 0 is given as part of the input, our problem is shown here to have no approximation algorithm with a bounded asymptotic approximation ratio (assuming that P ≠ N P ). However, for the case where Δ > 0 is seen as a constant, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) that is our main contribution. [ABSTRACT FROM AUTHOR]

We consider non-preemptive load balancing on m identical machines where the cost of a machine is defined as the maximum starting time of a job assigned to the machine, and the goal is to find a partition of the jobs that minimizes the maximum machine cost. In our variant the last job on each machine is the smallest job assigned to that machine. The online model for this problem is too restrictive as a trivial example shows that there is no competitive algorithm for the problem. We show that a constant migration factor is sufficient to guarantee a (3 2 + ε) -competitive algorithm for all ε > 0 , and using a constant migration factor cannot lead to a better than a 3 2 -competitive algorithm. We also show that for this problem, constant amortized migration factor is strictly more powerful and allows us to obtain a polynomial time approximation scheme with a constant amortized migration factor. Thus, the ability to move some limited set of jobs on each step allows the algorithm to be much better than in the pure online settings. [ABSTRACT FROM AUTHOR]

We consider the problem of weighted throughput in the single machine preemptive scheduling with continuous controllable processing times. A set of tasks can be scheduled on a single machine. Each task j is associated with a nonnegative weight w j , a release date, a due date, and an interval of possible processing times. A task j can either be scheduled with a total processing time p j which is in the given interval, or rejected (not participating in the schedule). The reward for processing j for p j time units is w j p j , and we are interested in constructing a feasible preemptive schedule such that the sum of rewards is maximized. We present a dynamic programming algorithm that solves the problem in pseudo-polynomial time and use it to obtain an FPTAS. Afterward, as our main contribution we propose an interesting efficient frontier approach for improved complexity bounds. [ABSTRACT FROM AUTHOR]

We present a new generalization of the extensible bin packing with unequal bin sizes problem. In our generalization the cost of exceeding the bin size (also known as the bin capacity) depends on the index of the bin and not only on the amount in which the size of the bin is exceeded. This generalization does not satisfy the assumptions on the cost function that were used to present the existing polynomial time approximation scheme (PTAS) for the extensible bin packing with unequal bin sizes problem. In this work, we show the existence of an efficient PTAS (EPTAS) for this new generalization and thus in particular we improve the earlier PTAS for the extensible bin packing with unequal bin sizes problem into an EPTAS. Our new scheme is based on using the shifting technique followed by a solution of a polynomial number of n-fold programming instances. In addition, we present an asymptotic fully polynomial time approximation scheme for the related bin packing type variant of the problem. [ABSTRACT FROM AUTHOR]

We consider a scheduling problem on identical machines, where the cost for each machine is the total size of jobs assigned to it, excluding its largest job. The objective is to minimize the cost of the schedule, which is the maximum cost over all machines. We study online algorithms with and without migration. We design an algorithm with competitive ratio 3 for the purely online variant and provide a lower bound of 2.26953 on the competitive ratio of any online algorithm. For two machines, we find tight bounds of 2 on the competitive ratio. Additionally, we design a polynomial time approximation scheme for the variant with migration. We also briefly discuss the same online problem on uniformly related machines. [ABSTRACT FROM AUTHOR]

We consider a general load balancing problem on parallel machines. Our machine environment in particular generalizes the standard models of identical machines, and the model of uniformly related machines, as well as machines with a constant number of types, and machines with activation costs. The objective functions that we consider contain in particular the makespan objective and the minimization of the ℓ p -norm of the vector of loads of the machines, and each case allows the possibility of job rejection. We consider this general model and design an efficient polynomial time approximation scheme (EPTAS) that applies for all its previously-studied special cases. This EPTAS improves the current best approximation scheme for some of these cases where only a polynomial time approximation scheme was known into an EPTAS. [ABSTRACT FROM AUTHOR]

Abstract We study the Deadline TSP problem. The input consists of a complete undirected graph G = (V , E) , a metric c : E → Z + , a reward function w : V → Z + , a non-negative deadline function d : V → Z + , and a starting node s ∈ V. A feasible solution is a path starting at s. Given such a path and a node v ∈ V , we say that the path visits v by its deadline if the length of the prefix of the path starting at s until the first time it traverses v is at most d (v) (in particular, it means that the path traverses v). If a path visits v by its deadline, it gains the reward w (v). The objective is to find a path P starting at s that maximizes the total reward. In our work we present a bi-criteria (1 + ε , α 1 + ε)-approximation algorithm for every ε > 0 for the Deadline TSP, where α is the approximation ratio for Deadline TSP with a constant number of deadlines (currently α = 1 3 by [5]) and thus significantly improving the previously best known bi-criteria approximation for that problem (a bi-criteria (1 + ε , 1 O (log ⁡ (1 / ε))) -approximation algorithm for every ε > 0 by Bansal et al. [1]). We also present improved bi-criteria (1 + ε , 1 1 + ε) -approximation algorithms for the Deadline TSP on weighted trees. [ABSTRACT FROM AUTHOR]

Abstract In sum coloring, it is required to find a proper coloring of the vertices of a graph using positive integers, such that the sum of colors of the vertices is minimized. First Fit is the natural coloring algorithm that processes vertices one by one (in some order), and colors the current vertex with the minimum color that was not used for any of its already considered neighbors. Here, we study the approximation ratio of First Fit for sum coloring for the class of claw-free graphs, its most natural subclasses, and its generalizations, and get tight bounds for it. Highlights • A thorough study of the approximation ratio for the natural algorithm First Fit. • A study of sum coloring of graphs, of vertices or edges. • A tight analysis of (k + 1)-claw free graphs, with new types of examples. • A tight analysis for important subclasses of via linear programs. • A tight analysis for edge coloring and a tight analysis for unit interval graphs. [ABSTRACT FROM AUTHOR]

The dual of splittable bin packing with cardinality constraint is a variant of fractional scheduling on identical machines with the goal of minimizing the makespan. In this variant we are given an upper bound on the number of jobs that have fractions that are processed on a common machine. This restriction makes the problem NP-hard in the strong sense. We exhibit an EPTAS for this problem when the cardinality upper bound is part of the input. This result answers an open question raised by Epstein, Levin, and van Stee [16]. [ABSTRACT FROM AUTHOR]

We introduce and study the problem of optimizing arbitrary functions over degree sequences of hypergraphs and multihypergraphs. We show that over multihypergraphs the problem can be solved in polynomial time. For hypergraphs, we show that deciding whether a given sequence is the degree sequence of a 3-hypergraph is NP-complete, thereby solving a 30 year long open problem. This implies that optimization over hypergraphs is hard even for simple concave functions. In contrast, we show that for graphs, if the functions at vertices are the same, then the problem is polynomial time solvable. We also provide positive results for convex optimization over multihyper-graphs and graphs and exploit connections to degree sequence polytopes and threshold graphs. We then elaborate on connections to the emerging theory of shifted combinatorial optimization. [ABSTRACT FROM AUTHOR]

Preemptive online algorithms for the maximum matching problem 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 randomized preemptive online algorithms: • 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. • We devise a randomized algorithm that achieves an expected competitive ratio of 5.356 for maximum weight matching. [ABSTRACT FROM AUTHOR]

Consider a rescue plan after a major disaster such as an earthquake, where the objective is to find and rescue as many survivors as possible. The rescue team has to decide where to search for survivors, and as time progress the number of survivors in each location decreases. This problem can be modeled as Discounted Reward TSP on a graph G=(V,E) where each node v∈V represents a potential place for searching survivors, and the length of an edge represents the time it takes to travel from one place to another. Each node has an initial prize π(v) (that represents the number of survivors in it) and this prize deteriorates exponentially. Therefore, the prize collected from node v∈V is π(v)λt, where λ is the deterioration rate and t is the first time v was visited. The objective is to find a path that maximizes the total prize collected from the nodes of G. We present two different algorithms for Discounted Reward TSP, each improves the previously best known approximation ratio of 0.1481-δ shown by Blum et al. (SIAM J Comput 37(2):653–670, 2007). Our better algorithm is a (0.1929-δ)-approximation algorithm. [ABSTRACT FROM AUTHOR]

Motivated by issues of minimizing energy consumption, we study variable sized bin packing with general costs . In this problem we are given an unlimited supply of bins of different types. A bin of each type has a size and a cost. A set of items is given, where each item has a size in ( 0 , 1 ] . The goal is to assign the items to bins, so that the total cost is minimized. It is allowed to use multiple instances of any of the bin types, but this counts towards the total cost. The problem is general as the cost of a bin has no relation to its size. We design an AFPTAS for the problem by introducing new reduction methods and separation techniques, thus providing new insights into this interesting optimization problem. Furthermore, we use this AFPTAS to provide an AFPTAS for the bin packing with bin utilization cost problem. [ABSTRACT FROM AUTHOR]

For scheduling problems on parallel machines, the power of preemption is defined as the supremum ratio of the cost of an optimal nonpreemptive schedule over the cost of an optimal preemptive schedule (for the same input), where the cost is defined by a fixed common cost function. We present a tight analysis of the power of preemption for the problem of minimizing the total completion time on m ≥ 2 uniformly related machines, showing that its value for m = 2 is equal to 1.2, and its overall value is approximately 1.39795. [ABSTRACT FROM AUTHOR]

We consider a hybrid two-stage optimization problem that generalizes two classic combinatorial optimization problems: (i) weighted vertex cover in graphs, and (ii) makespan minimization in multiprocessor scheduling. An instance specifies a machine environment, a set of jobs, and an undirected graph over the jobs. The goal is to select a subset of the jobs that forms a vertex cover and to schedule it on a set of parallel machines so as to minimize the makespan. We call this problem family vertex cover meets multiprocessor scheduling (VCMS). The problem is motivated by networks where vertices represent servers and each edge corresponds to a task that can be done by any of the two servers of its endpoint. Each selected server can complete any number of tasks assigned to it within a given time defined by its weight, as the time consumption of the server is roughly equal to its activation time. The activation is performed by a set of $$m$$ processors, such that every selected server is activated by one processor, and the goal is to minimize the maximum total activation time assigned to any processor. We design a multitude of approximation algorithms for VCMS and its variants, many of which match or almost match the best approximation bound known for the vertex cover problem. In particular, we give a $$2$$ -approximation for the case of a fixed number of unrelated machines, a $$3$$ -approximation for an arbitrary number of unrelated machines, and a $$(2+\varepsilon )$$ -approximation for an arbitrary number of identical machines. Furthermore we consider special graph classes for which the weighted vertex cover problem can be solved to optimality in polynomial time: for many of these classes, there is a PTAS for VCMS on identical machines; for bipartite graphs, however, VCMS on identical machines turns out to be APX-hard. Finally, we study the bin packing counterpart of VCMS and design a $$(2+\varepsilon )$$ -approximation algorithm for it. [ABSTRACT FROM AUTHOR]

Given an input undirected graph $$G=(V,E)$$ , we say that a vertex $$\ell $$ separates $$u$$ from $$v$$ (where $$u,v\in V$$ ) if the distance between $$u$$ and $$\ell $$ differs from the distance from $$v$$ to $$\ell $$ . A set of vertices $$L\subseteq V$$ is a feasible solution if for every pair of vertices, $$u,v\in V$$ ( $$u\ne v$$ ), there is a vertex $$\ell \in L$$ that separates $$u$$ from $$v$$ . Such a feasible solution is called a landmark set, and the metric dimension of a graph is the minimum cardinality of a landmark set. Here, we extend this well-studied problem to the case where each vertex $$v$$ has a non-negative cost, and the goal is to find a feasible solution with a minimum total cost. This weighted version is NP-hard since the unweighted variant is known to be NP-hard. We show polynomial time algorithms for the cases where $$G$$ is a path, a tree, a cycle, a cograph, a $$k$$ -edge-augmented tree (that is, a tree with additional $$k$$ edges) for a constant value of $$k$$ , and a (not necessarily complete) wheel. The results for paths, trees, cycles, and complete wheels extend known polynomial time algorithms for the unweighted version, whereas the other results are the first known polynomial time algorithms for these classes of graphs even for the unweighted version. Next, we extend the set of graph classes for which computing the unweighted metric dimension of a graph is known to be NP-hard. We show that for split graphs, bipartite graphs, co-bipartite graphs, and line graphs of bipartite graphs, the problem of computing the unweighted metric dimension of the graph is NP-hard. [ABSTRACT FROM AUTHOR]

We consider stochastic variants of a wide class of NP-hard packing integer problems. In these variants the problem consists of two stages, the first stage is the probing phase, and the second is the optimization phase. The problem has items, each of which is associated with stochastic information which we can probe. We assume that every probed value corresponds to a distribution, that is, the probing does not fix the exact value of the stochastic information associated with the probed item, but fixes another distribution for that information, that is perhaps different for different outcomes of the probing. All these distributions are known to the optimizer a priori. In the optimization phase, the solution is constructed sequentially, and the act of choosing an item instantiates its stochastic information. The goal is to compute a policy that maximizes the expected value of the given objective function of the resulting solution such that the packing constraints are satisfied, where the output solution is the last feasible solution in the series of solutions which the optimizer creates during the optimization phase. We consider both non-adaptive policies (that designate a priori a fixed permutation of variables in the solution) and adaptive policies (that can make dynamic decisions based on the history of the instantiated values of the stochastic information). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. In such problems the benefit of adaptivity is due to two phases: probing and optimization. Assuming that for the optimization phase (without the probing) the benefit of adaptivity is at most ρ , we show an upper bound on the adaptivity gap of 2 ρ for the corresponding class with probing. We demonstrate our results for different problems and for each of these classes we provide examples that show that there is indeed a benefit of adaptivity in probing. [ABSTRACT FROM AUTHOR]

N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicityN-fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N-fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explicit (non-succinct) instance. We present the first fixed-parameter algorithm for high-multiplicity N-fold IPs, which even works for convex objectives. Our key contribution is a novel proximity theorem which relates fractional and integer optima of the Configuration LP, a fundamental notion by Gilmore and Gomory [Oper. Res., 1961] which we generalize. Our algorithm for N-fold IP is faster than previous algorithms whenever the number of blocks is much larger than the number of block types, such as in N-fold IP models for various scheduling problems. [ABSTRACT FROM AUTHOR]

We consider basic problems of non-preemptive scheduling on uniformly related machines. For a given schedule, defined by a partition of the jobs into m subsets corresponding to the m machines, $$C_i$$ denotes the completion time of machine i. Our goal is to find a schedule that minimizes or maximizes $$\sum _{i=1}^m C_i^p$$ for a fixed value of p such that $$01$$ the minimization problem is equivalent to the well-known problem of minimizing the $$\ell _p$$ norm of the vector of the completion times of the machines, and for $$0

Preemptive scheduling problems on parallel machines are classic problems. Given the goal of minimizing the makespan, they are polynomially solvable even for the most general model of unrelated machines. In these problems, a set of jobs is to be assigned to run on a set of m machines. A job can be split into parts arbitrarily and these parts are to be assigned to time slots on the machines without parallelism, that is, for every job, at most one of its parts can be processed at each time. Motivated by sensitivity analysis and online algorithms, we investigate the problem of designing robust algorithms for constructing preemptive schedules. Robust algorithms receive one piece of input at a time. They may change a small portion of the solution as an additional part of the input is revealed. The capacity of change is based on the size of the new piece of input. For scheduling problems, the supremum ratio between the total size of the jobs (or parts of jobs) which may be re-scheduled upon the arrival of a new job j, and the size of j, is called migration factor. We design a strongly optimal algorithm with the migration factor $1-\frac{1}{m}$ for identical machines. Strongly optimal algorithms avoid idle time and create solutions where the (non-increasingly) sorted vector of completion times of the machines is lexicographically minimal. In the case of identical machines this results not only in makespan minimization, but the created solution is also optimal with respect to any ℓ norm (for p>1). We show that an algorithm of a smaller migration factor cannot be optimal with respect to makespan or any other ℓ norm, thus the result is best possible in this sense as well. We further show that neither uniformly related machines nor identical machines with restricted assignment admit an optimal algorithm with a constant migration factor. This lower bound holds both for makespan minimization and for any ℓ norm. Finally, we analyze the case of two machines and show that in this case it is still possible to maintain an optimal schedule with a small migration factor in the cases of two uniformly related machines and two identical machines with restricted assignment. [ABSTRACT FROM AUTHOR]

Abstract: We consider a stochastic variant of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. In every stage of insertion if the subset of the items inserted thus far is feasible, then it has a total value that equals to the sum of values of all items of this subset. Otherwise, if the subset violates the constraint, then its value equals to zero. The goal is to compute a policy for insertion of the items, that maximizes the expected total value of items placed in the knapsack. We consider both non-adaptive policies (that designate a priori a fixed subset of items to insert) and adaptive policies (that can make dynamic decisions based on the instantiated sizes of items placed in the knapsack thus far). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. First we show a tight bound of on the adaptivity gap for the case of inputs consisting of only two items. Then we present a non-adaptive policy with expected value that is at least times the expected value of the optimal adaptive policy. Thus the adaptivity gap in this model is at most 11.66. Additionally this non-adaptive policy is computed in polynomial time. Finally, we consider a special case of the model where all sizes are distributed according to Bernoulli distribution with different parameters. For this special case we improve our result and bound the adaptivity gap by 8. [Copyright &y& Elsevier]

Square bin packing, where square items are to be packed into a minimum number of unit size squares, and its multidimensional generalization, cube packing, where d-dimensional cubic items are to be packed into a minimum number of unit size cubes of the same dimension, are well-studied generalizations of the classical one-dimensional bin packing problem. These problems are known to have asymptotic polynomial time approximation schemes (APTAS). In this paper we design robust approximation schemes for these problems. At each step, a robust algorithm receives a single input item to be added to the packing. The new item must be packed and the packing can be modified, but the total volume of items which may migrate between bins, or change their positions inside bins, must be bounded by a constant factor times the volume of the new item. That is, the solution is created by slightly adjusting the solution upon the arrival of each new item. Previous approximation schemes partition items into three types according to size, and rely heavily on the knowledge of the complete input before the implementation of this partition and the creation of the solution, as the definition of the set of medium items is based oil the entire specific input. We introduce new methods which allow us to adjust the partition dynamically, and to modify the packing accordingly. Using these methods, we develop a robust APTAS for every dimension d, that is, a robust polynomial time algorithm for d-dimensional cube packing, which maintains an asymptotically (1 + ε)-approximate solution throughout this process. [ABSTRACT FROM AUTHOR]

Abstract: We consider max coloring on hereditary graph classes. The problem is defined as follows. Given a graph and positive node weights , the goal is to find a proper node coloring of whose color classes minimize . We design a general framework which allows to convert approximation algorithms for standard node coloring into algorithms for max coloring. The approximation ratio increases by a multiplicative factor of at most for deterministic offline algorithms and for randomized online algorithms, and by a multiplicative factor of at most for deterministic online algorithms. We consider two specific hereditary classes which are interval graphs and perfect graphs. For interval graphs, we study the problem in several online environments. In the List Model, intervals arrive one by one, in some order. In the Time Model, intervals arrive one by one, sorted by their left endpoints. For the List Model we design a deterministic 12-competitive algorithm, and a randomized -competitive algorithm. In addition, we prove a lower bound of 4 on the competitive ratio of any deterministic or randomized algorithm. For the Time Model, we use simplified versions of the algorithm and the lower bound of the List Model, to develop a deterministic 4-competitive algorithm, a randomized -competitive algorithm, and to design a lower bounds of on the deterministic competitive ratio and a lower bound of on the randomized competitive ratio. The former lower bounds hold even for unit intervals. For unit intervals in the List Model, we obtain a deterministic -competitive algorithm, a randomized -competitive algorithm and lower bounds of on the deterministic competitive ratio and on the randomized competitive ratio. Finally, we employ our framework to obtain an offline -approximation algorithm for max coloring of perfect graphs, improving and simplifying a recent result of Pemmaraju and Raman. [Copyright &y& Elsevier]

We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. Our objective is to minimize ∑wjf(Cj) for any nondecreasing, nonnegative, differentiable cost function f(Cj ). We aim for a universal solution that performs well without adaptation for all cost functions for any possible machine behavior. We design a deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant algorithm that knows the machine behavior in advance. A randomized version of this algorithm attains in expectation a ratio of e. We also show that both performance guarantees are best possible for any unbounded cost function. Our algorithms can be adapted to run in polynomial time with slightly increased cost. When jobs have individual release dates, the situation changes drastically. Even if all weights are equal, there are instances for which any universal solution is a factor of Ω(log n/ log log n) worse than an optimal sequence for any unbounded cost function. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a nontrivial algorithm with a small constant performance guarantee. [ABSTRACT FROM AUTHOR]

In the ADM minimization problem the input is a set of arcs along a directed ring. The input arcs need to be partitioned into non-overlapping chains and cycles so as to minimize the total number of endpoints, where a k-arc cycle contributes k endpoints and a k-arc chain contains k+1 endpoints. We study ADM minimization problem both as non-cooperative and cooperative games. In these games each arc corresponds to a player, and the players share the cost of the ADM switches. We consider two cost allocation models, a model which was considered by Flammini et al., and a new cost allocation model, which is inspired by congestion games. We compare the price of anarchy and price of stability in the two cost allocation models, as well as the strong price of anarchy and the strong price of stability. [ABSTRACT FROM AUTHOR]

Following the work of Anily et al., we consider a variant of bin packing called bin packing with general cost structures (GCBP) and design an asymptotic fully polynomial time approximation scheme (AFPTAS) for this problem. In the classic bin packing problem, a set of one-dimensional items is to be assigned to subsets of total size at most 1, that is, to be packed into unit sized bins. However, in GCBP, the cost of a bin is not 1 as in classic bin packing, but it is a non-decreasing and concave function of the number of items packed in it, where the cost of an empty bin is zero. The construction of the AFPTAS requires novel techniques for dealing with small items, which are developed in this work. In addition, we develop a fast approximation algorithm which acts identically for all non-decreasing and concave functions, and has an asymptotic approximation ratio of 1.5 for all functions simultaneously. [ABSTRACT FROM AUTHOR]

We continue the study of bin packing with splittable items and cardinality constraints. In this problem, a set of n items must be packed into as few bins as possible. Items may be split, but each bin may contain at most k (parts of) items, where k is some given parameter. Complicating the problem further is the fact that items may be larger than 1, which is the size of a bin. The problem is known to be strongly NP-hard for any fixed value of k. We essentially close this problem by providing an efficient polynomial-time approximation scheme (EPTAS) for most of its versions. Namely, we present an efficient polynomial time approximation scheme for k= o( n). A PTAS for k=Θ( n) does not exist unless P = NP. Additionally, we present dual approximation schemes for k=2 and for constant values of k. Thus we show that for any ε>0, it is possible to pack the items into the optimal number of bins in polynomial time, if the algorithm may use bins of size 1+ ε. [ABSTRACT FROM AUTHOR]

We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke [Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, 2008, pp. 669-680] by devising a deterministic approach whose performance guarantee is 4.91 + ε. In addition, we study preemptive online algorithms, a class of algorithms related to one-pass semi-streaming algorithms, where we are allowed to maintain only a feasible matching in memory at any point in time. We provide a lower bound of 4.967 on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges that is not necessarily a feasible matching. We conclude by presenting an empirical study, conducted in order to compare the practical performance of our approach to that of previously suggested algorithms. [ABSTRACT FROM AUTHOR]

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 m identical machines, we show an upper bound of Hm-1 + 1 for a buffer of size - 1. A competitive ratio below Hm is not possible with any fixed buffer size, and it requires a buffer of size Ω(m/log m) to get a ratio of log Ω(log m). For uniformly related machines, we show that a buffer of size 1 is sufficient to get a competitive ratio of m, 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 already for identical machines, and it is impossible to obtain m an algorithm of finite competitive ratio in the other two models, even for m = 2. 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. [ABSTRACT FROM AUTHOR]

Abstract: We are given base elements and a finite collection of subsets of them. The size of any subset varies between to (). In addition, we assume that the input contains all possible subsets of size . Our objective is to find a subcollection of minimum-cardinality which covers all the elements. This problem is known to be NP-hard. We provide two approximation algorithms for it, one for the generic case, and an improved one for the special case of . The algorithm for the generic case is a greedy one, based on packing phases: at each phase we pick a collection of disjoint subsets covering new elements, starting from down to . At a final step we cover the remaining base elements by the subsets of size . We derive the exact performance guarantee of this algorithm for all values of and , which is less than , where is the ’th harmonic number. However, the algorithm exhibits the known improvement methods over the greedy one for the unweighted -set cover problem (in which subset sizes are only restricted not to exceed ), and hence it serves as a benchmark for our improved algorithm. The improved algorithm for the special case of is based on non-oblivious local search: it starts with a feasible cover, and then repeatedly tries to replace sets of size 3 and 4 so as to maximize an objective function which prefers big sets over small ones. For this case, our generic algorithm achieves an asymptotic approximation ratio of , and the local search algorithm achieves a better ratio, which is bounded by . [Copyright &y& Elsevier]

Abstract: We consider the following vertex coloring problem. We are given an undirected graph , where each vertex v is associated with a penalty rejection cost . We need to choose a subset of vertices, , and to find a proper coloring of the induced subgraph of G over . We are interested in both the number of colors used to color the vertices of , and in the total rejection cost of all other vertices. The goal is to minimize the sum of these two amounts. In this paper we consider both the online and the offline versions of this problem. In the online version, vertices arrive one at a time, revealing the rejection cost of the current vertex and the set of edges connecting it to previously revealed vertices. We also consider the classical online coloring problem on bounded degree graphs and on -claw free graphs. [ABSTRACT FROM AUTHOR]

In the process of reviewing and ranking projects by a group of reviewers, the allocation of the subset of projects to each reviewer has major impact on the robustness of the outcome ranking. We address here this problem where each reviewer is assigned, out of the list of all projects, a subset of up to k projects. Each individual reviewer then ranks and compares all pairs of k projects. The k-allocation problem is to determine an allocation of up to k projects to each reviewer, that lie within the expertise set of the reviewer, so that the resulting union of reviewed projects has certain desirable properties. The k-complete problem is a k-allocation with the property that all pairs of projects have been compared by at least one reviewer. A k-complete allocation is desirable as otherwise there may be projects that were not compared by any reviewer, leading to possible adverse properties in the outcome ranking. When a k-complete allocation cannot be achieved, one might settle for other properties. One basic requirement is that each pair of projects is comparable via a ranking path which is a sequence of pairwise rankings of projects implying a comparison of all pairs on the path. A k-allocation with a ranking path between each pair is the connectivity- k- aloc. Since the robustness of relative comparisons deteriorates with increased length of the ranking path, another goal is that between each pair of projects there will be at least one ranking path that has at most two hops or q hops for fixed values of q. An alternative means for increasing the robustness of the ranking is to use a k-allocation with at least p disjoint ranking paths between each pair. We model all these problems as graph problems. We demonstrate that the connectivity- k- aloc problem is polynomially solvable, using matroid intersection; we prove that the k-complete problem is NP-hard unless k = 2; and we provide approximation algorithms for a related optimization problem. All other variants are shown to be NP-complete for all values of k ≥ 2. [ABSTRACT FROM AUTHOR]

Abstract: Online interval selection is a problem in which intervals arrive one by one, sorted by their left endpoints. Each interval has a length and a non-negative weight associated with it. The goal is to select a non-overlapping set of intervals with maximal total weight and run them to completion. The decision regarding a possible selection of an arriving interval must be done immediately upon its arrival. The interval may be preempted later in favor of selecting an arriving overlapping interval, in which case the weight of the preempted interval is lost. We follow Woeginger (1994) and study the same models. The types of instances we consider are C-benevolent instances, where the weight of an interval is a monotonically increasing (convex) function of length, and D-benevolent instances, where the weight of an interval is a monotonically decreasing function of length. Some of our results can be extended to the case of unit length intervals with arbitrary costs. We significantly improve the previously known bounds on the performance of online randomized algorithms for the problem, namely, we introduce a new algorithm for the D-benevolent case and for unit intervals, which uses a parameter and has a competitive ratio of at most . This value is equal to approximately 2.4554 for being the solution of the equation . We further design a lower bound of on the competitive ratio of any randomized algorithm. The lower bound is valid for any C-benevolent instance, some D-benevolent functions and for unit intervals. We further show a lower bound of for a wider class of D-benevolent instances. This improves over previously known lower bounds. We also design a barely random online algorithm for the D-benevolent case and the case of unit intervals, which uses a single random bit, and has a competitive ratio of 3.22745. [Copyright &y& Elsevier]

We design improved approximation algorithms for two variants of the ADM minimization problem. SONET add-drop multiplexers (ADMs) are the dominant cost factor in SONET/WDM rings. The number of SONET ADMs required by a set of traffic streams (lightpaths) in a ring is determined by the routing and the wavelength assignment of the traffic streams. We consider both the arc version where the route of each traffic stream is given as input, and the chord version, where the routing is to be decided by the algorithm. The goal in both cases is to assign wavelengths so as to minimize the total number of used SONET ADMs. [ABSTRACT FROM AUTHOR]

Abstract: An optimization problem arising in the design of optical networks is shown here to be abstracted by the following model of covering the edges of a bipartite graph with a minimum number of 4-cycles, or : Given a bipartite graph over the node set with , and the implicit collection of all four-node cycles in the complete bipartite graph over . The goal is to cover all the edges in with a sub-collection of graphs , of minimum size, where each is a subgraph of a cycle over four nodes — a 4-cycle. Since a subgraph of a 4-cycle can cover up to 4 edges, this covering problem is a special case of the unweighted 4-set cover problem. This specialization allows us to obtain an improved approximation guarantee. Whereas the currently best known approximation algorithm for the general unweighted 4-set cover problem has an approximation ratio of (where denotes the -th harmonic number), we show that, for every , there is a polynomial time -approximation algorithm for our problem. Our analysis of the greedy algorithm shows that, when applied to covering a bipartite graph using copies of bicliques, it returns a feasible solution whose cost is at most where denotes the optimal cost, thus improving the approximation bound for unweighted -set cover by a factor of almost 2. [Copyright &y& Elsevier]

Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property cannot be maintained with respect to optimal solutions. [ABSTRACT FROM AUTHOR]

Abstract: SONET add-drop multiplexers (ADMs) are the dominant cost factor in SONET/WDM rings. The number of SONET ADMs required by a set of traffic streams is determined by the routing and wavelength assignment of the traffic streams. Following previous work, we consider the problem where the route of each traffic stream is given as input, and we need to assign wavelengths so as to minimize the total number of used SONET ADMs. This problem is known to be NP-hard, and the best known approximation algorithm for this problem has a performance guarantee of . We improve this result, and present a -approximation algorithm. We also study some of the previously proposed algorithms for this problem, and give either tight or tighter analysis of their approximation ratio. [Copyright &y& Elsevier]

Abstract: Online unit clustering is a clustering problem where classification of points is done in an online fashion, but the exact location of clusters can be modified dynamically. We study several variants and generalizations of the online unit clustering problem, which are inspired by variants of packing and scheduling problems in the literature. [Copyright &y& Elsevier]

We consider the offline and online versions of a bin packing problem called bin packing with conflicts. Given a set of items V = {1, 2, . . . ,n} with sizes s1, s2, . . . , sn ∈ [0, 1] and a conflict graph G = (V,E), the goal is to find a partition of the items into independent sets of G, where the total size of items in each independent set is at most 1 so that the number of independent sets in the partition is minimized. This problem is clearly a generalization of both the classical (one-dimensional) bin packing problem where E = ø and of the graph coloring problem where si = 0 for all i = 1, 2, . . . , n. Since coloring problems on general graphs are hard to approximate, following previous work, we study the problem on specific graph classes. For the offline version, we design improved approximation algorithms for perfect graphs and other special classes of graphs: These are a 5÷2 = 2.5-approximation algorithm for perfect graphs; a 7÷3 ≈ 2.33333-approximation algorithm for a subclass of perfect graphs, which contains interval graphs and chordal graphs; and a 7÷4 = 1.75-approximation for algorithm bipartite graphs. For the online problem on interval graphs, we design a 4.7-competitive algorithm and show a lower bound of 155÷36 ≈ 4.30556 on the competitive ratio of any algorithm. To derive the last lower bound, we introduce the first lower bound on the asymptotic competitive ratio of any online bin packing algorithm with known optimal value, which is 47÷36 ≈ 1.30556. [ABSTRACT FROM AUTHOR]

We study the two-dimensional version of the bin packing problem with conflicts. We are given a set of (two-dimensional) squares V = {1, 2, . . . , n} with sides $${s_1, s_2 \ldots ,s_n \in [0,1]}$$ and a conflict graph G = ( V, E). We seek to find a partition of the items into independent sets of G, where each independent set can be packed into a unit square bin, such that no two squares packed together in one bin overlap. The goal is to minimize the number of independent sets in the partition. This problem generalizes the square packing problem (in which we have $${E = \emptyset}$$ ) and the graph coloring problem (in which s i = 0 for all i = 1,2, . . . , s n). It is well known that coloring problems on general graphs are hard to approximate. Following previous work on the one-dimensional problem, we study the problem on specific graph classes, namely, bipartite graphs and perfect graphs. We design a $${2+\varepsilon}$$ -approximation for bipartite graphs, which is almost best possible (unless P = NP). For perfect graphs, we design a 3.2744-approximation. [ABSTRACT FROM AUTHOR]

Bin packing is a well-known problem which has a large number of applications. Classical bin packing is a simple model in which all bins are identical. In the bin packing problem with variable-sized bins, we are given a supply of a variety of sizes. This latter model assumes, however, that the cost of a bin is always defined to be its exact size. In this paper we study the more general problem where an available bin size is associated with a fixed cost, which may be smaller or larger than its size. The costs of different bin sizes are unrelated. This generalized problem has various applications in storage and scheduling. In order to generalize previous work, we design new rounding and allocation methods. Our main result is an asymptotic polynomial time approximation scheme for the generalized problem. [ABSTRACT FROM AUTHOR]

We give a 7.18-approximation algorithm for the minimum latency problem that uses only O(n log n) calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the k-minimum spanning tree (k-MST) problem which is called as a black box for each value of k. Their algorithm can achieve an approximation factor of 10.77 while making O(n(n + log C) log n) PCST calls, a factor of 8.98 using O(n³ (n + log C) log n) PCST calls, or a factor of 7.18 + ϵ using nO(1/ϵ) log C PCST calls, via the k-MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here n denotes the number of nodes in the instance, and C is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in O(n²) time, the overall running time of our algorithm is O(n³ log n). We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only O(log² n) PCST calls, and derandomize it to obtain a deterministic algorithm with factor 7.18 + ϵ, using O( 1/ϵ log² n) PCST calls. The basic idea for our improvement is that we do not treat the k-MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate k-MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate k-MSTs for all values of k, even though we have them only for some values of k that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem. [ABSTRACT FROM AUTHOR]

Abstract: Given a graph with a cost function , we want to represent all possible min-cut values between pairs of vertices and . We consider also the special case with an additive cost where there are vertex capacities , and for a subset , . We consider two variants of cuts: in the first one, separation, and are feasible cuts that disconnect and . In the second variant, vertex-cut, a cut-set that disconnects from does not include or . We consider both variants for undirected and directed graphs. We prove that there is a flow-tree for separations in undirected graphs. We also show that a compact representation does not exist for vertex-cuts in undirected graphs, even with additive costs. For directed graphs, a compact representation of the cut-values does not exist even with additive costs, for neither the separation nor the vertex-cut cases. [Copyright &y& Elsevier]

Abstract: Let be an undirected tree, in which each edge is associated with a non-negative cost, and let be a collection of k distinct pairs of vertices. Given a requirement parameter , the partial multicut on a tree problem asks to find a minimum cost set of edges whose removal from T disconnects at least t out of these k pairs. This problem generalizes the well-known multicut on a tree problem, in which we are required to disconnect all given pairs. The main contribution of this paper is an -approximation algorithm for partial multicut on a tree, whose run time is strongly polynomial for any fixed . This result is achieved by introducing problem-specific insight to the general framework of using the Lagrangian relaxation technique in approximation algorithms. Our algorithm utilizes a heuristic for the closely related prize-collecting variant, in which we are not required to disconnect all pairs, but rather incur penalties for failing to do so. We provide a Lagrangian multiplier preserving algorithm for the latter problem, with an approximation factor of 2. Finally, we present a new 2-approximation algorithm for multicut on a tree, based on LP-rounding. [Copyright &y& Elsevier]

We consider packing and covering optimization problems over constraints in consecutive and circular 1's. Such problems arise in the context of shift scheduling, and in problems related to interval graphs. Previous approaches to this problem depended on solving several minimum cost network flow problems. We devise here substantially more efficient and strongly polynomial algorithms based on parametric shortest paths approaches. The objective function in the covering and packing problems is to either minimize or maximize the number of sets that satisfy the constraints. The various problems studied are classified according to whether the constraints are all consecutive 1's or if there are also circular 1's constraints, and according to whether the constraints are all of covering type; all of packing type, or mixed. The running time of our algorithm for a pure covering all consecutive 1's constraints problem on n variables and m constraints is O(m + n). For the pure packing problem with consecutive 1's constraints we present an O(m + n log n) time algorithm. For the "mixed" case with both covering and packing consecutive 1's constraints we present an O(mn) time algorithm. An O(mn + n² log n)-time algorithm is presented for the case where the constraints are circular (consecutive 1's constraint is also circular) of pure type--either all covering constraints or all packing constraints. Finally, we show an O(n min{mn, n² log n + m log² n}) time algorithm for the most general problem of mixed covering and packing case where the constraints are circular. All our algorithms are strongly polynomial and improve on the nonstrongly polynomial parametric minimum cost network flow or the (strongly polynomial) linear programming known approaches. [ABSTRACT FROM AUTHOR]

Abstract: Cellular telephony systems, where locations of mobile users are unknown at some times, are becoming more common. In such systems, mobile users are roaming in a zone and a user reports its location only if it leaves the zone entirely. The conference call search (CCS) problem deals with tracking a set of mobile users in order to establish a call. To find a single roaming user, the system may need to search each cell where the user may be located. The goal is to identify the location of all users, within bounded time, satisfying some additional constraints on the search scheme. We consider cellular systems with cells and mobile users (cellular phones). The uncertain location of users is given by probability distribution vectors. Whenever the system needs to find the users, it conducts a search operation lasting at most rounds. A request for a single search step specifies a user and a cell. In this search step, the cell is asked whether the given user is located there. In each round the system may perform an arbitrary number of such requests. An integer number bounds the number of distinct requests per cell in every round. The bound results from quality of service considerations, whereas the bound results from the wireless bandwidth allocated for signaling being scarce. Every search step consumes expensive wireless links, which motivates search techniques minimizing the expected number of requests thus reducing the total search costs. We distinguish between oblivious, semi-adaptive and adaptive search protocols. An oblivious search protocol decides on all requests in advance, and stops only when all users are found. A semi-adaptive search protocol decides on all the requests in advance, but it stops searching for a user once it is found. An adaptive search protocol stops searching for a user once it has been found (and its search strategy may depend on the subsets of users that were found in each previous round). We establish the difference between those three search models. We show that for oblivious “single query per cell” systems (), and a tight environment (), it is NP-hard to compute an optimal solution (the case was proven to be NP-hard already by Bar-Noy and Naor) and we develop a PTAS for these cases (for fixed values of ). However, we show that semi-adaptive systems allow polynomial time algorithms. This last result also shows that the case and is polynomially solvable also for adaptive search systems, answering an open question of Bar-Noy and Naor. [Copyright &y& Elsevier]

We consider the problem of minimizing the weighted sum of job completion times on a single machine (subject to certain job weights) with an additional side constraint on the weighted sum of job completion times (with respect to different job weights). This problem is NP-hard, and we provide a polynomial time approximation scheme for this problem. Our method is based on Lagrangian relaxation mixed with carefully guessing the positions of certain jobs in the schedule. [ABSTRACT FROM AUTHOR]

Abstract: We consider a problem which arises in optical routing. WDM/SONET rings are a network architecture used by telecommunications carriers for traffic streams. The dominant cost factor in such networks is the total number of add-drop multiplexers (ADMs) used. A list of traffic streams to be routed between pairs of nodes is given. In this paper we consider the problem where we need to assign a route and a wavelength to each traffic stream, minimizing the total number of used SONET ADMs. This is called the chord version of the SONET ADMs minimization problem, to denote the fact that the routing is not given a priori. The best previously known approximation algorithms for this problem have the performance guarantee of . We present an improved algorithm with performance guarantee of exactly . Moreover, we study some natural heuristics for this problem, and give tight analysis of their approximation ratios. [Copyright &y& Elsevier]

In the weighted set-cover problem we are given a set of elements $E=\{ e_1,e_2, \ldots ,e_n \}$ and a collection $\cal F$ of subsets of $E$, where each $S \in \cal F$ has a positive cost $c_{S}$. The problem is to compute a subcollection $SOL$ such that $\bigcup_{S\in SOL}S_j=E$ and its cost $\sum_{S\in SOL}c_S$ is minimized. When $|S|\le k\ \forall S\in\cal F$ we obtain the weighted $k$-set cover problem. It is well known that the greedy algorithm is an $H_k$-approximation algorithm for the weighted $k$ set cover, where $H_k=\sum_{i=1}^k {1 \over i}$ is the $k$th harmonic number, and that this bound is exact for the greedy algorithm for all constant values of $k$. In this paper we give the first improvement on this approximation ratio for all constant values of $k$. This result shows that the greedy algorithm is not the best possible for approximating the weighted set cover problem. Our method is a modification of the greedy algorithm that allows the algorithm to regret. [ABSTRACT FROM AUTHOR]