Search

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]

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]

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]

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]

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]

In the online capacitated interval coloring problem, a sequence of requests arrive online. Each request is an interval Ij ⊆ {1, 2,…, n} with bandwidth bj . We are initially given a vector of capacities (c1, c2,…, cn). Each color can support a set of requests such that the total bandwidth of intervals containing i is at most ci. 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 bmax = maxj bj is at most the minimum capacity cmin = mini ci. For the case bmax > cmin, we give an algorithm with competitive ratio O(log bmax/cmin) 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. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

Given an undirected graph G = (V, E) with |V| = n and |E| = m, nonnegative integers Ce and de for each edge e ϵ E, and a bound D, the constrained minimum spanning tree problem (CST) is to find a spanning tree T = (V, ET such that ΣeϵET de ≤ D and ΣeϵET ce is minimized. We present an efficient polynomial time approximation algorithm with time complexity O((&frac1c;)O(&frac;1c;)n4. Our method is based on Lagrangian relaxation and matroid intersection. [ABSTRACT FROM AUTHOR]