检索结果-内蒙古大学图书馆

Dismantling Networks by Skeleton Extraction and Greedy Tree Breaking

IEEE ACCESS 2021年 9卷 84922-84931页

作者： Rui, Xiaobin Meng, Fanrong Chai, Yahui Wang, Zhixiao Yu, Philip S. China Univ Min & Technol Sch Comp Sci & Technol Xuzhou 221116 Jiangsu Peoples R China Minist Educ Peoples Republ China Mine Digitizat Engn Res Ctr Xuzhou 221116 Jiangsu Peoples R China Univ Illinois Dept Comp Sci Chicago IL 60607 USA

Network dismantling is one of the important NP-hard problems in the field of social network analysis. It aims to break down networks into many small components of limited size by only removing a small group of nodes. One feasible way is to decycle (eliminating all the cycles) the network first and then break the acyclic graph. However, existing decycling-based algorithms mainly concentrate on the decycling step, ignoring the importance of the tree breaking process. Besides, none of the algorithms try to pre-process the network, which may bring improvement in both effectiveness and efficiency. In this paper, we fill these two gaps by proposing a novel network dismantling algorithm that combines skeleton extraction and greedy tree breaking (SEGTB). Network skeleton supports the whole network structure, whose removal would leave a much looser structure and serves as an effective pre-processing for the dismantling problem. The presented tree breaking method is provided with theoretical proofs on its lower bound. Experiments on ten real-world datasets show that our proposed SEGTB algorithm is both effective and efficient, outperforming the state-of-the-art.

关键词： Skeleton Clustering algorithms Heuristic algorithms Topology Explosives Social networking (online) Licenses Network dismantling network skeleton acyclic graph greedy tree breaking approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Bilevel Optimization to Design Control Plane for SDONs in Consideration of Planned Physical-Layer Attacks

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2021年第3期18卷 3221-3230页

作者： Lv, Qian Zhou, Fen Zhu, Zuqing Univ Sci & Technol China Sch Informat Sci & Technol Hefei 230027 Peoples R China Univ Lille Ctr Digital Syst Inst Mines Telecom IMT Lille Douai F-59000 Lille France

In the network planning of software-defined optical networks (SDONs), the control plane design is of great importance because it directly affects the performance and reliability of network control and management (NC&M). In this article, we consider the planned physical-layer attacks from a rational attacker, which can analyze the control plane of an SDON and target its attacks to the most vulnerable part. To address such attacks, we model the control plane design as a bilevel optimization, where the upper-level optimization is for the network planner to design the control plane whose vulnerability to planned attacks is minimized, while the lower-level optimization is for the attacker to plan its attacks such that the control plane can be disturbed as severely as possible. We first develop two approaches to solve the bilevel model exactly. Specifically, we first leverage the cutting plane method to solve it directly, and then transform it into a single-level mixed integer linear programming (MILP) model with the Bellman method for problem solving. To improve the time efficiency for large-scale problems, we also propose a polynomial-time approximation algorithm based on linear programming (LP) relaxation and randomized rounding. Extensive simulations with various physical topologies verify the effectiveness of our proposals.

关键词： Optimization Optical fiber networks Optical switches Topology Control systems approximation algorithms Proposals Software-defined optical networks (SDONs) control plane resilience physical-layer attacks planned attacks bilevel optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Online algorithms for BP functions maximization

引用

THEORETICAL COMPUTER SCIENCE 2021年 858卷 114-121页

作者： Liu, Zhicheng Chen, Ling Chang, Hong Du, Donglei Zhang, Xiaoyan Nanjing Normal Univ Coll Taizhou Taizhou 225300 Peoples R China Nanjing Normal Univ Sch Math Sci Nanjing 210023 Peoples R China Nanjing Normal Univ Inst Math Nanjing 210023 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada

BP maximization problem has many applications in machine learning and data science. It can be described as maximizing the sum of a suBmodular function and a suPermodular function (BP) under some constraints, where both functions are nonnegative and monotonic. In this paper, we consider two online cases. The first is a BP maximization problem subject to a uniform matroid constraint when the items arrive one-by-one, for which we offer an online algorithm with constant competitive ratio. The second is a BP maximization problem subject to a partition matroid constraint where each part of the partition arrives in a random order, for which we present two approximation algorithms of both constant competitive ratios, where one is randomized and the other is deterministic. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Online BP maximization partition matroid Submodular term Supermodular term Competitive ratio approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Job release scheduling problem: Complexity and an approximation algorithm

引用

DISCRETE APPLIED MATHEMATICS 2013年第6期161卷 858-863页

作者： Choi, Byung-Cheon Chung, Jibok Chungnam Natl Univ Dept Business Adm Taejon 305704 South Korea Daejeon Univ Dept Business Adm Taejon 300716 South Korea

We consider the problem of releasing multiple types of jobs to a facility over a fixed period. In the problem, each type of job has its own demand for the period and the daily capacity of the facility can fluctuate. The variability of each type is defined as the total absolute deviation between the number of jobs of the corresponding type released on consecutive days. The objective is to minimize the total variability over all types. We show that the problem is strongly NP-hard. In addition, we develop an approximation algorithm and analyze its approximability according to the level of fluctuation of the daily capacity. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Scheduling Variability Computational complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable

引用

OPERATIONS RESEARCH LETTERS 2021年第2期49卷 270-277页

作者： Afanasev, Vsevolod A. van Bevern, Rene Tsidulko, Oxana Yu. Novosibirsk State Univ Dept Mech & Math Ul Pirogova 1 Novosibirsk 630090 Russia Russian Acad Sci Sobolev Inst Math Siberian Branch Novosibirsk Russia

The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem. (C) 2021 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Fixed-parameter algorithm NP-hardness Arc routing Rural Postman Problem Temporal graphs

来源：评论

学校读者我要写书评

暂无评论

Minimum constellation covers: hardness, approximability and polynomial cases

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第3期41卷 603-624页

作者： Ravelo, Santiago Valdes Univ Fed Rio Grande do Sul Inst Informat Porto Alegre RS Brazil

This paper considers two graph covering problems, theMinimum Constellation Cover (CC) and theMinimum k-Split Constellation Cover (k- SCC). The input of these problems consists on a graph G = ( V, E) and a set C of stars of G, and the output is a minimum cardinality set of stars C, such that any two different stars of C are edgedisjoint and the union of the stars of C covers all edges of G. For CC, the set C must be compound by edges of G or stars of C while, for k- SCC, an integer k is given and the elements of C must be k-stars obtained by splitting stars of C. This work proves that unless P = NP, CC does not admit polynomial time |C|(O(1))-approximation algorithms and k- SCC cannot be ((1 - epsilon) ln |E|)-approximated in polynomial time, for any epsilon > 0. Additionally, approximation ratios are given for the worst feasible solutions of the problems and, for k- SCC, polynomial time approximation algorithms are proposed, achieving a (ln | E| - ln ln |E| + Theta (1)) approximation ratio. Also, polynomial time algorithms are presented for special classes of graphs that include bounded degree trees and cacti.

关键词： Exact graph cover NP-hard Inapproximability approximation algorithm Polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Shifting Opinions in a Social Network Through Leader Selection

引用

IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS 2021年第3期8卷 1116-1127页

作者： Yi, Yuhao Castiglia, Timothy Patterson, Stacy Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA

We study the French-DeGroot opinion dynamics in a social network with two polarizing parties. We consider a network in which the leaders of one party are given, and we pose the problem of selecting the leader set of the opposing party so as to shift the average opinion to a desired value. When each party has only one leader, we express the average opinion in terms of the transition matrix and the stationary distribution of random walks in the network. The analysis shows the balance of influence between the two leader nodes. We show that the problem of selecting at most k absolute leaders to shift the average opinion is NP-hard. Then, we reduce the problem to a problem of submodular maximization with a submodular knapsack constraint and an additional cardinality constraint, and propose a greedy algorithm with upper bound search to approximate the optimum solution. We also conduct experiments in random networks and real-world networks to show the effectiveness of the algorithm.

关键词： approximation algorithm balance of opinions French-DeGroot model optimization social network

来源：评论

学校读者我要写书评

暂无评论

Optimizing flight trajectory of UAV for efficient data collection in wireless sensor networks

引用

THEORETICAL COMPUTER SCIENCE 2021年 853卷 25-42页

作者： Luo, Chuanwen Chen, Wenping Li, Deying Wang, Yongcai Du, Hongwei Wu, Lidong Wu, Weili Renmin Univ China Sch Informat Beijing 100872 Peoples R China Harbin Inst Technol Dept Comp Sci & Technol Shenzhen 518055 Peoples R China Univ Texas Tyler Dept Comp Sci Tyler TX 75799 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

Unmanned Aerial Vehicles (UAVs) are expected to be important components in the upcoming wireless communication field, which are increasingly used as data collectors to gather sensory data from Wireless Sensor Networks (WSNs) due to their high mobility, flexible deployment. Since the storage capacity and lifetime of sensors are increasing with the development of science and technology, sensors can store more and more sensing data about the monitoring area. However, due to the energy limitation of UAVs and a large amount of data carried by sensors, we can not collect all data from WSN within the limited time. Therefore, in this paper, we investigate two problems: (1) without the energy limitation of UAV, how to optimize the trajectory of UAV to minimize the sum of traveling time and data transmission time of UAV while guaranteeing the amount of data collected from each sensor reaches to a certain proportion of the original data, which is called the Minimizing Transportation and Communication Latency (MTCL) problem;(2) given the limited budget of UAV, how to find the optimal trajectory of UAV to maximize the minimum ratio of the collected data to the stored data among all sensors, which is called the Maximizing Data Collection Proportion (MDCP) problem. We first prove that both the problems are NP-Complete. Then we study a special case of the MTCL problem, which is called the MTCL-disjoint problem, in which any pair of data collection areas are disjoint, and we propose an approximation algorithm to solve the MTCL-disjoint problem. Based on the MTCL-disjoint problem, we propose an approximation algorithm for the general MTCL problem. Afterward, an approximation algorithm for the MDCP problem is proposed on the basis of the algorithm for the MTCL problem. Finally, we present numerical results in different scenarios to assess the effectiveness of the proposed algorithms. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Wireless sensor network Mobile data collection Unmanned aerial vehicle approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Relay Node Placement in Wireless Sensor Networks: From Theory to Practice

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2021年第4期20卷 1602-1613页

作者： Liang, Wei Ma, Chaofan Zheng, Meng Luo, Longxiang Chinese Acad Sci Shenyang Inst Automat State Key Lab Robot Shenyang 110016 Peoples R China Chinese Acad Sci Shenyang Inst Automat Key Lab Networked Control Syst Shenyang 110016 Peoples R China Chinese Acad Sci Inst Robot & Intelligent Mfg Shenyang 110016 Peoples R China Zhongyuan Univ Technol Software Coll Zhengzhou 450007 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China

The increasingly wide utilization of Wireless Sensor Networks (WSNs) in industrial applications outstands the significance of the Delay Constrained Relay Node Placement (DCRNP) problem. Existing algorithms to the DCRNP problem are designed based on the ideal geometric disk wireless channel model, and no real-world deployments are performed to verify the effectiveness of these algorithms. However, the unreliable and unpredictable wireless links in WSNs may lead these algorithms to fail in practice. Therefore, we first conduct extensive real-world deployments under the guidance of existing algorithms to evaluate their performance and to gain some insights for designing practical deployment algorithms. The results exhibit that the WSNs built by existing algorithms have a favorable performance in end-to-end delay but a poor performance in reliability, which is mainly due to the lack of methods ensuring high-quality links. To this end, we first devise a Set-Covering-based algorithm (SCA) which figures out the DCRNP problem while ensuring the quality of each link better than a given threshold. As our experiments also show that the fault-tolerant topology can significantly improve network reliability, we then design a k-Set-Covering-based algorithm (kSCA) to build fault-tolerant WSNs based on the methodology of SCA. Furthermore, the elaborate analysis proves that both SCA and kSCA are polynomial-time algorithms, and their approximation ratios are both O(ln n), where n is the number of sensor nodes. Finally, extensive experiments are performed under the guidance of SCA and kSCA to demonstrate the effectiveness of these two algorithms.

关键词： Wireless sensor networks approximation algorithms Delays Relays Wireless communication Reliability Topology Wireless sensor network relay node placement approximation algorithm set cover delay

来源：评论

学校读者我要写书评

暂无评论

A spectral partitioning algorithm for maximum directed cut problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第3期42卷 373-395页

作者： Zhang, Zhenning Du, Donglei Wu, Chenchen Xu, Dachuan Zhang, Dongmei Beijing Univ Technol Coll Appl Sci Beijing 100124 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 5A3 Canada Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

We investigate the maximum directed cut (MaxDC) problem by designing a spectral partitioning algorithm. Given a directed graph with nonnegative arc weights, we wish to obtain a bipartition of the vertices such that the total weight of the directed cut arcs is maximized. Relaxing the MaxDC problem as a quadratic program allows us to explore combinatorial properties of the optimal solution, leading to a 0.272-approximation algorithm via the technique of spectral partitioning rounding.

关键词： Maximum directed cut Spectral graph theory Spectral partitioning rounding approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：