We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair $\{i, j\}$ of nodes, an edgeconnectivity requirement $r_{ij}$. The goal is to find a minimum-cost network using the available links and satisfying the requirements. Our algorithm outputs a solution whose cost is within $2 \lceil {\log_{2}(r + 1)} \rceil $ of optimal, where r is the highest requirement value. In the course of proving the performance guarantee, we prove a combinatorial minmax approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. As a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts; we show that this algorithm has application to estimating the reliability of a probabilistic network.

Article When trees collide: an approximation algorithm for the generalized Steiner problem on networks Share on Authors: Ajit Agrawal Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile , Philip Klein Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile , R. Ravi Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 134–144https://doi.org/10.1145/103418.103437Online:03 January 1991Publication History 47citation861DownloadsMetricsTotal Citations47Total Downloads861Last 12 Months16Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The first approximate max-flow-min-cut theorem for general multicommodity flow is proved. It is used to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF identical to formula, via minimization problems, and other problems. Also presented are approximation algorithms for chordalization of a graph and for register sufficiency that are based on undirected and directed node separators.>

The authors present a high-speed fault simulator, called CMP3F, that performs parallel-pattern, parallel-fault simulation, implemented on the Connection Machine (CM). Unlike conventional parallel pattern or parallel fault simulators, CMP3F can dynamically choose the fault set size as well as the number of vectors being simulated in parallel. Hence, the fault simulation process is split into several phases. The first phase primarily uses fault-list partitioning because, initially, the fault-list size dominates the fault simulation time. If fault dropping is allowed, CMP3F goes through a number of subsequent phases as the fault list becomes smaller, simulating an increasing number of distinct sets of vectors in parallel. Thus, CMP3F avoids useless computations when a small number of faults are present and maintains nearly linear speedup with an increasing number of processors. Experimental data obtained using ISCAS85 benchmark circuits suggest that CMP3F implemented on a fully configured 64 K-node CM, will perform fault simulation one to two orders of magnitude faster than most existing fault simulators.>

Abstract : This paper discusses a set of powerful primitive matrix operations which allow easy specification of parallel matrix routines. It demonstrates via the hypercube implementation that the additional expressive power need not reduce performance and can, in fact, improve performance by providing automatic load balancing in the case where there are more matrix elements than processors. Some routines based on these primitives and other simple parallel operations give some timings for the primitives and routines for our implementation on the Connection Machine. One expects to generalize these implementations of the primitives so they work on processor grids whose row and column sizes are not powers of two, and to allow a vector extracted from a row off a matrix to be distributed to or deposited in either a row or column of another matrix. The primitives should be available to higher level languages so that they can be easily used.