Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Submodular Function Maximization Over Graphs via Zero-Suppressed Binary Decision Diagrams
Authors: Shinsaku Sakaue, Masaaki Nishino, Norihito Yasuda
AAAI 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments show that our algorithm runs much faster than exact algorithms and ๏ฌnds better solutions than those obtained by an existing approximation algorithm in many instances. Notably, our algorithm achieves better than a 90%-approximation in all instances for which optimal values are available. |
| Researcher Affiliation | Industry | Shinsaku Sakaue, Masaaki Nishino, Norihito Yasuda NTT Communication Science Laboratories, NTT Corporation EMAIL |
| Pseudocode | Yes | Algorithm 1 Greedy DP(ZF, f) 1: U = N\{r}. 2: Create a topological order of all n U. 3: Rr,n = for all n N. 4: while U = do 5: Let n U be the ๏ฌrst node in the topological order. 6: (n , n) = argmax (n ,n) An f(Rr,n (n , n)). 7: Rr,n = Rr,n (n , n). 8: U = U\{n}. 9: end while 10: return Rr,1. |
| Open Source Code | No | The paper states: |
| Open Datasets | Yes | This experiment uses air quality sensor data monitored at 11 stations in Shanghai, China (Zheng, Liu, and Hsieh 2013), and we focus on PM2.5 data. |
| Dataset Splits | No | The paper describes experiments involving optimizing a function on graph instances, not training machine learning models with explicit train/validation/test splits. Therefore, the concept of a 'validation split' as typically understood in machine learning is not directly applicable. |
| Hardware Specification | Yes | All experiments were performed on a computer equipped with 128 GB RAM and Xeon E5 3.1 GHz CPU. |
| Software Dependencies | No | The paper mentions: |
| Experiment Setup | Yes | The 2-D target space is discretized by the grid graph G = (V, E). We discretize the target space by using 5x9 and 7x13 grids. For simplicity, we suppose that the cost of traversing one edge is always 1, and the obtained path X E must satisfy the budget constraint |X| B for some B > 0. To assess the scalability of algorithms, we consider all feasible budget values: B = 1, 3, . . . , 43 for the 5x9 grid and B = 1, 3, . . . , 89 for the 7x13 grid. |