all_pairs_shortest_path_approximate (907B)
1 # All pairs shortest path approximate 2 3 See also roditty2023new 4 5 For approximation ratio alpha<2, with directed or undirected graph, reduction from [boolean_matrix_multiplication] (exact?) 6 7 for approximation (1+eps), zwick2022?: Otilde(n^omega/eps log W) 8 - if the graph is undirected we can shave off the log W 9 - if directed we can shave off the log W but at the expense of a worse exponent, and equivalence to "exact MinMaxProduct"? 10 11 connection to approximate [distance_product] (equivalence up to log factors) 12 13 for an undirected graph, for any k, we can preprocess the graph in O(m n^{1/k}) such that for each pair we obtain in constant time a 2k-1 approximation of the distance 14 - and lower bound from [3sum]: under this preprocessing and with n^{o(1)} query time we cannot have <k approx (work involving [amir_abboud]) 15 - "hardness of approximation in P"? 16 17 Up: [approximation] of [all_pairs_shortest_path]