Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint
Authors: Tan D. Tran, Canh V. Pham, Dung T. K. Ha, Phuong N. H. Pham
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Extensive experimental studies on three applications, Revenue Maximization, Image Summarization, and Maximum Weighted Cut, show that our algorithm not only significantly increases solution quality but also requires comparative adaptivity to state-of-the-art algorithms. |
| Researcher Affiliation | Academia | 1ORLab, Faculty of Computer Science, Phenikaa University, Hanoi, Vietnam 2 Faculty of Information Technology, VNU University of Engineering and Technology, Hanoi, Vietnam 3 Faculty of Information Technology, Ho Chi Minh City University of Industry and Trade, Ho Chi Minh, Vietnam |
| Pseudocode | Yes | Algorithm 1: AST Algorithm |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code for the described methodology or links to a code repository. |
| Open Datasets | Yes | As in the prior work, [Amanatidis et al., 2021], we can construct the graph G using a You Tube community network dataset [Han et al., 2021] with 39,841 nodes and 224,235 edges. As in recent work [Amanatidis et al., 2020], we generate an Erd os-R enyi random graph with 5, 000 nodes and an edge probability of 0.2. As in recent works [Han et al., 2021; Mirzasoleiman et al., 2016], we create an instance as follows: First, randomly sample 500 images from the CIFAR dataset [Krizhevsky, 2019] of 10,000 images |
| Dataset Splits | No | The paper mentions using specific datasets but does not explicitly provide details about training, validation, or test dataset splits (e.g., percentages, counts, or references to predefined splits). |
| Hardware Specification | Yes | Besides, we experimented on a high-performance computing (HPC) server cluster with the following parameters: partition=large, #threads(CPU)=128, node=4, max memory = 3,073 GB. |
| Software Dependencies | No | The paper states 'We used Open MP to program with C++ language' but does not specify version numbers for the programming language or any libraries used. |
| Experiment Setup | Yes | In our experiments, we set the accuracy parameter ϵ = 0.1 for all algorithms evaluated, and for AST, we set δ = 0.12. |