Deletion-Robust Submodular Maximization with Knapsack Constraints
Authors: Shuang Cui, Kai Han, He Huang
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The empirical performance of our algorithm is extensively evaluated in several applications including influence maximization and recommendation systems, and the experimental results demonstrate the effectiveness of our algorithm. In this section, we compare our streaming algorithm RSK-Streaming with state-of-the-art streaming algorithms for solving the RSK-Streaming problem, on the real-world application. |
| Researcher Affiliation | Academia | Shuang Cui1, Kai Han2*, He Huang2 1 School of Computer Science and Technology / Suzhou Institute for Advanced Research, University of Science and Technology of China 2 School of Computer Science and Technology, Soochow University lakers@mail.ustc.edu.cn, hankai@suda.edu.cn, huangh@suda.edu.cn |
| Pseudocode | Yes | The paper includes 'Algorithm 1: RSK-Streaming-Summary' and 'Algorithm 2: RSK-Streaming-Mining', which are clearly labeled algorithm blocks presenting structured steps. |
| Open Source Code | No | The paper does not contain any explicit statement about providing open-source code for the described methodology, nor does it provide a link to a code repository. |
| Open Datasets | Yes | For our experiments, we utilize two network datasets: (1) epinions (Leskovec and Krevl 2014) with 131,828 nodes and 841,372 edges; and (2) wiki (Rossi and Ahmed 2015) with 138,592 nodes and 740,397 edges. |
| Dataset Splits | No | The paper mentions evaluating performance on real-world applications and running randomized algorithms multiple times, but it does not specify explicit training, validation, or test dataset splits (e.g., percentages, sample counts, or specific splitting methodology). |
| Hardware Specification | Yes | all experiments are conducted on a Linux server equipped with an Intel Xeon Gold 6126 @ 2.60GHz CPU and 256GB memory. |
| Software Dependencies | No | The paper mentions using specific algorithms as sub-algorithms (e.g., SMMK (Han et al. 2021) algorithm) but does not provide any specific software dependencies with version numbers (e.g., programming languages, libraries, frameworks). |
| Experiment Setup | Yes | Each randomized algorithm is executed independently five times and the average result is reported, and all experiments are conducted on a Linux server equipped with an Intel Xeon Gold 6126 @ 2.60GHz CPU and 256GB memory. The implemented algorithms are evaluated in two real-world applications, including robust influence maximization and interactive movie recommendation. For the purposes of comparison, we assume that KS is omniscient and is thus aware of the removed element in advance, which allows KS to effectively solve the RSK problem and serve as a strong comparison for our algorithm. In our experiments, we utilize the objective function value (i.e., utility) as the primary metric, and also evaluate the summary size of our algorithm against that of another robust algorithm (i.e., Alg Mult). Following the approach of previous work on robust submodular optimization (D utting et al. 2022b; Kazemi, Zadimoghaddam, and Karbasi 2018; Zhang, Tatti, and Gionis 2022), the state-of-the-art practical algorithm for the SK problem (i.e., the SMMK (Han et al. 2021) algorithm) is utilized to generate the set R of removed elements and serves as the sub-algorithm called by any algorithm that requires an offline sub-algorithm, and we set ϵ = 0.5 to avoid large summary. |