Provable Submodular Minimization using Wolfe's Algorithm
Authors: Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari
NeurIPS 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our analysis suggests that the Fujishige-Wolfe s algorithm is dependent on F and has worse dependence on n than the Iwata-Orlin [11] algorithm. To verify this, we conducted empirical study on several standard SFM problems. |
| Researcher Affiliation | Collaboration | Microsoft Research, 9 Lavelle Road, Bangalore 560001. University of Texas at Austin (Part of the work done while interning at Microsoft Research) |
| Pseudocode | Yes | Algorithm 1 Wolfe s Algorithm |
| Open Source Code | No | The paper does not contain any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | Yes | In Figure 1 (a), we run both on Erdos-Renyi graphs with p = 0.8 and randomly chosen s, t nodes. In Figure 1 (b), we run both on the Iwata group functions [16] with 3 groups. |
| Dataset Splits | No | The paper discusses empirical studies but does not provide specific details on training, validation, or test dataset splits. |
| Hardware Specification | No | The paper describes empirical studies but does not provide any specific hardware specifications such as CPU or GPU models used for the experiments. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers for replication. |
| Experiment Setup | Yes | In Figure 1 (a), we run both on Erdos-Renyi graphs with p = 0.8 and randomly chosen s, t nodes. In Figure 1 (b), we run both on the Iwata group functions [16] with 3 groups. Perhaps more interestingly, in Figure 1 (c), we ran the Fujishige-Wolfe algorithm on the simple path graph where s, t were the end points, and changed the capacities on the edges of the graph which changed the parameter F. |