Submodular Optimization with Routing Constraints
Authors: Haifeng Zhang, Yevgeniy Vorobeychik
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental evaluation on realistic mobile sensing and door-to-door marketing problems, as well as using simulated networks, show that our algorithm achieves significantly higher utility than state-of-the-art alternatives, and has either lower or competitive running time. |
| Researcher Affiliation | Academia | Haifeng Zhang and Yevgeniy Vorobeychik Electrical Engineering and Computer Science Vanderbilt University Nashville, TN {haifeng.zhang, yevgeniy.vorobeychik}@vanderbilt.edu |
| Pseudocode | Yes | Algorithm 1: Generalized Cost-benefit Algorithm. Data: B > 0 Result: Selection S V A := arg max{f(X)|X V, ˆc(X) B}; G := ; V := V ; while V = do foreach X V do ΔX f := f(G X) f(G); ΔX c := ˆc(G X) ˆc(G); end X = arg max{ΔX f /ΔX c |X V }; if ˆc(G X ) B then G := G X ; end V := V \X end return arg max S {A,G} f(S) |
| Open Source Code | No | The paper does not provide any statement about releasing source code or a link to a code repository for the methodology described. |
| Open Datasets | Yes | Our experiments use sensor data representing air quality measurements for 36 air quality monitoring stations in Beijing, China (Zheng, Liu, and Hsieh 2013)... Our first influence network was generated to represent adoption of a highly visible technology, such as rooftop solar (Zhang et al. 2015)... we use the well-known Barabasi-Albert (BA) model (Albert and Barab asi 2002)... and the Erdos-Renyi (ER) model to generate the routing network (Erdos and Renyi 1959). |
| Dataset Splits | No | The paper mentions the datasets used for experiments but does not provide specific details on how the data was split into training, validation, or test sets. |
| Hardware Specification | Yes | All experiments were performed on an Ubuntu Linux 64-bit PC with 32 GB RAM and an 8-core Intel Xeon 2.1 GHz CPU. Each experiment used a single thread. |
| Software Dependencies | No | The paper mentions algorithms and models used (e.g., Nearest Neighbor, Gaussian Process, Independent Cascade model), but it does not specify any particular software names with version numbers (e.g., Python, PyTorch, TensorFlow, specific libraries like scikit-learn or optimization solvers with their versions) that would be needed for replication. |
| Experiment Setup | Yes | In our experiments below, we used pvw = 0.1 for all network edges (v, w). In our implementation, we generated a BA social network over 200 nodes, adding m = 2 edges in each iteration. The ER model is the simplest generative model of networks, where each edge is added to the network with a fixed probability p. In our experiments, we considered values of p {0.01, 0.02, 0.03}. |