Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Fair Submodular Maximization over a Knapsack Constraint
Authors: Lijun Li, Chenyang Xu, Liuyi Yang, Ruilong Zhang
IJCAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This work makes progress in finding a non-trivial approximation for FKSM. To overcome the challenges mentioned above, we propose a novel technique: knapsack truncating and combine it with the randomized weighted pipage rounding. ... Theorem 1.1. Given an FKSM instance with a constant number of groups, there exists a polynomial-time algorithm that achieves an approximation ratio of 1 e ϵ with probability at least 1 1 e2 for any ϵ > 0. |
| Researcher Affiliation | Academia | Lijun Li1 , Chenyang Xu2 , Liuyi Yang2 and Ruilong Zhang3 1 Department of Computer Science, City University of Hong Kong, Hong Kong, China 2 Software Engineering Institute, East China Normal University, Shanghai, China 3 Department of Mathematics, Technical University of Munich, Munich, Germany EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 Knapsack Truncating; Algorithm 2 Feasibility Extension; Algorithm 3 Randomized Weighted Pipage Rounding |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that open-source code for the described methodology is provided. |
| Open Datasets | No | The paper defines a theoretical problem and proposes algorithms and proofs; it does not present empirical results or refer to any specific datasets for experimentation. |
| Dataset Splits | No | As the paper focuses on theoretical contributions and does not involve empirical experiments with datasets, there is no discussion of dataset splits. |
| Hardware Specification | No | The paper presents theoretical algorithms and proofs, without performing empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical in nature, focusing on algorithm design and mathematical proofs; it does not describe any specific software implementations or their dependencies with version numbers. |
| Experiment Setup | No | The paper is a theoretical work presenting algorithms and proofs, and does not include an experimental section or details on an experimental setup. |