Search

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]

In bin packing with cardinality constraints (BPCC), there is an upper bound k ≥ 2 on the number of items that can be packed into each bin, additionally to the standard constraint on the total size of items. We study the algorithm First Fit (FF), acting on a list of items, packing each item into the minimum indexed bin that contains at most k − 1 items and has sufficient space for the item. We present a complete analysis of its asymptotic approximation ratio for all values of k . Many years after FF for BPCC was introduced, its tight asymptotic approximation ratio is finally found. [ABSTRACT FROM AUTHOR]

In the file caching problem, the input is a sequence of requests for files out of a slow memory. A file has two attributes, a positive retrieval cost and an integer size. An algorithm is required to maintain a cache of size k such that the total size of files stored in the cache never exceeds k. Given a request for a file that is not present in the cache at the time of request, the file must be brought from the slow memory into the cache, possibly evicting other files from the cache. This incurs a cost equal to the retrieval cost of the requested file. Well-known special cases include paging (all costs and sizes are equal to 1), the cost model, which is also known as weighted paging, (all sizes are equal to 1), the fault model (all costs are equal to 1), and the bit model (the cost of a file is equal to its size). If bypassing is allowed, a miss for a file still results in an access to this file in the slow memory, but its subsequent insertion into the cache is optional. We study a new online variant of caching, called caching with rejection. In this variant, each request for a file has a rejection penalty associated with the request. The penalty of a request is given to the algorithm together with the request. When a file that is not present in the cache is requested, the algorithm must either bring the file into the cache, paying the retrieval cost of the file, or reject the file, paying the rejection penalty of the request. The objective function is the sum of total rejection penalty and the total retrieval cost. This problem generalizes both caching and caching with bypassing. We design deterministic and randomized algorithms for this problem. The competitive ratio of the randomized algorithm is O(log k), and this is optimal up to a constant factor. In the deterministic case, a k-competitive algorithm for caching, and a ( k+1)-competitive algorithm for caching with bypassing are known. Moreover, these are the best possible competitive ratios. In contrast, we present a lower bound of 2 k+1 on the competitive ratio of any deterministic algorithm for the variant with rejection. The lower bound is valid already for paging. We design a (2 k+2)-competitive algorithm for caching with rejection. We also design a different (2 k+1)-competitive algorithm, that can be used for paging and for caching in the bit and fault models. [ABSTRACT FROM AUTHOR]

Motivated by fundamental optimization problems in video delivery over wireless networks, we consider the following problem of packing resizable items ( PRI ). Given is a bin of capacity B > 0 , and a set I of items. Each item j ∈ I has a size s j > 0 . A packed item must stay in the bin for a fixed common time interval. To accommodate additional items in the bin, each item j can be compressed to a given size p j ∈ [ 0 , s j ) for at most a fraction q j ∈ [ 0 , 1 ) of the packing interval, during one continuous sub-interval. The goal is to pack in the bin, for the given time interval, a subset of items of maximum cardinality. PRI is a generalization of the well-known Knapsack problem, and it is strongly NP-hard already for highly restricted instances. Our main result is an approximation algorithm that packs, for any instance I of PRI , at least 2 3 OPT ( I ) − 2 items, where OPT ( I ) is the number of items packed in an optimal solution. Our algorithm yields a better performance ratio for instances in which the maximum compression time of an item is q max ∈ ( 0 , 1 2 ) . For subclasses of instances arising in realistic scenarios, we give an algorithm that packs at least OPT ( I ) − 2 items. Finally, we show that a non-trivial subclass of instances admits an asymptotic fully polynomial time approximation scheme ( AFPTAS ). [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 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]

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]

Abstract: It is well known that the two simple algorithms for the classic bin packing problem, and both have an approximation ratio of . However, seems to be a more reasonable algorithm, since it never opens a new bin if an existing bin can still be used. Using resource augmented analysis, where the output of an approximation algorithm, which can use bins of size , is compared to an optimal packing into bins of size , we give a complete analysis of the asymptotic approximation ratio of and of , and use it to show that is strictly better than for any , while they have the same asymptotic performance guarantee for all , and for . [Copyright &y& Elsevier]

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]

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]

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]

The original version of the article was inadvertently published with misinterpretations on author's proof corrections on mathematical expressions. [ABSTRACT FROM AUTHOR]