.png){kind=icon}
返回
Optimizing the Maximum Vertex Coverage Attacks Under Knapsack Constraint
.png){kind=icon}
PRE
AI
DOI：10.1109/TNET.2021.3056450.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Only when we understand how hackers think, can we defend against their attacks. Towards this end, this paper studies the cyber-attacks that aim to remove nodes or links from network topologies. We particularly focus on one type of such attacks called Maximum Vertex Coverage Attacks under Knapsack constraint (MVCAK), in which a hacker has a fixed budget to remove nodes from a network with the nodes involving different costs for removal, and the hacker's goal is to maximize the number of links incident to the nodes removed. Since the MVCAK problem is NP-hard, we firstly propose an optimal solution by Integer Linear Program formulation. Secondly, we give an approximate solution by Linear Programming relaxation that achieves an approximation ratio of 3/4, outperforming the existing 1 - 1/sqrt(e) (about 0.39). Thirdly, since the straightforward implementation of our approximate solution has a high time complexity, we propose two heuristics to significantly reduce its complexity while preserving the approximation ratio. We formally prove the correctness and the effectiveness of these two heuristics. Finally, we conduct extensive experiments on both artificial and real-world networks, showing that our approximate solution produces almost the same results as the optimal solution in practice and has an acceptable running time.
Keyword:
Approximation algorithms
Linear programming
Computer hacking
Time complexity
Complexity theory
Heuristic algorithms
Silicon
Network topology
maximum vertex coverage attacks
Knapsack constraint
linear programming
approximation algorithms
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
3.6
论文数:
4.4K
被引数:
9.5K
机构
引用论文
分享收藏Pain, perceived injustice and the persistence of post-traumatic stress symptoms during the course of rehabilitation for whiplash injuries鞭打伤康复过程中的疼痛，感知到的不公正和创伤后应激症状的持续存在.png)
Pain
PainIF0
PREAI
分享收藏
Does it take older adults longer than younger adults to perceptually segregate a speech target from a background masker?在感知上将语音目标与背景掩蔽器隔离开来是否需要老年人比年轻人更长的时间？
PREAI
分享收藏
查看更多内容