Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule
Authors: Bo Li, Xiaowei Wu, Chenyang Xu, Ruilong Zhang
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We first show that this problem is NP-hard and does not admit better than ((1 o(1)) ln k)-approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents rankings on the edges. Finally, we extend our results to submodular objective functions and Matroid rank constraints. |
| Researcher Affiliation | Academia | 1 Department of Computing, The Hong Kong Polytechnic University 2 IOTSC, University of Macau 3 Software Engineering Institute, East China Normal University 4 College of Computer Science, Zhejiang University 5 Department of Computer Science, City University of Hong Kong |
| Pseudocode | Yes | Algorithm 1: Kruskal s Algorithm; Algorithm 2: Computing a Perfect MST Cover; Algorithm 3: Multi-Round Plural Voting Algorithm |
| Open Source Code | No | The paper does not provide any links to source code or explicitly state that the code for their methodology is open-source or publicly available. |
| Open Datasets | No | This paper is theoretical and focuses on algorithm design, hardness proofs, and approximation ratios. It does not involve experimental evaluation on datasets, and therefore, does not refer to publicly available datasets or provide access information for them. |
| Dataset Splits | No | This paper is theoretical and focuses on algorithm design and proofs. It does not involve experimental evaluation on datasets, and therefore, does not discuss training/validation/test dataset splits. |
| Hardware Specification | No | This paper is theoretical and focuses on algorithm design and proofs. It does not describe any experimental setup or the hardware used to run experiments. |
| Software Dependencies | No | This paper is theoretical and focuses on algorithm design and proofs. It does not describe any experimental setup or specific software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and focuses on algorithm design and proofs. It does not describe an experimental setup, hyperparameters, or system-level training settings. |