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

Fair-Energy Trajectory Planning for Multi-Target Positioning Based on Cooperative Unmanned Aerial Vehicles

IEEE ACCESS 2020年 8卷 9782-9795页

作者： Ji, Yao Dong, Chao Zhu, Xiaojun Wu, Qihui Nanjing Univ Aeronaut & Astronaut Coll Elect & Informat Engn Minist Ind & Informat Technol Key Lab Dynam Cognit Syst Electromagnet Spectrum Nanjing 210016 Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 210016 Peoples R China

Owing to the flexibility and low cost, cooperative Unmanned Aerial Vehicles(UAVs) have been attractive in multi-target positioning recently. Although it is popular and easy to accomplish, positioning based on trilateration method still faces challenges under scenarios with multiple UAVs. First, large accumulated errors will be brought if a single UAV is used to perform trilateration on same targets. Second, due to the mobility of targets, the time interval between UAVs performing twice successive distance measurement on one target cannot be long for positioning precision. Finally, the limited energy provided by onboard battery limits the time for UAVs to perform tasks. Once the energy used by some of the UAVs reaches limitation, the whole positioning mission will fail. Thus, to complete the mission of locating multiple targets, this paper is intended to minimize the maximum energy consumption among all UAVs. We formulate the problem, and decompose it into two subproblems, one of which plans the routes for UAV groups and the other plans the routes for UAVs in a group. To solve the first subproblem, a heuristic algorithm called adjusted genetic algorithm (AGA) is proposed to plan trajectories for all UAV groups under constraints on maximum energy consumption. To guarantee stable performance and reduce computation complexity, we propose an approximation algorithm, Tree Decomposition united with Christofides algorithm (TDCA), and the approximation ratio is proved to be (3 * N '/(2*(N ' 1))), where N ' denotes the number of UAV groups. For the second subproblem, a two-step greedy heuristic algorithm is proposed to plan trajectories for UAVs in same groups. Extensive simulations show that compared to existing algorithms, the proposed algorithms can reduce up to 26.6% maximum and 26.3% average energy consumption.

关键词： Trajectory planning energy consumption cooperative UAVs approximation algorithm tree decomposition Christofides algorithm

来源：评论

学校读者我要写书评

暂无评论

Vector scheduling with rejection on two machines

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2020年第12期97卷 2507-2515页

作者： Dai, Bingfei Li, Weidong Yunnan Univ Sch Math & Stat Kunming 650504 Yunnan Peoples R China

In this paper, we study the problem of vector scheduling with rejection on two identical parallel machines, where the objective is to minimize the sum of maximum load over all dimensions and machines and the total penalty cost. We present a 3-approximation algorithm and a 2.54-approximation algorithm based randomized rounding for the general case. When the number of dimensions is fixed, we design a fully polynomial time approximation scheme based on dynamic programming. Finally, we design an online algorithm with competitive ratio 1.62d, where d is the number of dimensions.

关键词： Vector scheduling rejection approximation algorithm online algorithm

来源：评论

学校读者我要写书评

暂无评论

Robust network function virtualization

引用

NETWORKS 2020年第4期75卷 438-462页

作者： Lin, Tachun Zhou, Zhili Bradley Univ Dept Comp Sci & Informat Syst Peoria IL 61625 USA Grubhub Chicago IL USA

Network function virtualization (NFV) enables on-demand network function (NF) deployment providing agile and dynamic network services. Through an evaluation metric that quantifies the minimal reliability among all NFs for all demands, service providers and operators may better facilitate flexible NF service recovery and migration, thus offering higher service reliability. In this paper, we present evaluation metrics on NFV reliability and solution approaches to solve robust NFV under random NF-enabled node failure(s). We demonstrate how to construct an auxiliary NF-enabled network and its mapping onto the physical substrate network. With the constructed NF-enabled network, we develop pseudo-polynomial algorithms to solve the robust NF and SFC s - t path problems: subproblems of robust NFV. We also present approximation algorithms for robust NFV with the SFC-Fork as the NF forwarding graph. Furthermore, we propose exact solution approaches via mixed-integer linear programming under the general setting. Computational results show that our proposed solution approaches are capable of managing robust NFV in a large-size network.

关键词： approximation algorithm cross-layer network network function virtualization quality-of-service robustness of network function service service function chaining

来源：评论

学校读者我要写书评

暂无评论

Analysis of multiobjective evolutionary algorithms on the biobjective traveling salesman problem (1,2)

引用

MULTIMEDIA TOOLS AND APPLICATIONS 2020年第41-42期79卷 30839-30860页

作者： Lai, Xinsheng Zhou, Yuren Shaoxing Univ Sch Comp Sci & Engn Shaoxing 312000 Zhejiang Peoples R China Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou 510006 Peoples R China

Multiobjective evolutionary algorithms have been successfully used to deal with multiobjective combinatorial optimization problems for more than two decades. However, we know little about the performance of multiobjective evolutionary algorithms on multiobjective combinatorial optimization problems in theory so far, especially on NP-hard ones from real-world, since Pareto curves are often of exponential size, meanwhile, evolutionary algorithms rely heavily on the use of randomness and are hard to understand from a theoretical point of view. In this paper, we theoretically investigate the performance of two simple multiobjective evolutionary algorithms with different population diversity mechanisms on the biobjective traveling salesman problem (1,2). It is found that one of them can efficiently find a 3/2-approximation Pareto curve for the problem, the best result so far. At the same time, these two multiobjective evolutionary algorithms are proved to be superior to a multiobjective local search algorithm, and the multiobjective local search algorithm is also proven to outperform these two multiobjective evolutionary algorithms as well. Finally, the population diversity is proved to be helpful in reducing the expected runtime of multiobjective evolutionary algorithm.

关键词： Multiobjective evolutionary algorithm Multiobjective traveling salesman problem approximation algorithm Population diversity Combinatorial optimization problem

来源：评论

学校读者我要写书评

暂无评论

On Virtual Network Reconfiguration in Hybrid Optical/Electrical Datacenter Networks

引用

JOURNAL OF LIGHTWAVE TECHNOLOGY 2020年第23期38卷 6424-6436页

作者： Zhao, Sicheng Zhu, Zuqing Univ Sci & Technol China Sch Informat Sci & Technol Hefei 230027 Peoples R China

Hybrid optical/electrical datacenter networks (HOE-DCNs) build inter-rack networks with both electrical Ethernet switches and optical cross-connects (OXCs), and have been considered as a promising DCN architecture. However, to adapt to the dynamic network environment, the reconfiguration of virtual networks (VNTs) in an HOE-DCN still faces the unique difficulty that theHOE-DCN's topology can change because of the one-to-one connectivity of OXCs. To the best of our knowledge, this problem still has not been fully explored. In this article, we address this problem, and consider how to achieve effective VNT reconfiguration in an HOE-DCN such that the IT resource usages in racks can be re-balanced with the migration of virtual machines (VMs). We first formulate a mixed integer linear programming (MILP) to describe the VNT reconfiguration. Then, we solve the problem with two steps, 1) obtaining the VM migration schemes to balance the loads on racks and 2) determining the reconfiguration schemes of related virtual links (VLs) and the OXC. For the first step, we propose a polynomial-time approximation algorithm by leveraging linear relaxation. Then, we tackle the optimization of the second step by developing an algorithm that involves a linear-time dynamic programming and an integer linear programming (ILP). To solve the ILP time-efficiently, we propose another polynomial-time approximation algorithm based on Lagrangian relaxation. Our simulations confirm the effectiveness of the proposed approximation algorithms and verify that the overall procedure including them outperforms the existing approach.

关键词： approximation algorithm hybrid optical/electrical datacenter network (HOE-DCN) network virtualization virtual network reconfiguration virtual machines (VMs) migration

来源：评论

学校读者我要写书评

暂无评论

Liar's dominating set problem on unit disk graphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 286卷 91-99页

作者： Jallu, Ramesh K. Das, Gautam K. Indian Inst Technol Dept Math Gauhati India

In this paper, we consider Euclidean versions of the 2-tuple dominating set problem and the liar's dominating set problem. For a given set P = {p(1), p(2), ..., p(n)} of n points in R-2, the objective of the Euclidean 2-tuple dominating set problem is to find a minimum size set D subset of P such that IN[p(i)] boolean AND D vertical bar >= 2 for each p(i) is an element of P, where N[p(i)] = {p(j) is an element of P vertical bar delta(p(i), p(j)) <= 1} and delta(p(i), p(j)) is the Euclidean distance between p(i) and p(j). The objective of the Euclidean liar's dominating set problem is to find a set D(subset of P) of minimum size satisfying the following two conditions: (i) D is a 2-tuple dominating set of P, and (ii) for every distinct pair of points p(i) and p(j) in P, vertical bar(N[P-i] boolean OR N[p(j)]) boolean AND D vertical bar >= 3. We first propose a simple O(n log n) time 63/2-factor approximation algorithm for the Euclidean liar's dominating set problem. Next, we propose approximation algorithms to improve the approximation factor to 732/alpha for 3 <= alpha <= 183, and 846/alpha for 3 <= alpha <= 282. The running time of both the algorithms is 0(n(alpha+1) Delta), where Delta = max{vertical bar N[p]vertical bar : p is an element of P}. Finally, we propose a PTAS for the Euclidean 2-tuple dominating set problem. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Unit disk graph approximation algorithm Dominating set Liar's dominating set

来源：评论

学校读者我要写书评

暂无评论

New LP relaxations for Minimum Cycle/Path/Tree Cover Problems

引用

THEORETICAL COMPUTER SCIENCE 2020年 803卷 71-81页

作者： Yu, Wei Liu, Zhaohui Bao, Xiaoguang East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Shanghai Ocean Univ Coll Informat Technol Shanghai 201306 Peoples R China

Given an undirected complete graph G = (V, E) with nonnegative edge weight function obeying. the triangle inequality, a set (C-1, C-2, C-k} of cycles is called a cycle cover if V subset of boolean OR(k)(i=1) V(C-i), where V(C-i) represents the set of vertices in C-i, and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem (MCCP) aims to find a cycle cover of cost at most lambda with the minimum number of cycles. We propose new LP relaxations for MCCP as well as its variants, called the Minimum Path Cover Problem (MPCP) and the Minimum Tree Cover Problem, where the cycles are replaced by paths or trees. Moreover, we give new LP relaxations for a special case of the rooted version of MCCP/MPCP. We show that these LP relaxations have significantly better integrality gaps than the previous relaxations. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Vehicle routing Cycle cover Path cover approximation algorithm Integrality gap

来源：评论

学校读者我要写书评

暂无评论

Longest Increasing Subsequence under Persistent Comparison Errors

引用

THEORY OF COMPUTING SYSTEMS 2020年第4期64卷 662-680页

作者： Geissmann, Barbara Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

We study the problem of computing a longest increasing subsequence in a sequence S of n distinct elements in the presence of persistent comparison errors. In this model, Braverman and Mossel (Noisy sorting without resampling, SODA 2008, pages 268-276, 2008) every comparison between two elements can return the wrong result with some fixed (small) probability p, and comparisons cannot be repeated. Computing the longest increasing subsequence exactly is impossible in this model, therefore, the objective is to identify a subsequence that (i) is indeed increasing and (ii) has a length that approximates the length of the longest increasing subsequence. We present asymptotically tight upper and lower bounds on both the approximation factor and the running time. In particular, we present an algorithm that computes an O(log n)-approximation in O(n log n) time, with high probability. This approximation relies on the fact that we can approximately sort (Geissmann et al. Optimal Sorting with Persistent Comparison Errors, ArXiv e-prints 1804.07575, 2018) n elements in O(n log n) time such that the maximum dislocation of an element is O(logn). For the lower bounds, we prove that (i) there is a set of sequences, such that on a sequence picked randomly from this set every algorithm must return an Omega(log n)}-approximation with high probability, and (ii) any logn-approximation algorithm for longest increasing subsequence requires Omega(n log n) comparisons, even in the absence of errors.

关键词： Longest increasing subsequence Probabilistic persistent comparison errors approximation algorithm Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Profit Maximization problem with Coupons in social networks

引用

THEORETICAL COMPUTER SCIENCE 2020年 803卷 22-35页

作者： Liu, Bin Li, Xiao Wang, Huijuan Fang, Qizhi Dong, Junyu Wu, Weili Ocean Univ China Sch Math Sci Qingdao Peoples R China Qingdao Univ Sch Math & Stat Qingdao Peoples R China Ocean Univ China Coll Informat Sci & Engn Qingdao Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA

Viral marketing has become one of the most effective marketing strategies. In the process of real commercialization, in order to let some seed individuals know the products, companies can provide free samples to them. However, for some companies, especially famous ones, they are more willing to offer coupons than give samples. In this paper, we consider the Profit Maximization problem with Coupons (PM-C) in our new diffusion model named the Independent Cascade Model with Coupons and Valuations (IC-CV). To solve this problem, we propose the PMCA algorithm which can return a (1/3-epsilon)-approximate solution with at least 1 - 2n(-l) probability, and runs in O(log(np) . mn(3) logn(l logn n log2)/epsilon(3)) expected time. Furthermore, during the analysis we provide a method to estimate the non-monotone submodular function. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Profit Maximization Social network approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A random algorithm for profit maximization in online social networks

引用

THEORETICAL COMPUTER SCIENCE 2020年 803卷 36-47页

作者： Chen, Tiantian Liu, Bin Liu, Wenjing Fang, Qizhi Yuan, Jing Wu, Weili Ocean Univ China Sch Math Sci Qingdao 266100 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

Given a social network G and a positive integer k, the influence maximization problem seeks for k nodes in G that can influence the largest number of nodes. This problem has found important applications, and a large amount of works have been devoted to identifying the few most influential users. But most of existing works only focus on the diffusion of a single idea or product in social networks. However, in reality, one company may produce multiple kinds of products and one user may also have multiple adoptions. For multiple kinds of different products with different activation costs and profits, it is crucial for the company to distribute the limited budget among multiple products in order to achieve profit maximization. The Profit Maximization with Multiple Adoptions (PM(2)A) problem aims to seek for a seed set within the budget to maximize the overall profit. In this paper, a Randomized Modified Greedy (RMG) algorithm based on the Reverse Influence Sampling (RIS) technique is presented for the PM(2)A problem, which could achieve a (1 - 1/e -epsilon)-approximate solution with high probability and is also the best performance ratio of the PM(2)A problem. Comprehensive experiments on three real-world social networks are conducted, and the results demonstrate that our RMG algorithm outperforms the algorithm proposed in [16] and other heuristics in terms of profit maximization, and could better allocate the budget. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Profit maximization approximation algorithm Sampling Social network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：