检索结果-南通市图书馆

计算机工程与应用 1981年第7期 1-71页

作者： michael r.garey David S.Johnson 沈泓

在计算复杂性理论中已发现了几百个难题,著名的货郎担问题就是其中一例。这一类问题都是问:是否存在有解某一特定的大量问题的实际可行的算法(用专门术语来说,即是否有计算时间多项式有界的算法)?现在已经知道的是,对非决定的机器而言,... 详细信息

在计算复杂性理论中已发现了几百个难题,著名的货郎担问题就是其中一例。这一类问题都是问:是否存在有解某一特定的大量问题的实际可行的算法(用专门术语来说,即是否有计算时间多项式有界的算法)?现在已经知道的是,对非决定的机器而言,这些问题是有计算时间多项式有界的算法的,即是所说的复杂性属于NP类的问题,而且是NP类中难度最大的问题(用专门术语来说,是具有NP完全性的问题)。但对于决定的机器(实际计算机都是决定的机器)而言,是否有计算时间多项式有界的算法(即计算机上实际可行的算法)呢?目前还不知道。这一类问题具有下列的重要性质:只要能找到其中一个特定问题的实际可行的算法,就可以找到其他几百个问题的同类算法,而如果能证明其中某一个问题没有实际可行的算法,那么也就证明了其它几百个问题都没有这样的算法。由于这一类问题在许多数学分支(如代数、数论、数理逻辑和图论等)和工程技术中出现,而只要解决了其中的一个就解决了同类的千百个问题,这类问题一旦解决将有无比重要的理论意义和实际意义。这就是计算复杂性理论中所说的P=?NP的问题,这个问题被许多有关的科学工作者认为是当前计算机科学中最大的未解决的问题之一(目前绝大多数有关的科学工作者的猜测是:答案是否定的,即P≠NP)。美国贝尔电话公司研究所的研究员garey 和 Johnson二人在1979年出版了《计算机与难解性——一本NP完全性理论的指南》(Computers and Intractability:AGuide to the Theory of NP Completeness)一书。他们搜集了到1978年夏天为止已发现的三百个具有NP完全性的问题,索编成这书的附录。这一问题索编对于从事这方面研究工作的人是不可缺少的参考资料。

关键词：子集有限集注释注解 NP 多项式正整数等价性顶点的度矩阵数学分析可解性所有诱导子图子序列变量符号

来源：

同方期刊数据库评论

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Increasing public safety broadband network resiliency through traffic control

引用

Digital Communications and Networks 2018年第1期4卷 48-57页

作者： r. rouil W. garey C. Gentile N. Golmie P. Schwinghammer National Institute of Standards and Technology USA First responder Network Aulhority USA

Long Term Evolution （LTE）-based cellular networks are being deployed around the world to provide public safety with enhanced capabilities and access to broadband technology. In the United States, the First responder Network Authority （FirstNet） is on the verge of deploying a nationwide network called the National Public Safety Broadband Network （NPSBN）. Commercial networks typically aim at maximizing network capacity, i.e. the aggregate data rate, in order to increase revenue. However, in public safety networks, coverage, not capacity, is paramount, especially during an outage when sites are down. Through traffic control and preemption, the service level of low-priority users is reduced or denied, fleeing up resources to restore coverage to high-priority users, e.g. users responding to an incident. In this study, we examine the effect of outages on network coverage and throughput. As our main contribution, we propose three traffic-control schemes that exploit variable modulation and coding, a feature that LTE enhances with respect to its 3G predecessors. The schemes differ based on the proportion of low- and high-priority users preempted. We show that the network coverage can be restored significantly and we investigate the tradeoff between the three schemes. Finally, we perform sensitivity analysis to confirm the effectiveness of the schemes across a wide range of scenarios.

关键词： Network resiliency Network outage Incident Modeling

来源：