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

Trajectory Planning for Reconnaissance Mission Based on Fair-Energy UAVs Cooperation

IEEE ACCESS 2019年 7卷 91120-91133页

作者： Qin, Zhen Dong, Chao Li, Aijiing Dai, Haipeng Wu, Qihui Xu, Ai Army Engn Univ PLA Coll Commun Engn Nanjing 210042 Jiangsu Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Elect & Informat Engn Nanjing 211106 Jiangsu Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Nanjing Univ Posts & Telecommun Minist Educ Key Lab Broadband Wireless Commun & Sensor Networ Nanjing 210003 Jiangsu Peoples R China Army Engn Univ PLA Coll Command & Control Engn Nanjing 210042 Jiangsu Peoples R China

Unmanned aerial vehicles (UAVs) have recently received growing popularity in reconnaissance missions due to their many advantages, such as high mobility, flexible deployment, and low operational costs. In this paper, we investigate how the UAVs should optimally exploit its mobility via trajectory planning to achieve the fairness of energy consumption with communication, hovering, and motion energy consumption in consideration. Most of the current works only consider motion energy consumption;however, communication and hovering energy consumption cannot be ignored. We first formulate this problem as a min-max tour cover problem that has been proved to be NP-hard. Then, a heuristic algorithm is proposed to minimize the maximum energy consumption of the reconnaissance UAVs by planning the trajectories. Next, to guarantee the fairness of energy consumption under scenarios with strict and firm energy requirements, we propose an approximation algorithm that can achieve an approximation ratio of 2.5. Finally, the extensive simulations are conducted under different settings to evaluate the performance of our proposed algorithms. The results show that the algorithms can improve the fairness of energy consumption and reduce the maximum energy consumption compared with other algorithms.

关键词： Unmanned aerial vehicles (UAVs) fair energy consumption trajectory planning heuristic algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Scalable many-to-many building footprint matching

引用

Information Fusion 2025年 124卷

作者： Alexander Naumann Annika Bonerath Jan-Henrik Haunert Institut für Geodäsie und Geoinformation Rheinische Friedrich-Wilhelms-Universität Bonn Meckenheimer Allee 172 Bonn 53115 Germany

The amount of available geospatial data, particularly different data sets describing the same area, grows continuously. Finding entity correspondences between multiple such datasets is a vital prerequisite for data integration, fusion, and quality assessment. In this work, we focus on polygon datasets, more specifically, building footprints. We compute many-to-many matchings between two input datasets to find correspondences between polygons. Existing research explored heuristic solutions, exact optimization approaches, and machine learning strategies. So far, none of these methods scale well to large datasets while providing a precise problem formulation to measure the quality of a computed matching. We present a fast and versatile algorithm based on a constrained optimization model. Given a partitioning of the datasets into connected subsets, it can solve instances of over 5 million polygons per dataset in under 7 min. Our approach is based on the Jaccard index (intersection over union, IoU) as its central quality measure. However, it is flexible and easily adaptable to different metrics proposed in other works.

关键词： Matching Multisource data Hierarchical grouping approximation algorithm Building footprints

来源：评论

学校读者我要写书评

暂无评论

Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第2期37卷 601-619页

作者： Dai, Wenkai Yang, Yongjie Saarland Univ Dept Comp Sci Saarbrucken Germany Saarland Univ Chair Econ Theory Saarbrucken Germany

We study the reoptimization of the Minimum Latency problem (MLP) in metric space with respect to the modifications of adding (resp. removing) a vertex and increasing (resp. decreasing) the cost of an edge e. We provide 7/3-approximation and 3-approximation algorithms for the modifications of adding and removing a vertex, respectively. For the modification of increasing the cost of an edge e, we obtain -approximation algorithms where changes from 2.1286 to 4/3 as e moves from the first edge to the last edge in the given optimal tour of the initial instance. Concerning the case of decreasing the cost of an edge e, if e is an edge of the given optimal tour, we get a 2-approximation algorithm. Moreover, if e is the i-th edge of the given optimal tour and i is a constant, we derive a but prove that an does not exist unless . We also show that the special case where i{1,2} is polynomial-time solvable. If e is not in the given optimal tour, we derive a 2.1286-approximation algorithm, where n is the number of vertices. Finally, we show that if an approximation solution instead of an optimal one is given for the initial instance, the reoptimization of MLP with the vertex deletion operation admits no -approximation algorithm unless MLP itself admits such an algorithm.

关键词： Reoptimization Minimum latency Traveling salesman Complexity approximation algorithm PTAS Metrics

来源：评论

学校读者我要写书评

暂无评论

Energy-Aware Design of Stochastic Applications With Statistical Deadline and Reliability Guarantees

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2019年第8期38卷 1413-1426页

作者： Jiang, Wei Pan, Xiong Jiang, Ke Wen, Liang Dong, Qi Univ Elect Sci & Technol China Sch Informat & Software Engn Chengdu 610054 Sichuan Peoples R China Veoneer Res & Engn Dept S-58330 Linkoping Sweden

Energy efficiency, reliability, and real-time are three key requirements of mission-critical embedded systems. Existing approaches over emphasize the worst case design of real-time embedded systems, which will lead to serious waste of resources. In this paper, we aim at the energy-efficient design of soft real-time and reliable applications on uniprocessor embedded systems. We consider soft real-time tasks with stochastic execution durations regarding certain distributions. Thereby, we provide real-time guarantee with probability consideration. We utilize dynamic voltage and frequency scaling (DVFS) for saving energy, and also take into account the impact of DVFS on reliability. Our objective is to minimize the expected energy consumption of the system subject to statistical reliability and deadline constraints. The design optimization problem is a typical multidimensional multiple-choice knapsack problem, which is NP-hard. We first propose a dynamic programming-based optimal algorithm to solve the problem. To reduce the time complexity, we then develop a (1+beta)-approximation algorithm based on a binary search approach, where beta is the approximating factor. The approximation algorithm can obtain the near-optimal solution with at most (1+beta) times of optimal energy cost under given real-time and reliability constraints and has fully polynomial time complexity. Extensive experiments and a real-life synthetic application are conducted to evaluate the performance of the proposed techniques. Compared with existing approaches, the approximation approach can save much energy with low time overhead while guaranteeing the statistical deadline and reliability constraints.

关键词： approximation algorithm embedded systems energy reliability statistical guarantee stochastic real-time application

来源：评论

学校读者我要写书评

暂无评论

SUBDETERMINANTS AND CONCAVE INTEGER QUADRATIC PROGRAMMING

引用

SIAM JOURNAL ON OPTIMIZATION 2019年第4期29卷 3154-3173页

作者： Del Pia, Alberto Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Univ Wisconsin Wisconsin Inst Discovery Madison WI 53706 USA

We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by Delta the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an epsilon-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by Delta in absolute value. The number of these integer linear programs is polynomial in the dimension n, in Delta, and in 1/epsilon, provided that the number k of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with Delta <= 2 and k fixed. In the totally unimodular case Delta = 1, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in 1/epsilon and is independent of n, provided that k is fixed.

关键词： integer quadratic programming approximation algorithm concave function subdeterminants total unimodularity total bimodularity

来源：评论

学校读者我要写书评

暂无评论

Joint optimization of tasks placement and routing to minimize Coflow Completion Time

引用

JOURNAL OF NETWORK AND COMPUTER APPLICATIONS 2019年第Jun.期135卷 47-61页

作者： Guo, Yingya Wang, Zhiliang Zhang, Han Yin, Xia Shi, Xingang Wu, Jianping Tsinghua Univ Dept Comp Sci & Technol Beijing Peoples R China Tsinghua Univ Inst Network Sci & Cyberspace Beijing Peoples R China Beijing Natl Res Ctr Informat Sci & Technol Beijing Peoples R China Beihang Univ Sch Cyber Space & Technol Beijing Peoples R China

Coflow is defined as the parrellel flows between two successive computation stages of data-parallel jobs. Reducing Coflow Completion Time (CCT) is important to improve the performance of data-parallel applications in geo-distributed datacenter networks. CCT is influenced by two factors: tasks placement and coflow routing. Previous works that optimize only one factor are insufficient in reducing CCT. In this paper, we explore the joint optimization of tasks placement and coflow routing to reduce CCT. We formulate the joint optimization of a single coflow as a Mixed Integer Non-Linear Programming problem, and propose an approximate algorithm PRO with an approximation ratio of (1 + epsilon). Moreover, we propose algorithms to optimize multiple coflows scheduling offline and online. Through extensive experiments, we demonstrate that our proposed algorithms have superior performance in reducing CCT or average CCT compared with other algorithms.

关键词： Data-parallel job Coflow Completion Time Task placement Routing inter-DC WAN approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Streaming algorithm for k-Means with Approximate Coreset

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2019年第1期36卷 10-18页

作者： Li, Min Xu, Dachuan Zhang, Dongmei Zhang, Tong Shandong Normal Univ Sch Math & Stat Jinan 250014 Shandong Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp 100 Pingleyuan Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China Beijing Univ Technol Coll Appl Sci Dept Informat & Operat Res 100 Pingleyuan Beijing 100124 Peoples R China

For computing the k-means clustering of the streaming and distributed big sparse data, we present an algorithm to obtain the sparse coreset for the k-means in polynomial time. This algorithm is mainly based on the explicit form of the center of mass and the approximate k-means. Because of the existence of the approximation, the coreset of the output inevitably has a factor, which can be controlled to be a very small constant.

关键词： k-Means clustering coreset streaming approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithmic aspects of semitotal domination in graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 766卷 46-57页

作者： Henning, Michael A. Pandey, Arti Univ Johannesburg Dept Pure & Appl Math Auckland Pk ZA-2006 Johannesburg South Africa Indian Inst Technol Ropar Dept Math Nangal Rd Rupnagar 140001 Punjab India

For a graph G = (V, E), a set D subset of V is called a semitotal dominating set of G if D is a dominating set of G, and every vertex in D is within distance 2 of another vertex of D. The MINIMUM SEMITOTAL DOMINATION problem is to find a semitotal dominating set of minimum cardinality. Given a graph G and a positive integer k, the SEMITOTAL DOMINATION DECISION problem is to decide whether G has a semitotal dominating set of cardinality at most k. The SEMITOTAL DOMINATION DECISION problem is known to be NP-complete for general graphs. In this paper, we show that the SEMITOTAL DOMINATION DECISION problem remains NP-complete for planar graphs, split graphs and chordal bipartite graphs. We give a polynomial time algorithm to solve the MINIMUM SEMITOTAL DOMINATION problem in interval graphs. We show that the MINIMUM SEMITOTAL DOMINATION problem in a graph with maximum degree A admits an approximation algorithm that achieves the approximation ratio of 2+3ln(Delta+1), showing that the problem is in the class log-APX. We also show that the MINIMUM SEMITOTAL DOMINATION problem cannot be approximated within (1 - epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless NP subset of DTIME (vertical bar V vertical bar(0(log log vertical bar v vertical bar))) Finally, we prove that the MINIMUM SEMITOTAL DOMINATION problem is APX-complete for bipartite graphs with maximum degree 4. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Domination Semitotal domination Bipartite graphs Chordal graphs Interval graphs Graph algorithm NP-complete approximation algorithm APX-complete

来源：评论

学校读者我要写书评

暂无评论

Two-agent scheduling on a single machine with release dates

引用

COMPUTERS & OPERATIONS RESEARCH 2019年 111卷 35-42页

作者： Liu, Peihai Gu, Manzhan Li, Ganggang East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Shanghai Univ Finance & Econ Sch Math Shanghai 200433 Peoples R China Jiangxi Univ Finance & Econ Sch Math Nanchang 330077 Jiangxi Peoples R China

This paper considers a two-agent scheduling problem, in which all jobs belong to two agents A and B, and each job has a release date. The objective is to schedule all jobs non-preemptively on a single machine such that the linear combination of the makespans of the two agents, i.e., C-max(A) + theta C-max(B) (theta >= 1), is minimized. It is known that the problem is NP-hard in the ordinary sense. For this case, we provide an approximation algorithm with worst-case ratio 1 + theta/1+theta+theta(2). We also propose a Fully Polynomial Time approximation Scheme (FPTAS) for the problem under study. Finally, computational experiments are conducted to verify the effectiveness of the approximation algorithm and the FPTAS. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Two-agent scheduling Makespan approximation algorithm FPTAS

来源：评论

学校读者我要写书评

暂无评论

Constrained Submodular Maximization via a Nonsymmetric Technique

引用

MATHEMATICS OF OPERATIONS RESEARCH 2019年第3期44卷 988-1005页

作者： Buchbinder, Niv Feldman, Moran Tel Aviv Univ Stat & Operat Res Dept IL-6997801 Tel Aviv Israel Open Univ Israel Dept Math & Comp Sci IL-43107 Raanana Israel

The study of combinatorial optimization problems with submodular objectives has attracted much attention in recent years. Such problems are important in both theory and practice because their objective functions are very general. Obtaining further improvements for many submodular maximization problems boils down to finding better algorithms for optimizing a relaxation of them known as the multilinear extension. In this work, we present an algorithm for optimizing the multilinear relaxation whose guarantee improves over the guarantee of the best previous algorithm (by Ene and Nguyen). Moreover, our algorithm is based on a new technique that is, arguably, simpler and more natural for the problem at hand. In a nutshell, previous algorithms for this problem rely on symmetry properties that are natural only in the absence of a constraint. Our technique avoids the need to resort to such properties, and thus seems to be a better fit for constrained problems.

关键词： submodular maximization multilinear relaxation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：