We present a faster algorithm for low-diameter decompositions on directed graphs, matching the \(O(\log n \log \log n)\) loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICALP 2025) and improving the running time to \(O((m + n \log \log n) \log n \log \log n)\) in expectation. We then apply our faster low-diameter decomposition to obtain an algorithm for negative-weight single source shortest paths on integer-weighted graphs in \(O((m+n \log \log n) \log(nW) \log n \log \log n)\) time, a nearly log-factor improvement over the algorithm of Bringmann, Cassis, and Fischer (FOCS 2023).

We develop a novel algorithm to construct a congestion-approximator with polylogarithmic quality on a capacitated, undirected graph in nearly-linear time. Our approach is the first bottom-up hierarchical construction, in contrast to previous top-down approaches including that of Racke, Shah, and Taubig (SODA 2014), the only other construction achieving polylogarithmic quality that is implementable in nearly-linear time (Peng, SODA 2016). Similar to Racke, Shah, and Taubig, our construction at each hierarchical level requires calls to an approximate max-flow/min-cut subroutine. However, the main advantage to our bottom- up approach is that these max-flow calls can be implemented directly without recursion. More precisely, the previously computed levels of the hierarchy can be converted into a pseudo-congestion-approximator, which then translates to a max-flow algorithm that is sufficient for the particular max-flow calls used in the construction of the next hierarchical level. As a result, we obtain the first non-recursive algorithms for congestion-approximator and approximate max-flow that run in nearly-linear time, a conceptual improvement to the aforementioned algorithms that recursively alternate between the two problems.

In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut in a (weighted) graph in time O(m log3 n) which he termed near-linear time meaning linear (in the size of the input) times a polylogarthmic factor. In this paper, we give the first deterministic algorithm which runs in near-linear time for weighted graphs.

Incremental tree building (INC) is a new phylogeny estimation method that has been proven to be absolute fast converging under standard sequence evolution models. A variant of INC, called Constrained-INC, is designed for use in divide-and-conquer pipelines for phylogeny estimation where a set of species is divided into disjoint subsets, trees are computed on the subsets using a selected base method, and then the subset trees are combined together. We evaluate the accuracy of INC and Constrained-INC for gene tree and species tree estimation on simulated datasets, and compare it to similar pipelines using NJMerge (another method that merges disjoint trees). For gene tree estimation, we find that INC has very poor accuracy in comparison to standard methods, and even Constrained-INC(using maximum likelihood methods to compute constraint trees) does not match the accuracy of the better maximum likelihood methods. Results for species trees are somewhat different, with Constrained-INC coming close to the accuracy of the best species tree estimation methods, while being much faster; furthermore, using Constrained-INC allows species tree estimation methods to scale to large datasets within limited computational resources. Overall, this study exposes the benefits and limitations of divide-and-conquer strategies for large-scale phylogenetic tree estimation.

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic $O(m \log^2 n \log\log^2 n)$ time algorithm. This improves on both the best previously known deterministic running time of $O(m \log^{12} n)$ (Kawarabayashi and Thorup [ J. ACM, 66 (2018), 4]) and the best previously known randomized running time of $O(m \log^{3} n)$ (Karger [ J. ACM, 47 (2000), pp. 46--76]) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow- and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest.

We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is O(log2 n). This is a consequence of a more general result which shows that the spectral norm of the entrywise absolute value of the transfer impedance matrix of a graph is O(log2 n). This result implies a simple oblivious routing scheme based on electrical flows in the case of transitive graphs.

Absolute fast converging (AFC) phylogeny estimation methods are ones that have been proven to recover the true tree with high probability given sequences whose lengths are polynomial in the number of number of leaves in the tree (once the shortest and longest branch lengths are fixed). While there has been a large literature on AFC methods, the best in terms of empirical performance was DCM_NJ, published in SODA 2001. The main empirical advantage of DCM_NJ over other AFC methods is its use of neighbor joining (NJ) to construct trees on smaller taxon subsets, which are then combined into a tree on the full set of species using a supertree method; in contrast, the other AFC methods in essence depend on quartet trees that are computed independently of each other, which reduces accuracy compared to neighbor joining. However, DCM_NJ is unlikely to scale to large datasets due to its reliance on supertree methods, as no current supertree methods are able to scale to large datasets with high accuracy. In this study we present a new approach to large-scale phylogeny estimation that shares some of the features of DCM_NJ but bypasses the use of supertree methods. We prove that this new approach is AFC and uses polynomial time. Furthermore, we describe variations on this basic approach that can be used with leaf-disjoint constraint trees (computed using methods such as maximum likelihood) to produce other AFC methods that are likely to provide even better accuracy. Thus, we present a new generalizable technique for large-scale tree estimation that is designed to improve scalability for phylogeny estimation methods to ultra-large datasets, and that can be used in a variety of settings (including tree estimation from unaligned sequences, and species tree estimation from gene trees).

Diffusions and related random walk procedures are of central importance in many areas of machine learning, data analysis, and applied mathematics. Because they spread mass agnostically at each step in an iterative manner, they can sometimes spread mass “too aggressively,” thereby failing to find the “right” clusters. We introduce a novel Capacity Releasing Diffusion (CRD) Process, which is both faster and stays more local than the classical spectral diffusion process. As an application, we use our CRD Process to develop an improved local algorithm for graph clustering. Our local graph clustering method can find local clusters in a model of clustering where one begins the CRD Process in a cluster whose vertices are connected better internally than externally by an $O(\log^2 n)$ factor, where $n$ is the number of nodes in the cluster. Thus, our CRD Process is the first local graph clustering algorithm that is not subject to the well-known quadratic Cheeger barrier. Our result requires a certain smoothness condition, which we expect to be an artifact of our analysis. Our empirical evaluation demonstrates improved results, in particular for realistic social graphs where there are moderately good—but not very good—clusters.

We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log2 n log log2 n) time algorithm. This improves both on the best previously known deterministic running time of O(m log12 n) (Kawarabayashi and Thorup [12]) and the best previously known randomized running time of O(mlog3n) (Karger [11]) for this problem, though Karger's algorithm can be further applied to weighted graphs. Our approach is using the Kawarabayashi and Tho- rup graph compression technique, which repeatedly finds low-conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow- based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow and diffusion based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that is both local and produces low conductance cuts. Thus, it may be of independent interest.

Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with n variables and m clauses, there is a value of m = Ω(n) beyond which the CSP will be unsatisfiable with high probability. Strong refutation is the problem of certifying that no variable assignment satisfies more than a constant fraction of clauses; this is the natural algorithmic problem in the unsatisfiable regime (when m/n = ω(1)).

In a series of recent breakthroughs, Allen-Zhu and Orecchia [Allen-Zhu/Orecchia, STOC 2015; Allen-Zhu/Orecchia, SODA 2015] leveraged insights from the linear coupling method [Allen-Zhu/Oreccia, arXiv 2014], which is a first-order optimization scheme, to provide improved algorithms for packing and covering linear programs. The result in [Allen-Zhu/Orecchia, STOC 2015] is particularly interesting, as the algorithm for packing LP achieves both width-independence and Nesterov-like acceleration, which was not known to be possible before. Somewhat surprisingly, however, while the dependence of the convergence rate on the error parameter epsilon for packing problems was improved to O(1/epsilon), which corresponds to what accelerated gradient methods are designed to achieve, the dependence for covering problems was only improved to O(1/epsilon^{1.5}), and even that required a different more complicated algorithm, rather than from Nesterov-like acceleration. Given the primal-dual connection between packing and covering problems and since previous algorithms for these very related problems have led to the same epsilon dependence, this discrepancy is surprising, and it leaves open the question of the exact role that the linear coupling is playing in coordinating the complementary gradient and mirror descent step of the algorithm. In this paper, we clarify these issues, illustrating that the linear coupling method can lead to improved O(1/epsilon) dependence for both packing and covering problems in a unified manner, i.e., with the same algorithm and almost identical analysis. Our main technical result is a novel dimension lifting method that reduces the coordinate-wise diameters of the feasible region for covering LPs, which is the key structural property to enable the same Nesterov-like acceleration as in the case of packing LPs. The technique is of independent interest and that may be useful in applying the accelerated linear coupling method to other combinatorial problems.

BACKGROUND: The problem of de-novo assembly for metagenomes using only long reads is gaining attention. We study whether post-processing metagenomic assemblies with the original input long reads can result in quality improvement. Previous approaches have focused on pre-processing reads and optimizing assemblers. BIGMAC takes an alternative perspective to focus on the post-processing step. RESULTS: Using both the assembled contigs and original long reads as input, BIGMAC first breaks the contigs at potentially mis-assembled locations and subsequently scaffolds contigs. Our experiments on metagenomes assembled from long reads show that BIGMAC can improve assembly quality by reducing the number of mis-assemblies while maintaining or increasing N50 and N75. Moreover, BIGMAC shows the largest N75 to number of mis-assemblies ratio on all tested datasets when compared to other post-processing tools. CONCLUSIONS: BIGMAC demonstrates the effectiveness of the post-processing approach in improving the quality of metagenomic assemblies.

We give an algorithm which computes a (1-ε)-approximately maximum st-flow in an undirected uncapacitated graph in time O(1/ε√m/F⋅ m log2 n) where F is the flow value. By trading this off against the Karger-Levine algorithm for undirected graphs which takes ~O(m+nF) time, we obtain a running time of ~O(m n1/3/ε2/3) for uncapacitated graphs, improving the previous best dependence on ε by a factor of O(1/ε3). Like the algorithm of Christiano, Kelner, Madry, Spielman and Teng, our algorithm reduces the problem to electrical flow computations which are carried out in linear time using fast Laplacian solvers. However, in contrast to previous work, our algorithm does not reweight the edges of the graph in any way, and instead uses local (i.e., non s-t) electrical flows to reroute the flow on congested edges. The algorithm is simple and may be viewed as trying to find a point at the intersection of two convex sets (the affine subspace of st-flows of value F and the l∞ ball) by an accelerated version of the method of alternating projections due to Nesterov.

We consider solutions for distributed multicommodity flow problems, which are solved by multiple agents operating in a cooperative but uncoordinated manner. We show first distributed solutions that allow (1 + ϵ) approximation and whose convergence time is essentially linear in the maximal path length, and is independent of the number of commodities and the size of the graph. Our algorithms use a very natural approximate steepest descent framework, combined with a blocking flow technique to speed up the convergence in distributed and parallel environment. Previously known solutions that achieved comparable convergence time and approximation ratio required exponential computational and space overhead per agent.

We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the Rayleigh quotient. Using this, we show that every n -vertex graph of genus g and maximum degree D satisfies λ 2 ( G )= O (( g +1) 3 D / n ). This recovers the O ( D / n ) bound of Spielman and Teng for planar graphs, and compares to Kelner's bound of O (( g +1)poly( D )/ n ), but our proof does not make use of conformal mappings or circle packings. We are thus able to extend this to resolve positively a conjecture of Spielman and Teng, by proving that λ 2 ( G ) = O ( D h 6 log h / n ) whenever G is K h -minor free. This shows, in particular, that spectral partitioning can be used to recover O (√ n )-sized separators in bounded degree graphs that exclude a fixed minor. We extend this further by obtaining nearly optimal bounds on λ 2 for graphs that exclude small-depth minors in the sense of Plotkin, Rao, and Smith. Consequently, we show that spectral algorithms find separators of sublinear size in a general class of geometric graphs. Moreover, while the standard “sweep” algorithm applied to the second eigenvector may fail to find good quotient cuts in graphs of unbounded degree, our approach produces a vector that works for arbitrary graphs. This yields an alternate proof of the well-known nonplanar separator theorem of Alon, Seymour, and Thomas that states that every excluded-minor family of graphs has O (√ n )-node balanced separators.

We study the edge disjoint paths (EDP) problem in undirected graphs: Given a graph G with n nodes and a set $\mathcal{T}$ of pairs of terminals, connect as many terminal pairs as possible using paths that are mutually edge disjoint. This leads to a variety of classic NP-complete problems, for which approximability is not well understood. We show a polylogarithmic approximation algorithm for the undirected EDP problem in general graphs with a moderate restriction on graph connectivity; we require the global minimum cut of G to be $\Omega(\log^5n)$. Previously, constant or polylogarithmic approximation algorithms were known for trees with parallel edges, expanders, grids, grid-like graphs, and, most recently, even-degree planar graphs. These graphs either have special structure (e.g., they exclude minors) or have large numbers of short disjoint paths. Our algorithm extends previous techniques in that it applies to graphs with high diameters and asymptotically large minors.

Accurate phylogenetic reconstruction methods are currently limited to a maximum of few dozens of taxa. Supertree methods construct a large tree over a large set of taxa, from a set of small trees over overlapping subsets of the complete taxa set. Hence, in order to construct the tree of life over a million and a half different species, the use of a supertree method over the product of accurate methods, is inevitable. Perhaps the simplest version of this task that is still widely applicable, yet quite challenging, is quartet-based reconstruction. This problem lies at the root of many tree reconstruction methods and theoretical as well as experimental results have been reported. Nevertheless, dealing with false, conflicting quartet trees remains problematic. In this paper, we describe an algorithm for constructing a tree from a set of input quartet trees even with a significant fraction of errors. We show empirically that conflicts in the inputs are handled satisfactorily and that it significantly outperforms and outraces the Matrix Representation with Parsimony (MRP) methods that have previously been most successful in dealing with supertrees. Our algorithm is based on a divide and conquer algorithm where our divide step uses a semidefinite programming (SDP) formulation of MaxCut. We remark that this builds on previous work of ours for piecing together trees from rooted triplet trees. The recursion for unrooted quartets, however, is more complicated in that even with completely consistent set of quartet trees the problem is NP-hard, as opposed to the problem for triples where there is a linear time algorithm. This complexity leads to several issues and some solutions of possible independent interest.

Statistical machine learning techniques have recently garnered increased popularity as a means to improve network design and security. For intrusion detection, such methods build a model for normal behavior from training data and detect attacks as deviations from that model. This process invites adversaries to manipulate the training data so that the learned model fails to detect subsequent attacks.

We give aO(√logn)-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves theO(logn)-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem about projections of point sets inRd, whose proof makes essential use of a phenomenon called measure concentration. We also describe an interesting and natural “approximate certificate” for a graph's expansion, which involves embedding ann-node expander in it with appropriate dilation and congestion. We call this an expander flow.

We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O (log 2 n ) factor in Õ( m + n 3/2 ) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows that take time Õ( m + n 2 ). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O (log 2 n )-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time.

We present a new method for upper bounding the second eigenvalue of theLaplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the Rayleigh quotient. Using this, we show that every n-vertex graph of genus g and maximum degree d satisfies lambda2(G) = O((g+1)3d/n).This recovers the O(d/n) bound of Spielman and Teng for planar graphs, and compares to Kelner's bound of O((g+1)poly(d)/n), but our proof does not make use of conformal mappings or circle packings. We are thus able to extend this to resolve positively a conjecture of Spielman and Teng, by proving that lambda2(G) = O(dh6log h/n) whenever G is Kh-minor free. This shows, in particular, that spectral partitioning can be used to recover O(radicn)-sized separators in bounded degree graphs that exclude a fixed minor. We extend this further by obtaining nearly optimal bounds on lambda2for graphs which exclude small-depth minors in the sense of Plotkin, Rao, and Smith. Consequently, we show that spectral algorithms find small separators in a general class of geometric graphs. Moreover, while the standard "sweep'' algorithm applied to the second eigenvector may fail to find good quotient cuts in graphs of unbounded degree, our approach produces a vector that works for arbitrary graphs. This yields an alternate proof of the result of Alon, Seymour, and Thomas that every excluded-minor family of graphs has O(radicn)-node balanced separators.

This paper provides a randomized approximation scheme for the k-median problem when the input points lie in the d-dimensional Euclidean space. The worst-case running time is $O(2^{O((\log(1/\epsilon) / \varepsilon)^{d-1})} n \log^{d+6} n ),$ which is nearly linear for any fixed $\varepsilon$ and d. Moreover, our method provides the first polynomial-time approximation scheme for and uncapacitated facility location instances in d-dimensional Euclidean space for any fixed $d > 2.$ Our work extends techniques introduced originally by Arora for the Euclidean traveling salesman problem (TSP). To obtain the improvement we develop a structure theorem to describe hierarchical decomposition of solutions. The theorem is based on an adaptive decomposition scheme, which guesses at every level of the hierarchy the structure of the optimal solution and accordingly modifies the parameters of the decomposition. We believe that our methodology is of independent interest and may find applications to further geometric problems.

We consider the k -traveling repairmen problem, also known as the minimum latency problem, to multiple repairmen. We give a polynomial-time 8.497α-approximation algorithm for this generalization, where α denotes the best achievable approximation factor for the problem of finding the least-cost rooted tree spanning i vertices of a metric. For the latter problem, a (2 + ε)-approximation is known. Our results can be compared with the best-known approximation algorithm using similar techniques for the case k = 1, which is 3.59α. Moreover, recent work of Chaudry et al. [2003] shows how to remove the factor of α, thus improving all of these results by that factor. We are aware of no previous work on the approximability of the present problem. In addition, we give a simple proof of the 3.59α-approximation result that can be more easily extended to the case of multiple repairmen, and may be of independent interest.

We show that the sparsest cut in graphs can be approximated within O(log2 n) factor in Õ(n3/2) time using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows which take time Õ(n2). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log2 n) (pseudo) approximation algorithm for the edge-separator problem with a similar running time.

Supertree methods are used to construct a large tree over a large set of taxa from a set of small trees over overlapping subsets of the complete taxa set. Since accurate reconstruction methods are currently limited to a maximum of a few dozen taxa, the use of a supertree method in order to construct the tree of life is inevitable. Supertree methods are broadly divided according to the input trees: When the input trees are unrooted, the basic reconstruction unit is a quartet tree. In this case, the basic decision problem of whether there exists a tree that agrees with all quartets is NP-complete. On the other hand, when the input trees are rooted, the basic reconstruction unit is a rooted triplet and the above decision problem has a polynomial time algorithm. However, when there is no tree which agrees with all triplets, it would be desirable to find the tree that agrees with the maximum number of triplets. However, this optimization problem was shown to be NP-hard. Current heuristic approaches perform min cut on a graph representing the triplets inconsistency and return a tree that is guaranteed to satisfy some required properties. In this work, we present a different heuristic approach that guarantees the properties provided by the current methods and give experimental evidence that it significantly outperforms currently used methods. This method is based on a divide and conquer approach, where the min cut in the divide step is replaced by a max cut in a variant of the same graph. The latter is achieved by a lightweight semidefinite programming-like heuristic that leads to very fast running times.

No abstract available.

We give a O(√log n)-approximation algorithm for sparsest cut, balanced separator, and graph conductance problems. This improves the O(log n)-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem about projections of point sets in Rd, whose proof makes essential use of a phenomenon called measure concentration. We also describe an interesting and natural "certificate" for a graph's expansion, by embedding an n-node expander in it with appropriate dilation and congestion. We call this an expander flow.

We describe logarithmic approximation algorithms for the NP-hard graph optimization problems of minimum linear arrangement, minimum containing interval graph, and minimum storage--time product. This improves upon the best previous approximation bounds of Even, Naor, Rao, and Schieber [J. ACM, 47 (2000), pp. 585--616] for these problems by a factor of $\Omega$(log log n). We use the lower bound provided by the volume W of a spreading metric for each of the ordering problems above (as defined by Even et al.) in order to find a solution with cost at most a logarithmic factor times W for these problems. We develop a divide-and-conquer strategy where the cost of a solution to a problem at a recursive level is C plus the cost of a solution to the subproblems at this level, and where the spreading metric volume on the subproblems is less than the original volume by $\Omega$(C log n), ensuring that the resulting solution has cost O(log n) times the original spreading metric volume. We note that this is an existentially tight bound on the relationship between the spreading metric volume and the true optimal values for these problems. For planar graphs, we combine a structural theorem of Klein, Plotkin, and Rao [Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 682--690] with our new recursion technique to show that the spreading metric cost volumes are within an O(log log n) factor of the cost of an optimal solution for the minimum linear arrangement, and the minimum containing interval graph problems.

We give improved approximation algorithms for a variety of latency minimization problems. In particular, we give a 3.59-approximation to the minimum latency problem, improving on previous algorithms by a multiplicative factor of 2. Our techniques also give similar improvements for related problems like k-traveling repairmen and its multiple depot variant. We also observe that standard techniques can be used to speed up the previous and this algorithm by a factor of O/sup /spl tilde//(n).

Racke recently gave a remarkable proof showing that any undirected multicommodity ow problem can be routed in an oblivious fashion with congestion that is within a factor of O(log n) of the best o-line solution to the problem. He also presented interesting applications of this result to distributed computing. Maggs, Miller, Parekh, Ravi and Wu have shown that such a decomposition also has an application to speeding up iterative solvers of linear systems.

We devise the first constant factor approximation algorithm for minimum quotient vertex-cuts in planar graphs. Our algorithm achieves approximation ratio 1+4/3(1+ε) with running time O(W• n3+2/ε), where W is the total weight of the vertices. The approximation ratio improves to 4/3(1+ε+o(1)) if there is an optimal quotient vertex-cut (A*,B*,C*) where the weight of C* is of low order compared to those of A* and B*; this holds, for example, when the input graph has uniform weights and costs. The ratio further improves to 1+ε+o(1) if, in addition, min[w(A*),w(B*)] ≤ 1/3 W.We use our algorithm for quotient vertex-cuts to achieve the first constant-factor pseudo-approximation for vertex separators in planar graphs.Our technical contribution is two-fold. First, we prove a structural theorem for planar graphs, showing the existence of a near-optimal quotient vertex-cut whose high-level structure is that of a bounded-depth tree. Second, we develop an algorithm that optimizes over such complex structures in running time that depends (exponentially) not on the size of the structure, but rather only on its depth. These techniques may be applicable in other problems.

In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the result of Bartal who gave a bound of O(log n log log n). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Ω(log n)-distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems.

Modern networking applications replicate data and services widely, leading to a need for location-independent routing -- the ability to route queries directly to objects using names independent of the objects' physical locations. Two important properties of a routing infrastructure are routing locality and rapid adaptation to arriving and departing nodes. We show how these two properties can be efficiently achieved for certain network topologies. To do this, we present a new distributed algorithm that can solve the nearest-neighbor problem for these networks. We describe our solution in the context of Tapestry, an overlay network infrastructure that employs techniques proposed by Plaxton, Rajaraman, and Richa [14].

The authors present an O(n log/sup 3/ n) time algorithm for finding shortest paths in a planar graph with real weights. This can be compared to the best previous strongly polynomial time algorithm developed by R. Lipton et al., (1978 )which ran in O(n/sup 3/2/) time, and the best polynomial algorithm developed by M. Henzinger et al. (1994) which ran in O/spl tilde/(n/sup 4/3/) time. We also present significantly improved algorithms for query and dynamic versions of the shortest path problems.

The Lovász local lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. The original lemma was nonconstructive; a breakthrough of Beck and its generalizations (due to Alon and Molloy and Reed) have led to constructive versions. However, these methods do not capture some classes of applications of the LLL. We make progress on this by providing algorithmic approaches to two families of applications of the LLL. The first provides constructive versions of certain applications of an extension of the LLL (modeling, e.g., hypergraph-partitioning and low-congestion routing problems); the second provides new algorithmic results on constructing disjoint paths in graphs. Our results can also be seen as constructive upper bounds on the integrality gap of certain packing problems. One common theme of our work is a "gradual rounding" approach.

A basic problem faced by designers of high-bandwidth switches and routers is to provide effective techniques for scheduling the routing of cells through crossbars. The problem is particularly important under heavy loads or when quality-of-service (QoS) is to be supported. Much previous work on scheduling has focused on maximum bipartite matching (MBM), maximum weight bipartite matching (MWBM), and heuristics to approximate MBM and MWBM solutions. In this paper, we introduce the shakeup technique: a randomized approach that can be used in conjunction with a number of existing heuristics to substantially improve solution quality. The shakeup approach is conceptually simple and is supported by both theoretical and experimental results. In addition, this paper provides for the first time a framework for experimental scheduler analysis. We give extensive head-to-head comparisons of stability ranges for a number of previously proposed schedulers, and work towards the development of benchmark traffic types.

We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns lengths to either edges or vertices of the input graph, such that all subgraphs for which the optimization problem is nontrivial have large diameters. In addition, the spreading metric provides a lower bound, τ, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modeled by our paradigm whose approximation factor is O (min{log τ, log log τ, log k log log k }) where k denotes the number of “interesting” vertices in the problem instance, and is at most the number of vertices. We present seven problems that can be formulated to fit the paradigm. For all these problems our algorithm improves previous results. The problems are: (1) linear arrangement; (2) embedding a graph in a d -dimensional mesh; (3) interval graph completion; (4) minimizing storage-time product; (5) subset feedback sets in directed graphs and multicuts in circular networks; (6) symmetric multicuts in directed networks; (7) balanced partitions and p -separators (for small values of p ) in directed graphs.

A finite metric space, (S,d) , contains a finite set of points and a distance function on pairs of points.A contraction is an embedding, h, of a finite metric space (S, d) into Rd where for any u, v E S, the Euclidean (&) distance between h(u) and h(v) is no more than d(u, v).The distortion of the embedding is the maximum over pairs of the ratio of d(u, w) and the Euclidean distance between h(u) and h(v).Bourgain showed that any graphical metric could be embedded with distortion O(logn).Linial, London and Rabinovich and Aumman and Rabani used such embeddings to prove an O(log k) approximate max-flow min-cut theorem for k commodity flow problems.A generalization of embeddings that preserve distances between pairs-of points are embeddings that preserve volumes of larger sets.In particular, A (k, c)-volume respecting embedding of n-points in any metric space is a contraction where every subset of k points has within an ck-' factor of its maximal possible k -l-dimensional volume.Feige invented these embeddings in devising a polylogarithmic approximation algorithm for the bandwidth problem using these embeddings.Feige's methods have subsequently been used by Vempala for approximating versions of the VLSI layout problem.Feise showed that a (k, O(10,g~'~ n,/m)) volume r&ecting embedding' eksted."Be -recently found improved (k, 0( mdk log k + log n)) volume respecting embeddings.For metrics arising from planar graphs (planar metrics), we give (k,O(m)) volume respecting contractions.As a corollary, we give embeddings for Permission to makkr digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.XC'99 Miami Beach Florida Copyright ACM 1999 I-581 13-068-6/99/06...$5.00 planar metrics with distortion O(e).This gives rise to an O(e)-approximate max-flow min-cut theorem for multicommodity flow problems in planar graphs.We also give an improved bound for volume respecting embeddings for Euclidean metrics.In particular, we give an (k,O(dog klog D)) volume respecting embedding where D is the ratio of the largest distance to the smallest distance in the metric.Our results give improvements for Feige's and Vempala's approximation algorithms for planar and Euclidean metrics.For volume respecting embeddings, our embeddings do not degrade very fast when preserving the volumes of large subsets.This may be useful in the future for approximation algorithms or if volume .respectingembeddings prove to be of independent interest.

Article BOS is boss: a case for bulk-synchronous object systems Share on Authors: Mark W. Goudreau C&C Research Laboratories, NEC USA, Inc., 4 Independence Way, Princeton, NJ C&C Research Laboratories, NEC USA, Inc., 4 Independence Way, Princeton, NJView Profile , Kevin Lang NEC Research Institute, 4 Independence Way, Princeton, NJ NEC Research Institute, 4 Independence Way, Princeton, NJView Profile , Girija Narlikar School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PAView Profile , Satish B. Rao NEC Research Institute, 4 Independence Way, Princeton, NJ NEC Research Institute, 4 Independence Way, Princeton, NJView Profile Authors Info & Claims SPAA '99: Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architecturesJune 1999 Pages 115–125https://doi.org/10.1145/305619.305632Published:01 June 1999 1citation206DownloadsMetricsTotal Citations1Total Downloads206Last 12 Months1Last 6 weeks0 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

In this paper, we establish max-flow min-cut theorems for several important classes of multicommodity flow problems.In particular, we show that for any n-node multicommodity flow problem with uniform demands, the max-flow for the problem is within an O(log n) factor of the upper bound implied by the min-cut.The result (which is existentially optimal) establishes an important analogue of the famous 1-commodity max-flow min-cut theorem for problems with multiple commodities.The result also has substantial applications to the field of approximation algorithms.For example, we use the flow result to design the first polynomial-time (polylog n-times-optimal) approximation algorithms for well-known NP-hard optimization problems such as graph partitioning, min-cut linear arrangement, crossing number, VLSI layout, and minimum feedback arc set.Applications of the flow results to path routing problems, network reconfiguration, communication in distributed networks, scientific computing and rapidly mixing Markov chains are also described in the paper.

We study graph partitioning problems on graphs with edge capacities and vertex weights. The problems of b-balanced cuts and k-balanced partitions are unified into a new problem called minimum capacity $\rho$-separators. A $\rho$-separator is a subset of edges whose removal partitions the vertex set into connected components such that the sum of the vertex weights in each component is at most $\rho$ times the weight of the graph. We present a new and simple O(log n)-approximation algorithm for minimum capacity $\rho$-separators which is based on spreading metrics yielding an O(log n)-approximation algorithm both for b-balanced cuts and k-balanced partitions. In particular, this result improves the previous best known approximation factor for k-balanced partitions in undirected graphs by a factor of O(log k). We enhancethese results by presenting a version of the algorithm that obtains an O(log OPT)-approximation factor. The algorithm is based on a technique called spreading metrics that enables us to formulate directly the minimum capacity $\rho$-separator problem as an integer program. We also introduce a generalization called the simultaneous separator problem, where the goal is to find a minimum capacity subset of edges that separates a given collection of subsets simultaneously. We extend our results to directed graphs for values of $\rho \geq 1/2$. We conclude with an efficient algorithm for computing an optimal spreading metric for $\rho$-separators. This yields more efficient algorithms for computing b-balanced cuts than were previously known.

We present a work-optimal randomized algorithm for simulating a shared memory machine (PRAM) on an optical communication parallel computer (OCPC). The OCPC model is motivated by the potential of optical communication for parallel computation. The memory of an OCPC is divided into modules, one module per processor. Each memory module only services a request on a timestep if it receives exactly one memory request. Our algorithm simulates each step of an n lg lg n-processor EREW PRAM on an n-processor OCPC in O(lg lg n) expected delay. (The probability that the delay is longer than this is at most $n^{-\alpha}$ for any constant $\alpha$.) The best previous simulation, due to Valiant, required $\Theta(\log n)$ expected delay.

We describe an O(min(m,n 3/2 )m 1/2 )-time algorithm for finding maximum flows in undirected networks with unit capacities and no parallel edges. This improves upon the previous bound of Karzanov and Even and Tarjan when $m = \omega(n^{3/2})$, and upon a randomized bound of Karger when $v = \Omega(n^{7/4}/m^{1/2})$.

The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory, the BSP model has been shown to allow the asymptotically optimal execution of architecture independent software on a variety of architectures. Our goal in this work is to experimentally examine the practical use of the BSP model on current parallel architectures. We describe the design and implementation of the Green BSP Library, a small library of functions that implement the BSP model, and of several applications that were written for this library. We then discuss the performance of the library and application programs on several parallel architectures. Our results are positive in that we demonstrate efficiency and portability over a range of parallel architectures and show that the BSP cost model is useful for predicting performance trends and estimating execution times.

Article Approximation schemes for Euclidean k-medians and related problems Share on Authors: Sanjeev Arora Princeton University Princeton UniversityView Profile , Prabhakar Raghavan IBM Almaden Research Center, 650 Harry Road, San Jose CA IBM Almaden Research Center, 650 Harry Road, San Jose CAView Profile , Satish Rao NEC Research Institute, Princeton, NJ NEC Research Institute, Princeton, NJView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 106–113https://doi.org/10.1145/276698.276718Published:23 May 1998 210citation1,443DownloadsMetricsTotal Citations210Total Downloads1,443Last 12 Months66Last 6 weeks10 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

probability l/2 in a Monte Carlo sense2 in time The main result of t,his paper is an improvement of Arora's method to find (l+e) approximations for geometric NP-hard problems including the Euclidean Traveling Salesman Problem and t.he Euclidean Steiner Minimum Tree problems.For f&d dimension d and E, our algorithms run in O(NlogN) time.(s\/;i) O(d(+.&)d-')N + O(dN log N) and (sd)"(d)N + (sfi)"(d(~~)d-') log N (4 An interesting byproduct of our work is the definition and consbruction of banyans, a generalization of graph spxmers.A (1 + e)-banyan for a set of points A is a set of points A' and line segments S wit,h endpoints in A U A' such that a 1 + e optimal Steiner Minimum Tree for any subset of A is contained in S. We give a construction for banyans such that the total length of the line segments in S is within a constant factor of the size of t,he minimum spanning tree of A when e and d are fked.space, or in a Las Vegas sense3 in time 2(ad)"(d) N + O(dNlogN), or a deterministic algorithm with runt,ime 2(sd)"(d) N + (sd) o(d)Nlog N, in both of the latter cases consumingIn thii abbreviated paper, we only provide proofs of these results in two dimensions.The full paper on WDS's web page (http://wuu.neci.nj.nec.com/homepages/wds,click"NECItechnical reports") extends the techniques to higher dimensions, proves some new facts and clarifies some old facts about spanners, and also gives approsimation algorithms for minimum matching, edge cover, rectilinear Steiner minimum tree, and minimum a-matching.(s~)'(~)N + 2(8d)o'd' log N space.Our (1+1/s)-approsimation algorithms for NP-hard problems run more slowly than competing esact algorithms when so(l) > N or do(') > log N, otherwise they run more quicldy. New Ingredients

We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual arc capacities. Our approach leads to an O (min( n 2/3 , m 1/2 ) m log( n 2 / m ) log U ) time bound for a network with n vertices, m arcs, and integral arc capacities in the range [1, …, U ]. This is a fundamental improvement over the previous time bounds. We also improve bounds for the Gomory-Hu tree problem, the parametric flow problem, and the approximate s-t cut problem.

BSPlib is a small communications library for bulk synchronous parallel (BSP) programming which consists of only 20 basic operations. This paper presents the full definition of BSPlib in C, motivates the design of its basic operations, and gives examples of their use. The library enables programming in two distinct styles: direct remote memory access (DRMA) using put or get operations, and bulk synchronous message passing (BSMP). Currently, implementations of BSPlib exist for a variety of modern architectures, including massively parallel computers with distributed memory, shared memory multiprocessors, and networks of workstations. BSPlib has been used in several scientific and industrial applications; this paper briefly describes applications in benchmarking, Fast Fourier Transforms (FFTs), sorting, and molecular dynamics.

We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual are capacities. Our approach leads to an O(min(n/sup 2/3/, m/sup 1/2/)m log(n/sup 2//m) log U) time bound for a network with n vertices, m arcs, and integral arc capacities in the range [1,...,U]. This is a fundamental improvement over the previous time bounds. We also improve bounds for the Gomory-Hu tree problem, the parametric flow problem, and the approximate s-t cut problems.

We describe an O(min(m, n/sup 3/2/)m/sup 1/2/)-time algorithm for finding maximum flows in undirected networks with unit capacities and no parallel edges. This improves upon the previous bound of Karzanov and Even and Tarjan when m=/spl omega/(n/sup 3/2/), and upon a randomized bound of Karger when /spl upsi/=/spl Omega/(n/sup 7/4//m/sup 1/2/).

In this paper, we study the problem of emulating T G steps of an N G -node guest network, G, on an N H -node host network, H.We call an emulation work-preserving if the time required by the host, T H , is O(T G N G /N H ), because then both the guest and host networks perform the same total work (i.e., processor-time product), ⌰(T G N G ), to within a constant factor.We say that an emulation occurs in real-time if T H ϭ O(T G ), because then the host emulates the guest with constant slowdown.In addition to describing several work-preserving and real-time emulations, we also provide a general model in which lower bounds can be proved.Some of the more interesting and diverse consequences of this work include:(1) a proof that a linear array can emulate a (much larger) butterfly in a work-preserving fashion, but that a butterfly cannot emulate an expander (of any size) in a work-preserving fashion,(2) a proof that a butterfly can emulate a shuffle-exchange network in a real-time work-preserving fashion, and vice versa,(3) a proof that a butterfly can emulate a mesh (or an array of higher, but fixed, dimension) in a real-time work-preserving fashion, even though any O(1)-to-1 embedding of an N-node mesh in an N-node butterfly has dilation ⍀(log N), and (4) simple O(N 2 /log 2 N)-area and O(N 3/ 2 /log 3/2 N)-volume layouts for the N-node shuffle-exchange network.

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiringO(n4/3 log(nL)) time, whereLis the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms.

In this paper, we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the completely connected optical-communication parallel computer (OCPC), which has a completely connected optical network, and also the mesh-of-optical-buses parallel computer (MOB-PC), which has a mesh of optical buses as its communication network. The particular communication problem that we study is that of realizing an h-relation. In this problem, each processor has at most h messages to send and at most h messages to receive. It is clear that any 1-relation can be realized in one communication step on an OCPC. However, the best previously known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires $\Theta(h + \log p)$ expected communication steps. (This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for $h=\Omega(\log p)$, and it is an open question of Geréb-Graus and Tsantilas whether there is a faster algorithm for h=o(log p). In this paper, we answer this question in the affirmative and we extend the range of optimality by considering the case in which $h\leq \log p$. In particular, we present a $\Theta(h + \log\log p)$-communication-step randomized algorithm that realizes an arbitrary h-relation on a p-processor OCPC. We show that if $h\leq \log p$, then the failure probability can be made as small as $p^{-\alpha}$ for any positive constant $\alpha$. We use the OCPC algorithm as a subroutine in a $\Theta(h + \log\log p)$-communication-step randomized algorithm that realizes an arbitrary h-relation on a $p\times p$-processor MOB-PC. Once again, we show that if $h\leq \log p$, then the failure probability can be made as small as $p^{-\alpha}$ for any positive constant $\alpha$.

This paper describes the design and implementation of MPRES, a Multimedia Presentation Toolkit for the WWW. The WWW has seen phenomenal growth over the last couple of years. It has become a vast repository of multimedia information that is accessible to virtually anyone having a browser. MPRES is a multimedia presentation system that allows a user to compose and render a presentation consisting of objects referenced by their URLs (Uniform Resource Locators). It uses the concept of dynamic documents to render on a WWW browser, a sequence of multimedia scenarios, having objects of types such as audio, image, plaintext, HTML (Hypertext Markup Language) document and animation. MPRES Author, the authoring subsystem, allows the user to interactively test and compose such a presentation, using the Netscape Navigator to collect multimedia resources from the WWW. A presentation database stores the presentations and provides a convenient frontend for accessing them. © 1997 John Wiley & Sons,Ltd.

The vertex connectivity /spl kappa/ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{/spl kappa//sup 3/+n,/spl kappa/n}m); for an undirected graph the term m can be replaced by /spl kappa/n. A randomized algorithm finds /spl kappa/ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(/spl kappa//sub 1/nmlog(n/sup 2//m)) where /spl kappa//sub 1//spl les/m/n is the unweighted vertex connectivity, or in expected time O(nm log(n/sup 2//m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow push algorithm of J. Hao and J.B. Orlin (1994) that computes edge connectivity.

We develop a image segmentation algorithm in which the segmented region has both an exterior boundary cost and an interior benefit associated with it. Our segmentation method proceeds by minimizing the ratio between the exterior boundary cost and the enclosed interior benefit using a computationally efficient graph partitioning algorithm. Our interest is motivated by very efficient algorithms for finding the globally optimum solution, and a desire to investigate how weak smoothness constraints may be globally imposed without disallowing very high local curvature. We analyze the performance of the approach, indicating both strengths and weaknesses, and discuss its connections with prior image partitioning algorithms. The relationship with snakes is discussed in detail and it is shown how to efficiently compute an approximation to common snakes under the additional constraint that it enclose a given point. When user interaction is available, there is a clear advantage to minimizing user interaction for purposes of improved speed and ease of use and for robustness. "Ratio regions" can accommodate several levels of user interaction and it is empirically shown that very coarse initializations can be tolerated. User interaction not only guides the algorithm to perceptually salient regions but can also be exploited to significantly reduce the computational cost.

Article Towards efficiency and portability: programming with the BSP model Share on Authors: Mark Goudreau Department of Computer Science, University of Central Florida, Orlando, FL Department of Computer Science, University of Central Florida, Orlando, FLView Profile , Kevin Lang NEC Research Institute, 4 Independence Way, Princeton, NJ NEC Research Institute, 4 Independence Way, Princeton, NJView Profile , Satish Rao NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CA NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CAView Profile , Torsten Suel NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CA NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CAView Profile , Thanasis Tsantilas Department of Computer Science, Columbia University, New York, NY Department of Computer Science, Columbia University, New York, NYView Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 1–12https://doi.org/10.1145/237502.237503Online:24 June 1996Publication History 45citation447DownloadsMetricsTotal Citations45Total Downloads447Last 12 Months4Last 6 weeks0 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

We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a divide-and-conquer approach is applicable. Second, a fractional spreading metric is computable in polynomial time. The spreading metric assigns fractional lengths to either edges or vertices of the input graph, such that all subgraphs on which the optimisation problem is non-trivial have large diameters. In addition, the spreading metric provides a lower bound, /spl tau/, on the cost of solving the optimization problem. We present a polynomial time approximation algorithm for problems modelled by our paradigm whose approximation factor is O (mi.

We address efficient access to bandwidth in WDM (wavelength division multiplexing) optical networks. We consider tree topologies, ring topologies, as well as trees of rings. These are topologies of concrete practical relevance for which undirected underlying graph models have been studied before by P. Raghavan and E. Upfal (1993). As opposed to previous studies (A. Aggarwal et al., 1993; R. Pankaj, 1992; P. Raghavan and E. Upfal, 1993), we consider directed graph models. Directedness of fiber links is dictated by physical directedness of optical amplifiers. For trees, we give a polynomial time routing algorithm that satisfies requests of maximum load L/sub max/ per fiber link using no more than 15L/sub max//8/spl les/15OPT/8 optical wavelengths. This improves a 2L/sub max/ scheme that is implicit by P. Raghavan and E. Upfal by extending their undirected methods to our directed model. Alternatively stated, for fixed W wavelength technology, we can load the network up to L,, 8W/15 rather than W/2. In engineering terms, this is a so called "6.66% increase of bandwidth" and it is considered substantial. For rings, the approximation factor is 2OPT. For trees of rings, the approximation factor is 15OPT/4. Technically, optical routing requirements give rise to novel coloring paradigms. Our algorithms involve matchings and multicolored alternating cycles, combined with detailed potential and averaging analysis.

We present a work-optimal randomized algorithm for simulating a shared memory machine (PRAM) on an optical communication parallel computer (OCPC). The OCPC model is motivated by the potential of optical communication for parallel computation. The memory of an OCPC is divided into modules, one module per processor. Each memory module only services a request on a timestep if it receives exactly one memory request.

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. The previous best algorithms for these problems required\\Omega\\Gamma n p log n) time where n is the number of nodes in the input graph. For the case where negative edge-lengths are allowed, we give an algorithm requiring O(n 4=3 log nL) time, where L is the absolute value of the most negative length. Previous algorithms for shortest paths with negative edge-lengths required \\Omega\\Gamma n 3=2 ) time. Our shortest-path algorithm yields an O(n 4=3 log n)-time algorithm for finding a perfect matching in a planar bipartite graph. A similar improvement is obtained for maximum flow in a directed planar graph.

The existence of bounded degree networks which can emulate the computation of any bounded degree network of the same size with logarithmic slowdown is well-known. The butterfly is an example of such a universal network. Leiserson was the first to introduce the concept of an area-universal network: a network with VLSI layout area A which can emulate any network of the same size and layout area with logarithmic slowdown. His results imply the existence of an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(log N) slowdown. The main results of this paper are: There exists an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(loglogN) slowdown. The N-node butterfly (and hypercube) can emulate any network with VLSI layout area N/sup 2-/spl epsiv// (/spl epsiv/>0) with O(loglogN) slowdown. We also discuss sublogarithmic bounds for the slowdown of emulations of arbitrary bounded degree networks.>

When a numerical computation fails to fit in the primary memory of a serial or parallel computer, a so-called "out-of-core" algorithm must be used which moves data between primary and secondary memories. In this paper, we study out-of-core algorithms for sparse linear relaxation problems in which each iteration of the algorithm updates the state of every vertex in a graph with a linear combination of the states of its neighbors. We give a general method that can save substantially on the I/O traffic for many problems. For example, our technique allows a computer with M words of primary memory to perform T=/spl Omega/(M/sup 1/5/) cycles of a multigrid algorithm for a two-dimensional elliptic solver over an n-point domain using only /spl Theta/(nT/M/sup 1/5/) I/O transfers, as compared with the naive algorithm which requires /spl Omega/(nT) I/O's.>

paper we consider the probcommunication on a Compltd ely Connected Optical Communication Parallel Computer (OCPC).The particular problem we study is that of realizing an h-r-elation.In this problem, each processor has at most h messages to send and at most h messages to receive.It is clear that any 1-relation can be realized in one communication step on an OCPC.However, the best known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires @(h + logp) expected communication steps.(This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for h = f2(log p) and it is an open question of Ger6b-Graus and Tsantilas whether there is a faster algorithm for h = o(logp).In this paper we answer this question in the affirmative by presenting 1

In this paper, we present a new type of graph decomposition called a cut-cover that combines the notions of graph separators and t-neighborhood covers.We show that graphs with good cut-covers can be emulated in hypercubes and butterflies and we show that planar and certain minor-excluded graphs have good cut-covers.In particular, we show how to emulate any N-node bounded degree planar network or any N-node bounded degree graph that excludes KIOgOOl ~as a minor with constant slowdown on hypercube networks.We also show how to emulate any N-node bounded degree planar network or any IV-node bounded degree graph that excludes Ko(l) as a minor with O(log* N) slowdown on butterfly networks.

This paper presents a simple local algorithm for load balancing in a distributed network.The algorithm makes no assumption about the structure of the network.It can be executed on a synchronous network with fixed topology, a synchronous network with dynamically changing topology, or an asynchronous network.It works quickly and balances well when the network has an expansion property.In particular, we show that in an n-node network with maximum degree d whose live edges, at every time step, forma p-expander, the algorithm will balance the load to within an additive O(d log n/p) term in O(A log(nA)/p) time, where A is the initial imbalance.The algorithm improves upon previous approaches that yield O(n) time bounds in dynamic and asynchronous networks.

In this paper we show that, given a graph and parameters 6 and r, we can find either a K,,.minor or an edge-cut of size O(mT/6) whose removal yields components of weak diameter O(T-26); i.e., every pair of nodes in such a component are at distance 0(r26) in the original graph.Using this lemma, we improve the best known bounds for the rein-cut max-flow ratio for mukicommodity flows in graphs with forbidden small minors.In general graphs, it was known that the ratio is O(log k) for the uniform-demand case (the case where there is a unit-demand commodity between every pair of nodes), and that the ratio is 0(log2 k) for arbitrary demands, where k is the number of commodities.In this paper we show that for graphs excluding any fixed graph as a minor (e.g.planar graphs or boundedgenus graphs), the ratio is O(1) for the uniform-demand case and O(log k) for the arbitrary demand case.For such graphs, our method yields rein-ratio cut approximation algorithms with performance bounds that match the above ratios.Computation of such cuts is a basic step for a variety of approximation algorithms for NP-complete problems.

Article Free Access Share on Simple path selection for optimal routing on processor arrays Authors: Christos Kaklamanis View Profile , Danny Krizanc View Profile , Satish Rao View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 23–30https://doi.org/10.1145/140901.140904Published:01 June 1992Publication History 13citation290DownloadsMetricsTotal Citations13Total Downloads290Last 12 Months12Last 6 weeks7 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 SiteeReaderPDF

In this paper, we consider partitioning a planar graph by removing either nodes or edges. In particular, we consider a cut to be either a set of nodes or edges whose removal divides the graph into two pieces.

The computational power of 2-D and 3-D processor arrays that contain a potentially large number of faults is analyzed. Both a random and a worst-case fault model are considered, and it is proved that in either scenario low-dimensional arrays are surprisingly fault tolerant. It is also shown how to route, sort, and perform systolic algorithms for problems such as matrix multiplication in optimal time on faulty arrays. In many cases, the running time is the same as if there were no faults in the array (up to constant factors). On the negative side, it is shown that any constant congestion embedding of an n*n fault-free array on an n*n array with Theta (n/sup 2/) random faults (or Theta (log n) worst-case faults) requires dilation Theta (log n). For 3-D arrays, knot theory is used to prove that the required dilation is Omega ( square root log n).>

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.>

In this paper, we study the problem of emulating TG steps of an NG-node guest network on an NH-node host network. We call an emulation work-preserving if the time required by the host, TH, is Ο(TGNG/NH) because then both the guest and host networks perform the same total work, Θ(TGNG), to within a constant factor. We say that an emulation is real-time if TH = Ο(TG), because then the host emulates the guest with constant delay. Although many isolated emulation results have been proved for specific networks in the past, and measures such as dilation and congestion were known to be important, the field has lacked a model within which general results and meaningful lower bounds can be proved. We attempt to provide such a model, along with corresponding general techniques and specific results in this paper. Some of the more interesting and diverse consequences of this work include:

The packet-routing problem is examined in a network-independent context. The goal is to devise a strategy for routing that works well for a wide variety of networks. To achieve this goal, the routing problem is partitioned into two stages: a path-selection stage and a scheduling stage. In the first stage, paths for the packets are found with small maximum distance and small maximum congestion. Once the paths are fixed, both are lower bounds on the time required to deliver the packets. In the second stage, a schedule is found for the movement of each packet along its path so that no two packets traverse the same edge at the same time and the total time and maximum queue size required to route all of the packets to their destinations are minimized. The second stage is more challenging and is the focus of this study.>

A multicommodity flow problem is considered where for each pair of vertices (u, v) it is required to send f half-units of commodity (u, v) from u to v and f half-units of commodity (v, u) from v to u without violating capacity constraints. The main result is an algorithm for performing the task provided that the capacity of each cut exceeds the demand across the cut by a Theta (log n) factor. The condition on cuts is required in the worst case, and is trivially within a Theta (log n) factor of optimal for any flow problem. The result can be used to construct the first polylog-times optimal approximation algorithms for a wide variety of problems, including minimum quotient separators, 1/3-2/3 separators, bifurcators, crossing number, and VLSI layout area. It can also be used to route packets efficiently in arbitrary distributed networks.>

A k-ratio edge separator is a set of edges which separates a weighted graph into two disconnected sets of components neither of which contains more than k-1/k of the original graph's weight. An optimal quotient separator is an edge separator where the size of the separator (i.e., the number of edges) divided by the weight of the smaller set of components is minimized. An optimal quotient k-ratio separator is an edge separator where the size of the separator (i.e., the number of edges) divided by the smaller of either 1/k of the total weight or the weight of the smaller set of components is minimized. In this paper we present an algorithm that finds the optimal quotient k-ratio separator for any k ≥ 3. We use the optimal quotient algorithm to obtain approximation algorithms for finding optimal k-ratio edge separators for any k ≥ 3. Given a planar graph with a size OPT k-ratio separator, we describe an algorithm which a finds k-ratio separator which costs less than O(OPT log n). More importantly the algorithm finds ck-ratio separators (for any c ≫ 1) which cost less than C(c)OPT, where C(c) depends only on c.