Zwick's @math -approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time @math , where @math is the exponent of matrix multiplication and @math denotes the largest weight. This can be used to approximate several graph characteristics including the diameter, radius, median, minimum-weight triangle, and minimum-weight cycle in the same time bound. Since Zwick's algorithm uses the scaling technique, it has a factor @math in the running time. In this paper, we study whether APSP and related problems admit approximation schemes avoiding the scaling technique. That is, the number of arithmetic operations should be independent of @math ; this is called strongly polynomial. Our main results are as follows. - We design approximation schemes in strongly polynomial time @math for APSP on undirected graphs as well as for the graph characteristics diameter, radius, median, minimum-weight triangle, and minimum-weight cycle on directed or undirected graphs. - For APSP on directed graphs we design an approximation scheme in strongly polynomial time @math . This is significantly faster than the best exact algorithm. - We explain why our approximation scheme for APSP on directed graphs has a worse exponent than @math : Any improvement over our exponent @math would improve the best known algorithm for Min-Max Product In fact, we prove that approximating directed APSP and exactly computing the Min-Max Product are equivalent.
We show that the all pairs shortest paths (APSP) problem for undirected graphs with integer edge weights taken from the range 1, 2, ..., M can be solved using only a logarithmic number of distance products of matrices with elements in the range (1, 2, ..., M). As a result, we get an algorithm for the APSP problem in such graphs that runs in O (Mn sup spl omega ) time, where n is the number of vertices in the input graph, M is the largest edge weight in the graph, and spl omega <2.376 is the exponent of matrix multiplication. This improves, and also simplifies, an O (M sup ( spl omega +1) 2 n sup spl omega ) time algorithm of Galil and Margalit (1997).  The authors have solved the all pairs shortest distances (APSD) problem for graphs with integer edge lengths. Our algorithm is subcubic for edge lengths of small (?M) absolute value. In this paper we show how to transform these algorithms to solve the all pairs shortest paths (APSP), in the same time complexity, up to a polylogarithmic factor. Forn=|V| the number of vertices,Mthe bound on edge length, and?the exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSP(n, M) algorithm which runs inO(T(n, M)) time, where T(n, m)= 2. An undirected APSP(n, M) algorithm which runs inO(M(?+1) 2n?log(Mn)) time. 3. A general APSP(n, M) algorithm which runs inO((Mn)(3+?) 2). The upper bound on the exponent,?, of matrix multiplication over a ring that was three in 1968 has decreased several times and since 1986 it has been 2.376. On the other hand, the exponent of the algorithms known for the all pairs shortest path problem has stayed at three all these years even for the very special case of directed graphs with uniform edge lengths. In this paper we give an algorithm of timeO(n?log3n),?=(3+?) 2, for the case of edge lengths in ?1, 0, 1 . Thus, for the current known bound on?, we get a bound on the exponent,?<2.688. In case of integer edge lengths with absolute value bounded above byM, the time bound isO((Mn)?log3n) and the exponent is less than 3 forM=O(n?), for?<0.116 and the current bound on?.  Let @math be the maximal value such that the product of an @math matrix by an @math matrix can be computed with @math arithmetic operations. In this paper we show that @math , which improves the previous record @math by Coppersmith (Journal of Complexity, 1997). More generally, we construct a new algorithm for multiplying an @math matrix by an @math matrix, for any value @math . The complexity of this algorithm is better than all known algorithms for rectangular matrix multiplication. In the case of square matrix multiplication (i.e., for @math ), we recover exactly the complexity of the algorithm by Coppersmith and Wino grad (Journal of Symbolic Computation, 1990). These new upper bounds can be used to improve the time complexity of several known algorithms that rely on rectangular matrix multiplication. For example, we directly obtain a @math -time algorithm for the all-pairs shortest paths problem over directed graphs with small integer weights, where @math denotes the number of vertices, and also improve the time complexity of sparse square matrix multiplication. This paper presents a method to analyze the powers of a given trilinear form (a special kind of algebraic construction also called a tensor) and obtain upper bounds on the asymptotic complexity of matrix multiplication. Compared with existing approaches, this method is based on convex optimization, and thus has polynomial-time complexity. As an application, we use this method to study powers of the construction given by Coppersmith and Winograd [Journal of Symbolic Computation, 1990] and obtain the upper bound ω