Fair Submodular Maximization over a Knapsack Constraint
Authors: Lijun Li, Chenyang Xu, Liuyi Yang, Ruilong Zhang
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | 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. |