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

IEEE Global Communications Conference (GLOBECOM) on Advanced Technology for 5G Plus

作者： Wang, Kai Zhang, Xiao Duan, Lingjie South Cent Univ Nationalities Coll Comp Sci Wuhan Peoples R China Singapore Univ Technol & Design Engn Syst & Design Pillar Singapore Singapore

ISBN: (纸本)9781728182988

Unmanned Aerial Vehicle (UAV) technology is a promising solution for providing high-quality mobile services (e.g., edge computing, fast Internet connection, and local caching) to ground users, where a UAV with limited service coverage travels among multiple geographical user locations (e.g., hotspots) for servicing demands locally. It is necessary for different UAVs to cooperate with each other for servicing many users, and how to determine their cooperative path planning to best meet many users' spatio-temporally distributed demands is an important question. This paper is the first to design and analyze cooperative path-planning algorithms of a UAV swarm for optimally servicing many spatial locations with dynamic user arrivals and waiting deadlines in the time horizon. For each UAV, it needs to decide whether to wait at the current location or chase a newly released demand in another location, under upper coordination with the other UAVs in the swarm. For each TAV's routing problem even without coordinating with the rest UAVs, it follows dynamic programming structure and is difficult to solve directly given many user demands. We manage to simplify and propose an optimal algorithm of fast computation time (only polynomial with respect to both the numbers of user locations and user demands) for returning the UAV's optimal path-planning. When a large number vertical bar K vertical bar of UAVs are coordinating, the dynamic programming simplification becomes intractable. Alternatively, we present an iterative cooperation algorithm with approximation ratio 1 - (1 - 1/vertical bar K vertical bar)(vertical bar K vertical bar) in the worst case, which is proved to obviously outperform the traditional idea of partitioning UAVs to serve different user/location clusters separately. Finally, we conduct simulation experiments to show that our algorithm's average performance is close to the optimum.

关键词： UAV swarm deployment Cooperative path planning Dynamic programming approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

ContiMap: Continuous Heatmap for Large Time Series Data

ContiMap: Continuous Heatmap for Large Time Series Data

引用

IEEE Conference on Visualization in Data Science (VDS)

作者： Vung Pham Ngan Nguyen Dang, Tommy Texas Tech Univ Comp Sci Dept Lubbock TX 79409 USA

ISBN: (纸本)9781728192840

Limited human cognitive load, limited computing resources, and finite display resolutions are the major obstacles for developing interactive visualization systems in large-scale data analysis. Recent technological innovation has significantly improved computing power, such as faster CPUs and GPUs, as well as display resources, including ultra-high-resolution displays and video walls. However, large and complex data is still ahead in the run as we are generating huge amounts of data daily. Our strategy to bridge these gaps is to present the right amount of information through the use of compelling graphics. This paper proposes an approximation algorithm and a web prototype for representing a high-level abstraction of time series based on heatmap designs. Our approach aims to handle a significant amount of time series data arising from various application domains, such as cybersecurity, sensor network, and gene expression analysis.

关键词： Continuous heatmap time-series visualization approximation algorithm multivariate data analysis

来源：评论

学校读者我要写书评

暂无评论

Computing Maximum Matchings in Temporal Graphs 37

Computing Maximum Matchings in Temporal Graphs

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Mertzios, George B. Molter, Hendrik Niedermeier, Rolf Zamaraev, Viktor Zschoche, Philipp Univ Durham Dept Comp Sci Durham England TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany Univ Liverpool Dept Comp Sci Liverpool Merseyside England

ISBN: (纸本)9783959771405

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem MAXIMUM MATCHING, taking into account the dynamic nature of temporal graphs. In our problem, MAXIMUM TEMPORAL MATCHING, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e, t) such that no vertex is matched more than once within any time window of Delta consecutive time slots, where Delta is an element of N is given. The requirement that a vertex cannot be matched twice in any Delta-window models some necessary "recovery" period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for MAXIMUM TEMPORAL MATCHING, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.

关键词： Temporal Graph Link Stream Temporal Line Graph NP-hardness APX-hardness approximation algorithm Fixed-parameter Tractability Independent Set

来源：评论

学校读者我要写书评

暂无评论

Stealthy DGoS Attack: DeGrading of Service under the Watch of Network Tomography 38

Stealthy DGoS Attack: DeGrading of Service under the Watch o...

引用

39th IEEE International Conference on Computer Communications (IEEE INFOCOM)

作者： Chiu, Cho-Chun He, Ting Penn State Univ University Pk PA 16802 USA

ISBN: (纸本)9781728164120

Network tomography is a powerful tool to monitor the internal state of a closed network that cannot be measured directly, with broad applications in the Internet, overlay networks, and all-optical networks. However, existing network tomography solutions all assume that the measurements are trust-worthy, leaving open how effective they are in an adversarial environment with possibly manipulated measurements. To understand the fundamental limit of network tomography in such a setting, we formulate and analyze a novel type of attack that aims at maximally degrading the performance of targeted paths without being localized by network tomography. By analyzing properties of the optimal attack, we formulate novel combinatorial optimizations to design the optimal attack strategy, which are then linked to well-known problems and approximation algorithms. Our evaluations on real topologies demonstrate the large damage of such attacks, signaling the need of new defenses.

关键词： Network tomography Denial of Service attack combinatorial optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

How to Keep an Eye on Small Things

引用

International Journal of Computational Geometry and Applications 2020年第2期30卷 97-120页

作者： Nilsson, Bengt J. Zyliński, Paweł Department of Computer Science Malmö University Malmö SE-205 06 Sweden Institute of Informatics University of Gdańsk Gdańsk 80-308 Poland

We present new results on two types of guarding problems for polygons. For the first problem, we present an optimal linear time algorithm for computing a smallest set of points that guard a given shortest path in a simple polygon having n edges. We also prove that in polygons with holes, there is a constant c > 0 such that no polynomial-time algorithm can solve the problem within an approximation factor of clog n, unless P=NP. For the second problem, we present a (k + h)-FPT algorithm for computing a shortest tour that sees k specified points in a polygon with h holes. We also present a k-FPT approximation algorithm for this problem having approximation factor 2. In addition, we prove that the general problem cannot be polynomially approximated better than by a factor of clog n, for some constant c > 0, unless P =NP. © 2020 World Scientific Publishing Company.

关键词： approximation algorithm FPT-algorithm guarding Visibility

来源：评论

学校读者我要写书评

暂无评论

Partially Adaptive Stochastic Optimization for Electric Power Generation Expansion Planning

引用

INFORMS JOURNAL ON COMPUTING 2018年第2期30卷 388-401页

作者： Zou, Jikai Ahmed, Shabbir Sun, Xu Andy Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

Electric power generation expansion planning (GEP) is the problem of determining an optimal construction and generation plan of both new and existing electric power plants to meet future electricity demand. We consider a stochastic optimization approach for this capacity expansion problem under demand and fuel price uncertainty. In a two-stage stochastic optimization model for GEP, the capacity expansion plan for the entire planning horizon is decided prior to the uncertainty realized and hence allows no adaptivity to uncertainty evolution over time. In comparison, a multistage stochastic optimization model allows full adaptivity to the uncertainty evolution but is extremely difficult to solve. To reconcile the trade-off between adaptivity and tractability, we propose a partially adaptive stochastic mixed integer optimization model in which the capacity expansion plan is fully adaptive to the uncertainty evolution up to a certain period and follows the two-stage approach thereafter. Any solution to the partially adaptive model is feasible to the multistage model, and we provide analytical bounds on the quality of such a solution. We propose an efficient algorithm that solves a sequence of partially adaptive models, to recursively construct an approximate solution to the multistage problem. We identify sufficient conditions under which this algorithm recovers an optimal solution to the multistage problem. Finally, we conduct extensive test of our algorithm on a realistic GEP problem. Experiments show that, within a reasonable computation time limit, the proposed algorithm produces a significantly better solution than solving the multistage model directly.

关键词： generation expansion planning multistage stochastic optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Application Deployment in Mobile Edge Computing Environment 13

Optimal Application Deployment in Mobile Edge Computing Envi...

引用

IEEE 13th International Conference on Cloud Computing (CLOUD)

作者： Chen, Feifei Zhou, Jingwen Xia, Xiaoyu Jin, Hai He, Qiang Deakin Univ Sch Informat Technol Geelong Vic Australia Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan Peoples R China Swinburne Univ Technol Sch Software & Elect Engn Hawthorn Vic Australia Chengdu Univ Informat Technol Sch Comp Sci Chengdu Peoples R China

ISBN: (纸本)9781728187808

Mobile edge computing has emerged as a new distributed computing paradigm that overcomes the limitations of traditional cloud computing. In an edge computing environment, an app vendor can hire computing and storage resources on edge servers for deploying their applications to deliver lower-latency services to their app users. Under a budget constraint, an optimal edge application deployment strategy allows an app vendor to deploy application instances on edge servers in a specific area and provide services to the most app users in the area. In this paper, we make the first attempt to tackle this edge application deployment (EAD) problem. Specifically, we formulate the EAD problem as a constrained optimization problem and prove its NP-hardness. Then, we propose an optimal approach named EAD-opt to find the optimal solution of EAD based on integer programming, and an approximation approach named EAD-apx to find approximate solutions in large-scale EAD scenarios efficiently. We evaluate our approaches by conducting experiments on a widely used real-world data set and a synthetic data set with comparison against two baseline approaches. The experimental results demonstrate that our approaches can solve the EAD problem effectively and efficiently.

关键词： Edge computing application deployment low-latency services optimization integer programming approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Placing Wireless Chargers with Limited Mobility 38

Placing Wireless Chargers with Limited Mobility

引用

39th IEEE International Conference on Computer Communications (IEEE INFOCOM)

作者： Dai, Haipeng Wu, Chaofeng Wang, Xiaoyu Dou, Wanchun Liu, Yunhuai Nanjing Univ State Key Lab Novel Software Technol Nanjing 210024 Jiangsu Peoples R China Peking Univ Beijing 10080 Peoples R China

ISBN: (纸本)9781728164120

This paper studies the problem of Placing directional wIreless chargers with Limited mObiliTy (PILOT), that is, given a budget of mobile directional wireless chargers and a set of static rechargeable devices on a 2D plane, determine deployment positions, stop positions and orientations, and portions of time for all chargers such that overall charging utility of all devices can be maximized. To the best of our knowledge, we are the first to study placement of mobile chargers. To address PILOT, we propose a (1/2 - epsilon)-approximation algorithm. First, we present a method to approximate nonlinear charging power of chargers, and further propose an approach to construct Maximal Covered Set uniform subareas to reduce the infinite continuous search space for stop positions and orientations to a finite discrete one. Second, we present geometrical techniques to further reduce the infinite solution space for candidate deployment positions to a finite one without performance loss, and transform PILOT to a mixed integer nonlinear programming problem. Finally, we propose a linear programming based greedy algorithm to address it. Simulation and experimental results show that our algorithm outperforms five comparison algorithms by 31.33% similar to 281.10%.

关键词： Placement directional charging limited mobility wireless power transfer approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Constant Factor approximations to Edit Distance on Far Input Pairs in Nearly Linear Time 2020

Constant Factor Approximations to Edit Distance on Far Input...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Koucky, Michal Saks, Michael Charles Univ Prague Comp Sci Inst Prague Czech Republic Rutgers State Univ Dept Math Piscataway NJ USA

ISBN: (纸本)9781450369794

For any T >= 1, there are constants R = R(T) > 1 and zeta = zeta((T) > 0 and a randomized algorithm that takes as input an integer n and two strings x, y of length at most n, and runs in time O(n(1+1/T)) and outputs an upper bound U on the edit distance of d(edit)(x, y) that with high probability, satisfies U <= R(d(edit)(x, y) + n(1-zeta)). particular, on any input with d(edit)(x, y) >= n(1-zeta) the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein (this proceedings).

关键词： edit distance approximation algorithm almost linear-time algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Minimum Satisfiability Problem 6th

On the Minimum Satisfiability Problem

引用

6th International Conference on algorithms and Discrete Applied Mathematics

作者： Arif, Umair Benkoczi, Robert Gaur, Daya Ram Krishnamurti, Ramesh Simon Fraser Univ Sch Comp Sci Burnaby BC Canada Univ Lethbridge Dept Math & Comp Sci Lethbridge AB Canada

ISBN: (纸本)9783030392185;9783030392192

We characterize the optimal solution to the LP relaxation of the standard formulation for the minimum satisfiability problem. Based on the characterization, we give a O(nm(2)) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n(m) is the number of variables (clauses). As a by-product, we obtain a 2(1 - 1/2(k)) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause. We also give a simple linear time 2 approximation algorithm.

关键词： Primal-dual algorithm Minimum satisfiability approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：