Submodular Function Maximization Over Graphs via Zero-Suppressed Binary Decision Diagrams
Authors: Shinsaku Sakaue, Masaaki Nishino, Norihito Yasuda
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments show that our algorithm runs much faster than exact algorithms and finds 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 {sakaue.shinsaku, masaaki.nishino, yasuda.n}@lab.ntt.co.jp |
| 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 first 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. |