Search

Abstract: In this paper we consider the unsplittable flow problem (UFP): given a directed or undirected network with edge capacities and a set of terminal pairs (or requests) with associated demands, find a subset of the pairs of maximum total demand for which a single flow path can be chosen for each pair so that for every edge, the sum of the demands of the paths crossing the edge does not exceed its capacity. We present a collection of new results for the UFP both in the offline (all requests are given from the beginning) and the online (requests arrive at the system one after the other) setting. A fundamental ingredient of our analysis is the introduction of a new graph parameter, the flow number, that aims to capture global communication properties of the network. With the help of the flow number we develop a general method for transforming arbitrary multicommodity flow solutions into solutions that use short paths only. This generalizes a well-known theorem of Leighton and Rao [J. ACM 46 (6) (1999) 787–832] that applies to uniform flows only. Both the parameter and the method may therefore be of independent interest. [Copyright &y& Elsevier]

Abstract: Given an edge-weighted transportation network G and a list of transportation requests L, the Stacker Crane Problem is to find a minimum-cost tour for a server along the edges of G that serves all requests. The server has capacity one, and starts and stops at the same vertex. In this paper, we consider the case that the transportation network G is a tree, and that the requests are chosen randomly according to a certain class of probability distributions. We show that a polynomial time algorithm by Frederickson and Guan [J. Algorithms 15 (1993) 29–60], which guarantees a 4/3-approximation in the worst case, on almost all inputs finds a minimum-cost tour, along with a certificate of the optimality of its output. [Copyright &y& Elsevier]

Abstract: In this paper we show that a very simple and efficient approach can be used to solve the all pairs almost shortest path problem on the class of weakly chordal graphs and its different subclasses. Moreover, this approach works well also on graphs with small size of largest induced cycle and gives a unified way to solve the all pairs almost shortest path and all pairs shortest path problems on different graph classes including chordal, strongly chordal, chordal bipartite, and distance-hereditary graphs. [Copyright &y& Elsevier]

Abstract: This paper describes the first algorithm to compute the greatest common divisor (GCD) of two n-bit integers using a modular representation for intermediate values U, V and also for the result. It is based on a reduction step, similar to one used in the accelerated algorithm [T. Jebelean, A generalization of the binary GCD algorithm, in: ISSAC ''93: International Symposium on Symbolic and Algebraic Computation, Kiev, Ukraine, 1993, pp. 111–116; K. Weber, The accelerated integer GCD algorithm, ACM Trans. Math. Softw. 21 (1995) 111–122] when U and V are close to the same size, that replaces U by , where p is one of the prime moduli and b is the unique integer in the interval such that . When the algorithm is executed on a bit common CRCW PRAM with processors, it takes time in the worst case. A heuristic model of the average case yields time on the same number of processors. [Copyright &y& Elsevier]

We consider a variant of the Seat Reservation Problem [J. Boyar, K.S. Larsen, Algorithmica 25 (1999) 403–417] in which seat changes are allowed. We analyze the model using the competitive ratio, the competitive ratio on accommodating sequences [J. Boyar, K.S. Larsen, Algorithmica 25 (1999) 403–417], and the accommodating function [J. Boyar et al., Acta Informatica 40 (2003) 3–35; J. Boyar et al., SIAM J. Comput. 31 (1) (2001) 233–258]. A very promising family of algorithms considered in this paper is Min-Change, which will ask passengers to change seats, only if they would otherwise have been rejected. Min-Change belongs to a large class of conservative algorithms, which all have very high performance guarantees. For instance, if the optimal off-line algorithm can seat all of the passengers, 2/3 of the passengers can be seated on-line using any conservative algorithm allowing only one seat change and 3/4 will be seated if two seat changes are allowed. This should be compared to the asymptotic hardness result of 1/2 for the best algorithm when no seat changes are allowed [E. Bach et al., J. Sched. 6 (2003) 131–147]. Another interesting algorithm, Modified-Kierstead–Trotter, is proposed and shown to seat all passengers if the optimal off-line algorithm could have accommodated them with only half as many seats. On this type of sequence, Modified-Kierstead–Trotter is strictly better than Min-Change-First-Fit which is strictly better than the Checkerboard algorithm. [Copyright &y& Elsevier]

We consider two problems pertaining to P4-comparability graphs, namely, the problem of recognizing whether a simple undirected graph is a P4-comparability graph and the problem of producing an acyclic P4-transitive orientation of such a graph. Sequential algorithms for these problems have been presented by Hoa`ng and Reed and very recently by Raschle and Simon, and by Nikolopoulos and Palios. In this paper, we establish properties of P4-comparability graphs which allow us to describe parallel algorithms for the recognition and orientation problems on this class of graphs; for a graph on n vertices and m edges, our algorithms run in O(log2n) time and require O(nm/logn) processors on the CREW PRAM model. Since the currently fastest sequential algorithms for these problems run in O(nm) time, our algorithms are cost-efficient; moreover, to the best of our knowledge, this is the first attempt to introduce parallelization in problems involving P4-comparability graphs. Our approach relies on the parallel computation and proper orientation of the P4-components of the input graph. [Copyright &y& Elsevier]