Search

Abstract: This paper shows an asymptotically tight analysis of the Certified Write-All algorithm called AWT that was introduced by Anderson and Woll, SIAM J. Comput. 26 (1997) 1277, and a method for creating near-optimal instances of the algorithm. This algorithm is the best known deterministic algorithm that can be used to simulate n synchronous parallel processors on n asynchronous processors. The algorithm is instantiated with q permutations on , where q can be chosen from a wide range of values. When implementing a simulation on a specific parallel system with n processors, one would like to select the best possible value of q and the best possible q permutations, in order to maximize the efficiency of the simulation. This paper shows that work complexity of any instance of AWT is , where q is the number of permutations selected, and C is a value related to their combinatorial properties. The choice of q turns out to be critical for obtaining an instance of the AWT algorithm with near-optimal work. For any , and any large enough n, work of any instance of the algorithm must be at least . Under certain conditions, however, that q is about and for infinitely many large enough n, this lower bound can be nearly attained by instances of the algorithm that use certain q permutations and have work at most . The paper also shows a penalty for not selecting q well. When q is significantly away from , then work of any instance of the algorithm with this displaced q must be considerably higher than otherwise. [Copyright &y& Elsevier]

Abstract: A graph is called an interval graph if there exists a set of intervals corresponding to the vertex set of and two vertices are adjacent to each other if and only if the two corresponding intervals are intersecting with each other. In this paper, we apply the reliability-based backup 2-center modal proposed by Wang, Wu and Chao, in which each server may fail with a given probability, to interval graphs and present an time algorithm. [Copyright &y& Elsevier]

Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given. [Copyright &y& Elsevier]

Abstract: This paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary times. We want to pack a sequence of unit fractions items (i.e., items with sizes for some integer ) into unit-size bins, such that the maximum number of bins ever used over all time is minimized. Tight and almost-tight performance bounds are found for the family of any-fit algorithms, including first-fit, best-fit, and worst-fit. In particular, we show that the competitive ratio of best-fit and worst-fit is 3, which is tight, and the competitive ratio of first-fit lies between 2.45 and 2.4942. We also show that no on-line algorithm is better than 2.428-competitive. [Copyright &y& Elsevier]