Research map / Graph learning / Graph algorithms and clustering
Defending with Shared Resources on a Network
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LP feasibility tests with binary search in the single-threshold case | Network defending problem with LB_u = UB_u for every node · Single Threshold Model | running time: O(n^ω log n) | Helped |
| Use a maximum-flow test with binary search in the isolated case | Network defending problem with w_uv = 0 for all edges · Isolated Model | running time: O(mn log n) | Helped |
| Apply LP rounding with resource augmentation | General network defending problem · General network defending problem | resource augmentation approximation ratio: 2-approximation | Helped |
| Use LP rounding for the general problem | General network defending problem · General network defending problem | running time: O(mn log n) | Helped |
| Use LP rounding rather than an exact polynomial-time method for the general case | General network defending problem · General network defending problem | computational complexity | Mixed |
| Use resource augmentation instead of approximating the damage objective directly | General network defending problem · General network defending problem | approximation guarantee for minimizing defending result | Hurt |
| Allocate resources greedily to the currently vulnerable node rather than planning globally | Greedy · Isolated model, Greedy hard instance | defending result: 0 -> 10 | Hurt |
| Allocate resources greedily to the currently vulnerable node rather than planning globally | Greedy · Single Threshold Model, Greedy hard instance | defending result: 0 -> 10 | Hurt |
Closest papers by meaning
- Defending against Contagious Attacks on a Network with Resource Reallocation (AAAI 2021 · similarity 0.88)
- Discounted Cuts: A Stackelberg Approach to Network Disruption (AAAI 2026 · similarity 0.86)
- Finding Minimum-Weight Link-Disjoint Paths with a Few Common Nodes (AAAI 2020 · similarity 0.85)
- On Improving Resource Allocations by Sharing (AAAI 2022 · similarity 0.84)
- Practical Fixed-Parameter Algorithms for Defending Active Directory Style Attack Graphs (AAAI 2022 · similarity 0.83)
- Coalition Formation in Multi-defender Security Games (AAAI 2021 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.