Speeding Up Bellman Ford via Minimum Violation Permutations
Authors: Silvio Lattanzi, Ola Svensson, Sergei Vassilvitskii
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We complement the theoretical analysis with an empirical evaluation, showing that this approach can lead to a significant speed up in practice. |
| Researcher Affiliation | Collaboration | 1Google Research 2EPFL, Switzerland. Correspondence to: Silvio Lattanzi <silviol@google.com>, Ola Svensson <ola.svensson@epfl.ch>, Sergei Vassilvitskii <sergeiv@google.com>. |
| Pseudocode | Yes | Algorithm 3 Greedy Fas(G) |
| Open Source Code | No | The paper does not include any statements about open-sourcing its code or provide a link to a code repository. |
| Open Datasets | Yes | In particular we consider four real-world temporal graphs from the Stanford Large Network Dataset Collection2: College Msg (Panzarasa et al., 2009), email Eu-core (Paranjape et al., 2017), Math Overflow (Paranjape et al., 2017)and Ask Ubuntu (Paranjape et al., 2017). |
| Dataset Splits | No | The paper states how data is split into training (G1, G2, G3) and test (H) sets, but it does not specify a separate validation split or the exact percentages/counts for these splits. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used for running the experiments, such as CPU/GPU models or memory specifications. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers, such as programming languages, libraries, or solvers used in the implementation. |
| Experiment Setup | Yes | In all of our experiments, we begin with four weighted and directed graphs G1, G2, G3 and H. The graphs Gi will serve as a training set which we use to compute a solution to the MVP problem, and the graph H will represent the test where we evaluate the performance of this approach. ... To artificially vary the similarity between graphs, in each experiment we randomly permute node identifiers in the last x% of the layers in each graph. ... The choice of s induces shortest path trees in each of the training graphs, Gi, which then serve as input to the MVP problem. We then run Algorithm 3 to obtain a permutation on the nodes, and use that to evaluate the performance of Bellman-Ford in the graph H. Specifically, the input to Algorithm 3 is the graph formed by taking the union of the shortest path trees in G1, G2, and G3. |