2367227
Parallel Algorithms For Vehicle Routing Problems
Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connecting locations have time costs associated with them. In this paper, we consider two different problems in single vehicle routing. The first is to find least time cost routes between all pairs of nodes in a network for navigating vehicles; we call this the all pairs routing problem. We show that there is an O(log3 n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM. We next consider the problem in which a vehicle services all locations in a network. Here, locations can be passed through at any time but only serviced during their time window. The general problem is -complete under even fairly stringent restrictions but polynomial algorithms have been developed for some special cases. In particular, when the network is a line, there is no time cost in servicing a location, and all time windows are unbounded at either their lower or upper end, O(n2) algorithms have been developed. We show that under the same conditions, we can reduce this problem to the all pairs routing problem and therefore obtain an O(log3 n) time parallel algorithm on a CREW PRAM.
2981830
Characterizing the Complexity of Subgraph Isomorphism for Graphs of Bounded Path-Width
We show that the complexity of the subgraph isomorphism problem on graphs of bounded path-width is inherently dependent on the connectivity of the source and target graphs. In particular, for the problem of determining whether a source graph G of path-width k is a subgraph of a target graph H of path-width k, we present an O(n3) algorithm for G and H both k-connected, for n the sum of the sizes of the graphs, and NP-completeness results for connectivity less than k. In previous polynomial-time algorithms, the degree of the polynomial in the running time was a function of k. In contrast, we show that when neither G nor H is k-connected, the problem becomes NP-complete. The same result also holds if one of the graphs has at least k vertices of unbounded degree. Since bounded path-width graphs are also bounded tree-width graphs, our hardness results immediately extend to this larger class. A further NP-completeness result applies to the situation in which both graphs have tree-width k, but only the target graph is k-connected. This provides a complete characterization of the subgraph isomorphism problem on bounded tree-width graphs, thus answering an open question of Matousek and Thomas.
492959
On the Complements of Partial k-Trees
We introduce new techniques for studying the structure of partial k-trees. In particular, we show that the complements of partial k-trees provide an intuitively-appealing characterization of partial k-tree obstructions. We use this characterization to obtain a lower bound of 2Ω(k log k) on the number of obstructions, significantly improving the previously best-known bound of 2Ω(√k). Our techniques have the added advantage of being considerably simpler than those of previous authors.
17407466
Point-Based Approaches to Qualitative Temporal Reasoning
We are interested in the problem of qualitative, point-based temporal reasoning. That is, given a set of assertions concerning the relative positions of points in time, we are interested in compiling the assertions into a representation that supports efficient reasoning, determining consistency, computing the strongest entailed relation between any two points and updating the set of assertions. We begin by considering a general set of operations and their corresponding algorithms, applicable to general point-based temporal domains. We also consider special-purpose reasoners, which may be expected to perform well in an application domain with a restricted structure. Lastly we consider reasoners which incorporate restricted structures into a more general reasoning framework. Finally, we present instances of each such approach and give a comparison of their performance on random data sets.
2938206
An Optimal Parallel Algorithm for Formula Evaluation
A new approach to Buss’s ${\textbf{NC}}^1 $ algorithm [Proc. 19th ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, 1987, pp. 123–131] for evaluation of Boolean formulas is presented. This problem is shown to be complete for ${\textbf{NC}}^1 $ over ${\textbf{AC}}^0 $ reductions. This approach is then used to solve the more general problem of evaluating arithmetic formulas by using arithmetic circuits.
35215015
Coarse Grain Preconditioned Conjugate Gradient Solver for Large Sparse Systems
We explore a coarse grain parallel algorithm for the solution of large sparse linear systems with symmetric positive definite matrix, based on a preconditioned conjugate gradient method.
15483295
Conceptual Integration of Multiple Partial Geometric Models
Many scientific databases need to manage complex 3D geometric data such as models of the cerebral cortex. Often the complexity of the data forces users to construct muliple, simpler representations, which cover the real, complete model only partially and approximately. In order to recover the original information one needs to integrate these partial and incomplete models. In this paper, we first develop a conceptual model for objects and relationships in 3D geometric data, as well as their partial and approximate representations. We then establish mapping relationships between different approximations of the same data. Finally, we present a geometric information integration technique that will perform the integration where possible, and determine, for some cases, when the integration cannot be performed.
100323
Tree based MPLS routing
MPLS (MultiProtocol Label Switching) is a new technology proposed by the IETF [4,10] for network routing, and is being increasingly deployed by the largest Internet service providers. The MPLS technology differs from conventional network protocols in a crucial way: instead of reading the entire packet header at all switching points, the analysis of the packet header is done just once, when the packet header is assigned a stack of labels, and thenceforth, each switching point or router just gets to look at the label at the top of the stack (and the ingress edge), and based only on this information, it has to make a decision about the next-hop node [17,16]. In another departure from conventional routing and in particular from IP source routing, where the entire packet route is explicitly put in the header and popped off along the route, the router can not only pop the top label, it can push other labels on top of the stack.The two parameters of interest in designing MPLS routing protocols are the number of labels used, and the depth of the stack used for routing. Clearly, both cannot be simultaneously minimized, and there is often an interesting trade-off between label size and stack depth: it is obvious that if k labels are used, one must have a stack depth of logk n.In fact, it was not known whether this bound could be achieved even for trees; the best stack depth previously achieved with a constant number of labels was O(log2 n). In this paper, we show that one can indeed get asymptotically optimal upper bounds and route on trees using k labels and a maximum stack depth of O(logk n), and that this trade-off can be achieved using a simpler and more intuitive protocol than the one given in [9]. These tree-routing ideas are then shown to give better routing protocols for planar graphs as well. In particular, we show how to route along near-shortest paths (of length at most (1 + ε) times the shortest-path) with O(log2 n/ε) labels and logarithmic stack depth. We also apply them to graphs with smaller separators, including most large ISP networks.
42998438
Performance comparison of checkpoint and recovery protocols
Checkpoint and rollback recovery is a well-known technique for providing fault tolerance to long-running distributed applications. Performance of a checkpoint and recovery protocol depends on the characteristics of the application and the system on which it runs. However, given an application and system environment, there is no easy way to identify which checkpoint and recovery protocol will be most suitable for it. Conventional approaches require implementing the application with all the protocols under consideration, running them on the desired system, and comparing their performances. This process can be very tedious and time consuming. This paper first presents the design and implementation of a simulation environment, distributed process simulation or dPSIM, which enables easy implementation and evaluation of checkpoint and recovery protocols. The tool enables the protocols to be simulated under a wide variety of application, system, and network characteristics. The paper then presents performance evaluation of five checkpoint and recovery protocols. These protocols are implemented and executed in dPSIM under different simulated application, system, and network characteristics. Copyright © 2003 John Wiley & Sons, Ltd.
9282309
Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem
We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of capacity basis, or bought, which allows unlimited use after payment of a large fixed cost. Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink. The first constant-factor approximation algorithm for this problem was recently given by Kumar et al.; however, this algorithm and its analysis are both quite complicated, and its performance guarantee is extremely large. In this paper, we give a conceptually simple 12-approximation algorithm for this problem. Our analysis of this algorithm makes crucial use of cost sharing, the task of allocating the cost of an object to many users of the object in a "fair" manner. While techniques from approximation algorithms have recently yielded new progress on cost sharing problems, our work is the first to show the converse - those ideas from cost sharing can be fruitfully applied in the design and analysis of approximation algorithms.