Instance Specific Approximations for Submodular Maximization
Authors: Eric Balkanski, Sharon Qian, Yaron Singer
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We use this method to show that on a wide variety of real-world datasets and objectives, the approximation of the solution found by greedy goes well beyond 1 1/e and is often at least 0.95. We develop this method using a novel technique that lower bounds the objective of a dual minimization problem to obtain an upper bound on the value of an optimal solution to the primal maximization problem. [...] 5. Experiments We utilize DUAL to obtain bounds on the approximation achieved by submodular maximization algorithms in prac tice. We show that GREEDY and other algorithms find solutions that approximate the optimal solution significantly better than 1 1/e on a wide variety of real-world datasets and objectives. |
| Researcher Affiliation | Academia | 1Columbia University, New York, NY, USA 2Harvard Univer sity, Cambridge, MA, USA. Correspondence to: Eric Balkanski <eb3224@columbia.edu>. |
| Pseudocode | Yes | Method 1 Linear bound on dual objective for coverage input bipartite graph G = (P, D, E), constraint k [...] Method 2 Dual bound via partitioning for coverage input bipartite graph G = (P, D, E), constraint k [...] Method 3 Method for submodular functions input function f, cardinality constraint k [...] Method 4 DUAL input function f, constraint k, collection of sets S |
| Open Source Code | No | The paper does not provide any links to source code or explicitly state that the code for their method is open-sourced or publicly available. |
| Open Datasets | Yes | Influence maximization: As in Mirzasoleiman, Badani diyuru, and Karbasi (2016a), we use Youtube social network data (Yang & Leskovec, 2015) [...] Car dispatch: As in Balkanski and Singer (2018), we analyze n = 1, 000 locations of Uber pickups (Five Thirty Eight, 2019) [...] Influence maximization: We use a citation network of Physics collaborations (Leskovec et al., 2007) [...] Movie recommendation: As in Mirzasoleiman, Badani diyuru, and Karbasi (2016a), we use the Movie Lens dataset (Harper & Konstan, 2015) [...] Revenue maximization: We use a revenue maximization objective from Breuer, Balkanski, and Singer (2020) on the Cal Tech Facebook Network dataset (Traud et al., 2012) [...] Feature selection: We use the Adult Income dataset (Blake & Merz, 1998) [...] Sensor placement: As in Krause, Singh, and Guestrin (2008), we use the Berkeley Intel Lab dataset |
| Dataset Splits | No | The paper does not explicitly specify dataset splits for training, validation, or testing (e.g., percentages, sample counts, or cross-validation setup). |
| Hardware Specification | No | The paper does not provide specific details about the hardware used to run the experiments, such as GPU/CPU models or memory specifications. |
| Software Dependencies | No | The paper does not mention specific software dependencies with version numbers (e.g., Python version, specific library or framework versions like PyTorch, TensorFlow, scikit-learn, etc.). |
| Experiment Setup | Yes | For randomized algorithms, we average the results over 5 runs. [...] Settings. We examine the approximations computed by DUAL for these algorithms on 8 different datasets and ob jectives. Additional details can be found in Appendix E.1. |