Diverse Approximations for Monotone Submodular Maximization Problems with a Matroid Constraint
Authors: Anh Viet Do, Mingyu Guo, Aneta Neumann, Frank Neumann
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experimental investigation with maximum vertex coverage instances demonstrates their empirical differences in terms of objective-diversity trade-offs. |
| Researcher Affiliation | Academia | Anh Viet Do , Mingyu Guo , Aneta Neumann and Frank Neumann Optimisation and Logistics, School of Computer and Mathematical Sciences, The University of Adelaide {vietanh.do,mingyu.guo,aneta.neumann,frank.neumann}@adelaide.edu.au |
| Pseudocode | Yes | Algorithm 1: Greedy with common elements; Algorithm 2: Greedy with representation limits |
| Open Source Code | No | The paper does not provide any statements or links indicating that the source code for the described methodology is publicly available. |
| Open Datasets | Yes | For the benchmark instance, we use the complement of frb30-15-1, frb30-15-2, frb35-17-1, frb40-19-1 from the standard benchmark suite BHOSLIB created using the Model RB [Xu and Li, 2006], containing 450, 450, 595, 760 vertices respectively, and 17827, 17874, 27856, 41314 edges respectively; these are available at [Rossi and Ahmed, 2015]. |
| Dataset Splits | No | The paper references benchmark instances but does not provide specific details on how these datasets are split into training, validation, or testing sets. |
| Hardware Specification | No | The paper does not specify any hardware details such as GPU/CPU models, memory, or cloud computing resources used for the experiments. |
| Software Dependencies | No | To contextualize the results, we obtain a best known coverage for each instance using the built-in integer linear programming solver in MATLAB. (The specific version of MATLAB or the solver is not provided). |
| Experiment Setup | Yes | For each of the 16 instances, we run with r {20, 100}, Algorithm 1 with all parameter values b [0, r M], and Algorithm 2 with all parameter values l [1, r]. For both algorithms, the last tie-breaking is done by selecting the first choice (in increasing order of vertex labels). |