We consider ordinal scheduling on identical parallel machines with cardinality constraints. That is, a parameter k=1 is given such that no machine can contain more than k jobs. The objective is to assign the jobs to machines such that the makespan is minimized. In the ordinal setting, jobs are presented one by one and it is known that they arrive sorted by non-increasing sizes, but the specific sizes become known only after termination of the algorithm. An ordinal algorithm is compared to an optimal offline algorithm that knows all sizes, but it can also assign at most k jobs to each machine. Several simple algorithms achieve a competitive ratio of 2. In this work, we improve this ratio using a carefully designed algorithm.

Scheduling of independent jobs with release dates so as to minimize the total weighted completion time is a well-known scheduling problem. Here, we study it for the classic machine environment of uniformly related machines. An efficient polynomial time approximation scheme (an EPTAS) is a family of (1+ε)-approximation algorithms where the running time is bounded by a polynomial in the input size times a function of ε > 0. For problems that are NP-hard in the strong sense, as it is the case for the problem studied here, an EPTAS is the best possible approximation scheme. We design an EPTAS for the problem by employing known techniques and introducing a large collection of new methods.

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 𝓁_𝔭 norm for a fixed 𝔭 > 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 𝓁_𝔭 norm minimization for any 𝔭 > 1.

We study a classic scheduling problem on uniformly related machines for which we show an efficient polynomial time approximation scheme (EPTAS), where an EPTAS is a fast and practical approximation scheme. For a desired approximation ratio of 1+ε for ε > 0, the running time of an EPTAS is a function of ε multiplied by a polynomial function of the input length. 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 an EPTAS for the scheduling problem of a set of jobs on uniformly related machines so as to minimize the total weighted completion time. The problem is NP-hard in the strong sense, and therefore an EPTAS is the best possible approximation scheme for the problem, unless P=NP. Prior to our work, only a PTAS was known for the problem, while an EPTAS was known only for the special case of identical machines.

Abstract 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 $$\varDelta $$ Δ , 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+\varDelta $$ 1 + Δ . Our goal is to maximize the number of near exact covered bins. If $$\varDelta =0$$ Δ = 0 or $$\varDelta >0$$ Δ > 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\ne NP$$ P ≠ N P ). However, for the case where $$\varDelta >0$$ Δ > 0 is seen as a constant, we present an asymptotic fully polynomial time approximation scheme (AFPTAS) that is our main contribution.

Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. A well-studied measure of the amount of decisions that can be revoked is the (constant) migration factor. When an object arrives, the decisions for objects of total size at most the migration factor times its size may be revoked. This means that a small object only leads to small changes. 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. We therefore resolve the competitiveness of the bin covering problem with migration.

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. More specifically, we show that in both cases, one can get a competitive ratio that is strictly lower than 2, which is the bound from the standard online setting. On the other hand, we prove that no PTAS is possible.

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 $Ω(\sqrt{d})$. Our main result is that the lower bound of $Ω(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.

Bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k ≥ 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 and prove a lower bound of 2 on the overall asymptotic competitive ratio. 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. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, where no such lower bound was known even for fixed high dimensions.

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.

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.

The theory of $n$-fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an $n$-fold integer program (IP) consists of parameter $A$, dimension $n$, and numerical data of binary encoding length $L$. It was known for some time that such programs can be solved in polynomial time using $O(n^{g(A)}L)$ arithmetic operations where $g$ is an exponential function of the parameter. In 2013 it was shown that it can be solved in fixed-parameter tractable (FPT) time using $O(f(A)n^3L)$ arithmetic operations for a single-exponential function $f$. This, and a faster algorithm for a special case of combinatorial $n$-fold IP, have led to several very recent breakthroughs in the parameterized complexity of scheduling, stringology, and computational social choice. In 2015 it was shown that it can be solved in strongly polynomial time using $O(n^{g(A)})$ arithmetic operations. Here we establish a result which subsumes all three of the above results by showing that $n$-fold IP can be solved in strongly polynomial FPT time using $O(f(A)n^3)$ arithmetic operations. In fact, our results are much more general, briefly outlined as follows. - There is a strongly polynomial algorithm for ILP whenever a so-called Graver-best oracle is realizable for it. - Graver-best oracles for the large classes of multi-stage stochastic and tree-fold ILPs can be realized in FPT time. Together with the previous oracle algorithm, this newly shows two large classes of ILP to be strongly polynomial; in contrast, only few classes of ILP were previously known to be strongly polynomial. - We show that ILP is FPT parameterized by the largest coefficient $\|A\|_\infty$ and the primal or dual treedepth of $A$, and that this parameterization cannot be relaxed, signifying substantial progress in understanding the parameterized complexity of ILP.

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 multihypergraphs 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.

Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k >= 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 the long standing open problem of finding the value of the best possible overall asymptotic competitive ratio, since an algorithm of an absolute competitive ratio 2 for any fixed value of k 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. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, and thus provide for the first time a lower bound larger than 2 on the asymptotic competitive ratio for the vector packing problem in any fixed dimension.

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\geq 2$ uniformly related machines, showing that its value for m=2 is equal to 1.2, and its overall value is approximately 1.39795.

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.

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: - We provide a lower bound of 1 + ln 2 \approx 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) \approx 1.581 due to Karp, Vazirani, and Vazirani [STOC'90]. - 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} \approx 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].

The k‐opt heuristics are among the most common techniques for approaching the traveling salesman problem (TSP). They are used either directly or as subroutines in more sophisticated heuristics, such as the celebrated Lin–Kernighan heuristic. The value of k is typically 2 or 3. In this article, we modify the 2‐opt heuristic to be based on a function f of the distances rather than the distances solely. This may be viewed as modifying the local search with the 2‐change neighborhood to be nonoblivious. We denote the corresponding heuristic by (2, f)‐opt. We provide theoretical performance guarantees for it: both lower and upper bounds based on the ones given by Chandra et al. [SIAM J Comput 28 (1999), 1998–2029], obtained originally for the standard 2‐opt heuristic. By a tighter analysis of the neighborhood size, we improve their upper bound for the standard 2‐opt by a factor of , and we show that these bounds hold for (2, f)‐opt for any nonnegative, increasing function f. We then provide experimental evidence based on TSPLIB benchmark problems, showing that (2, f)‐opt with for various values of significantly outperforms 2‐opt. These values of r also depend on the method chosen for constructing the initial tours. Specifically, when the initial tours are random permutations, the improvement over 2‐opt is more than 35% for ; when they are generated by the Nearest Neighbor heuristic, it is about 10% for r = 0.5, 0.55, 0.6. We also see that the average length of the tour generated by (2, f)‐opt is relatively close to the optimum or the known bound. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 62(3), 201–219 2013

Finding a largest Order-Preserving SubMatrix, OPSM, is an important problem arising in the discovery of patterns in gene expression. Ben-Dor et al. formulated the problem in Ben-Dor et al. [2003]. They further showed that the problem is NP-complete and provided a greedy heuristic for the problem. The complement of the OPSM problem, called MinOPSM, is to delete the least number of entries in the matrix so that the remaining submatrix is order preserving. We devise a 5-approximation algorithm for the MinOPSM based on a formulation of the problem as a quadratic, nonseparable set cover problem. An alternative formulation combined with a primal-dual algorithm improves the approximation factor to 3. The complexity of both algorithms for a matrix of size m × n is O ( m 2 n ). We further comment on the related biclustering problem.

We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. Our objective is to minimize $\sum w_jf(C_j)$ for any nondecreasing, nonnegative, differentiable cost function $f(C_j)$. 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 $\Omega(\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.

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 [Formula: see text]. 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.

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.

A token is hidden in one of several boxes and then the boxes are locked. The probability of placing the token in each of the boxes is known. A searcher is looking for the token by unlocking boxes where each box is associated with an unlocking cost. The searcher conducts its search in rounds and must find the token in a predetermined number of rounds. In each round, the searcher may unlock any set of locked boxes concurrently. The optimization goal is to minimize the expected cost of unlocking boxes until the token is found. The motivation and main application of this game is the task of paging a mobile user (token) who is roaming in a zone of cells (boxes) in a cellular network system. Here, the unlocking costs reflect cell congestions and the placing probabilities represent the likelihood of the user residing in particular cells. Another application is the task of finding some data (token) that may be known to one of the sensors (boxes) of a sensor network. Here, the unlocking costs reflect the energy consumption of querying sensors and the placing probabilities represent the likelihood of the data being found in particular sensors. In general, we call mobile data any entity that has to be searched for.

We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc.\ STACS~'08, pages 669--680) by devising a deterministic approach whose performance guarantee is $4.91 + \eps$. In addition, we study {\em preemptive} online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. 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 which 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 The facility terminal cover problem is a generalization of the vertex cover problem. The problem is to “cover” the edges of an undirected graphG= (V,E) where each edgeeis associated with a non‐negative demandde. An edgee=u,vis covered if at least one of its endpoint vertices is allocated capacity of at leastde. Each vertexvis associated with a non‐negative weightwv. The goal is to allocate capacitycv≥ 0 to each vertexvso that all edges are covered and the total allocation cost,$\sum\limits_{v\in V}w_{v}c_{v}$, is minimized. A recent paper by Xu et al. [Networks 50 (2007), 118‐126], studied this problem, and presented a 2e‐ approximation algorithm for this problem forethe base of the natural logarithm. We generalize here the facility terminal cover problem to the multi‐integer set cover, and relate that problem to the set cover problem, which it generalizes, and the multi‐cover problem. We present a Δ‐approximation algorithm for the multi‐integer set cover problem, for Δ the maximum coverage. This demonstrates that even though the multi‐integer set cover problem generalizes the set cover problem, the same approximation ratio holds. In the special case of the facility terminal cover problem this yields a 2‐approximation algorithm, and with run time dominated by the sorting of the edge demands. This approximation algorithm improves considerably on the result of Xu et al. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

In the online capacitated interval coloring problem, a sequence of requests arrive online. Each request is an interval $I_j\subseteq\{1,2,\dots,n\}$ with bandwidth $b_j$. We are initially given a vector of capacities $(c_1,c_2,\dots,c_n)$. Each color can support a set of requests such that the total bandwidth of intervals containing i is at most $c_i$. The goal is to color the requests using a minimum number of colors. We present a constant competitive algorithm for the case where the maximum bandwidth $b_{\mathrm{max}}=\max_j b_j$ is at most the minimum capacity $c_{\mathrm{min}}=\min_i c_i$. For the case $b_{\mathrm{max}}>c_{\mathrm{min}}$, we give an algorithm with competitive ratio $O(\log\frac{b_{\mathrm{max}}}{c_{\mathrm{min}}})$ and, using resource augmentation, a constant competitive algorithm. We also give a lower bound showing that a constant competitive ratio cannot be achieved in the general case without resource augmentation.

We consider the well-known minimum quadratic assignment problem. In this problem we are given two n × n nonnegative symmetric matrices A = ( a ij ) and B = ( b ij ). The objective is to compute a permutation π of V = {1,…, n } so that ∑ i , j ∈ V i ≠ j a π( i ),π( j ) b i , j is minimized. We assume that A is a 0/1 incidence matrix of a graph, and that B satisfies the triangle inequality. We analyze the approximability of this class of problems by providing polynomial bounded approximations for some special cases, and inapproximability results for other cases.

We consider the problems of set partitioning into k clusters with minimum total cost and minimum of the maximum cost of a cluster. The cost function is given by an oracle, and we assume that it satisfies some natural structural constraints. That is, we assume that the cost function is monotone, the cost of a singleton is zero, and we assume that for all S ∩ S′ ≠ ∅ the following holds c ( S ) + c ( S ′) ≥ c ( S ∪ S ′). For the problem of minimizing the maximum cost of a cluster we present a (2 k − 1)-approximation algorithm for k ≥ 3, a 2-approximation algorithm for k = 2, and we also show a lower bound of k on the performance guarantee of any polynomial-time algorithm. For the problem of minimizing the total cost of all the clusters, we present a 2-approximation algorithm for the case where k is a fixed constant, a (4 k − 3)-approximation where k is unbounded, and we show a lower bound of 2 on the approximation ratio of any polynomial-time algorithm. Our lower bounds do not depend on the common assumption that P ≠ NP .

Abstract For a fixed pattern graph H, let H‐CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. This paper is part I of our study on the computational complexity of the H‐CONTRACTIBILITY problem. We continue a line of research that was started in 1987 by Brouwer and Veldman, and we determine the computational complexity of the H‐CONTRACTIBILITY problem for certain classes of pattern graphs. In particular, we pinpoint the complexity for all graphs H with five vertices except for two graphs, whose polynomial time algorithms are presented in part II. Interestingly, in all connected cases that are known to be polynomially solvable, the pattern graph H has a dominating vertex, whereas in all cases that are known to be NP‐complete, the pattern graph H does not have a dominating vertex. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract For a fixed pattern graph H, let H‐CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. This article is part II of our study on the computational complexity of the H‐CONTRACTIBILITY problem. In the first article we pinpointed the complexity for all pattern graphs with five vertices except for two pattern graphs H. Here, we present polynomial time algorithms for these two remaining pattern graphs. Interestingly, in all connected cases that are known to be polynomially solvable, the pattern graph H has a dominating vertex, whereas in all cases that are known to be NP‐complete, the pattern graph H does not have a dominating vertex. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

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^3(n+\log C) \log n)$ PCST calls, or a factor of $7.18+\epsilon$ using $n^{O(1/\epsilon)}\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^2)$ time, the overall running time of our algorithm is $O(n^3 \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^2 n)$ PCST calls, and derandomize it to obtain a deterministic algorithm with factor $7.18+\epsilon$, using $O(\frac{1}{\epsilon} \log^2 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.

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.

In the unweighted 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. The problem is to compute a subcollection $SOL\subseteq{\cal F}$ such that $\bigcup_{S_j\in SOL}S_j=E$ and its size $|SOL|$ is minimized. When $|S|\leq k$ for all $S\in{\cal F}$, we obtain the unweighted k-set cover problem. It is well known that the greedy algorithm is an $H_k$-approximation algorithm for the unweighted k-set cover, where $H_k=\sum_{i=1}^k\frac{1}{i}$ is the kth harmonic number and that this bound on the approximation ratio of the greedy algorithm is tight for all constant values of k. Since the set cover problem is a fundamental problem, there is an ongoing research effort to improve this approximation ratio using modifications of the greedy algorithm. The previous best improvement of the greedy algorithm is an $(H_k-\frac{1}{2})$-approximation algorithm. In this paper we present a new $(H_k-\frac{196}{390})$-approximation algorithm for $k\geq4$ that improves the previous best approximation ratio for all values of $k\geq4$. Our algorithm is based on combining a local search during various stages of the greedy algorithm.

Let G = ( V , E ) be an undirected graph, with three numbers d 0 ( e ) ≥ d 1 ( e ) ≥ d 2 ( e ) ≥ 0 for each edge e ∈ E . A solution is a subset U ⊆ V and d i ( e ) represents the cost contributed to the solution by the edge e if exactly i of its endpoints are in the solution. The cost of including a vertex v in the solution is c ( v ). A solution has cost that is equal to the sum of the vertex costs and the edge costs. The minimum generalized vertex cover problem is to compute a minimum cost set of vertices. We study the complexity of the problem with the costs d 0 ( e ) = 1, d 1 ( e ) = α and d 2 ( e ) = 0 ∀ e ∈ E and c ( v ) = β∀ v ∈ V , for all possible values of α and β. We also provide 2-approximation algorithms for the general case.

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 kth 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.

Given an undirected graph G=(V,E) with |V|=n and |E|=m, nonnegative integers c e and d e for each edge $e \in E$, and a bound D, the constrained minimum spanning tree problem (CST) is to find a spanning tree T=(V,E T ) such that $\sum_{e \in E_T} d_e \leq D$ and $\sum_{e \in E_T} c_e$ is minimized. We present an efficient polynomial time approximation scheme (EPTAS) for this problem. Specifically, for every $\epsilon>0$ we present a $(1+\epsilon)$-approximation algorithm with time complexity $O((\frac{1}{\epsilon})^{O(\frac{1}{\epsilon})}n^4)$. Our method is based on Lagrangian relaxation and matroid intersection.

Abstract Motivated by a problem arising in the design of telecommunications networks using the SONET standard, we consider the problem of covering all edges of a graph using subgraphs that contain at most k edges with the objective of minimizing the total number of vertices in the subgraphs. We show that the problem is 𝒩 𝒫 ‐hard when k ≥ 3 and present a linear‐time ‐approximation algorithm. For even k values, we present an approximation scheme with a reduced ratio but with increased complexity. © 2002 Wiley Periodicals, Inc.

Abstract Consider a requirement graph whose vertices represent customers and an edge represents the need to route a unit of flow between its end vertices along a single path. All these flows are to be routed simultaneously. A solution network consists of a (multi)graph on the same set of vertices, such that it is possible to route simultaneously all of the required flows in such a way that no edge is used more than K times. The SYNTHESIS OF WAVELENGTH ROUTING NETWORK (SWRN) problem is to compute a solution network of a minimum number of edges. This problem has significant importance in the world of fiber‐optic networks where a link can carry a limited amount of different wavelengths and one is interested in finding a minimum‐cost network such that all the requirements can be carried in the network without changing the wavelength of a path at any of its internal vertices. In this paper, we prove that the SWRN problem is NP‐hard for any constant K (K ≥ 2). Then, we assume that GR is a clique with n vertices and we find an “almost” optimal solution network for all values of K (K = o(n)) and present a Min{(K + 1)/2, 2 + 2/(K − 1)}‐approximation algorithm for the general case and a 2‐approximation algorithm for d‐regular graphs. © 2002 Wiley Periodicals, Inc.