Defending with Shared Resources on a Network
Authors: Minming Li, Long Tran-Thanh, Xiaowei Wu2111-2118
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give polynomial time exact algorithms for two important special cases of the network defending problem. For the case when an attack can only affect the target node, we present an LP-based exact algorithm. For the case when defending resources cannot be shared, we present a max-flow-based exact algorithm. We show that the general problem is NP-hard, and we give a 2-approximation algorithm based on LP-rounding. |
| Researcher Affiliation | Academia | Minming Li,1 Long Tran-Thanh,2 Xiaowei Wu3 1Department of Computer Science, City University of Hong Kong 2Department of Economics and Computer Science, University of Southampton 3Faculty of Computer Science, University of Vienna |
| Pseudocode | No | The paper describes algorithms using linear programming and maximum flow techniques, but it does not present them in structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not conduct empirical studies or use datasets; therefore, no information about publicly available datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation with datasets, so it does not provide specific dataset split information for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and proofs, thus it does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details or hyperparameters. |