Public Event Scheduling with Busy Agents
Authors: Bo Li, Lijun Li, Minming Li, Ruilong Zhang
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We first show that the problem is NP-hard, and then prove that a simple greedy algorithm achieves 1/2-approximation when the whole timeline is polynomially bounded. Our method also implies a (1-1/e)-approximate algorithm for this case. Subsequently, for the general timeline case, we present an algorithmic framework that extends a 1/alpha-approximate algorithm for the one-event instance to the general case that achieves 1/(alpha+1)-approximation. Finally, we give a polynomial time algorithm that solves the one-event instance, and this implies a 1/2-approximate algorithm for the general case. |
| Researcher Affiliation | Academia | Bo Li1 , Lijun Li2 , Minming Li2 and Ruilong Zhang3 1Department of Computing, The Hong Kong Polytechnic University 2Department of Computer Science, City University of Hong Kong 3Department of Computer Science and Engineering, University at Buffalo |
| Pseudocode | Yes | Algorithm 1 The Complete Algorithm for PESBA; Algorithm 2 Natural Greedy for SMGC; Algorithm 3 Good Posn |
| Open Source Code | No | The paper does not provide an explicit statement about releasing open-source code or a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not involve training on a dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe hardware specifications for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |