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

作者： Naib, Sameer University of Manitoba

学位级别：硕士

The classic k-server problem has been studied extensively in the context of competitive analysis for online problems. In this problem, a set of k servers move on a metric space to serve requests that appear in an online fashion on the nodes of the space. The goal is to move servers in a way to minimize the total distance moved by all of them. The Certain News Network (CNN) problem is a variant of the k-server problem where there is only one server `serving' requests on a grid metric space. To serve a request, the server should be vertically or horizontally aligned (not necessarily co-located) with the request. The orthogonal CNN problem is a restricted setting of the CNN problem in which every new request is aligned with the previous request. The best existing lower and upper bounds for the competitive ratios in the orthogonal setting are respectively 3 and 6.464. In this thesis, we tighten the gap between upper and lower bounds for the orthogonal CNN problem by providing better algorithms that achieves a competitive ratio of at most 5. Our algorithm, named Walk-and-Jump (WJ) algorithm, is based on the concept of work function that is studied before for both k-server and CNN problems. We use the concept of work function in designing the Walk-and-Jump algorithm. Moreover, in the worst-case sequences that we studied, the WJ algorithm has a cost that is no more than three times the cost of an optimal offline algorithm. Given this observation, we conjecture that the analysis can be improved to show the WJ algorithm is indeed optimal and has a competitive ratio of 3. Besides this main result, we also consider the advice model for the orthogonal CNN problem. Under this model, the online algorithm receives certain ``advice" about the input sequence that is generated by a benevolent offline oracle. We show that advice of size theta(n) is sufficient and necessary to achieve an optimal solution for the orthogonal CNN problem.

关键词： Online algorithms Potential Function Advice Competitive Ratio CNN Problem Work Fucntion greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Modelling and Simulation Analysis of Drones Allocation for Bushfires

Modelling and Simulation Analysis of Drones Allocation for B...

引用

作者： Junxu Wang Haisong Weng Yuxin Yan Congduan Li School of Electronics and Communication Engineering Sun Yat-sen University

Recent years, bushfire has been more and more frequent because of climate *** the scene of fires, firefighters have used drones for surveillance. In this paper, a model is designed to determine the optimal number of drones needed for a bushfire based on the data from satellites. We design a greedy algorithm to plan the cruise lines with the minimal number of drones, covering the fire region. We divide a region(take Victoria, Australia as an example)into blocks, and analysed each block to get the average number of drones needed. We also model the fire probability distribution and finally determine the total number of drones that should be reserved. The simulation(The simulation code is publicly available via https://***/WRangers/msadab) results and analysis show the model is effective and can adapt to a real-time changing large-scale bushfire situation, adjusting the cruise scheme dynamically. The algorithm is helpful to make a budget on purchasing equipment, and also helps the fire department deploy drones in bushfires.

关键词： Bushfire Drone allocation greedy algorithm Cruise planning

来源：评论

学校读者我要写书评

暂无评论

Research on the method of path planning for slag-removing on the surface of zinc pot

Research on the method of path planning for slag-removing on...

引用

第33届中国控制与决策会议

作者： Kebo LI Ling XIONG Zhenzhou ZHANG Gang CHEN Engineering Research Center for Metallurgical Automation and Measurement Technology of Ministry of Education Institute of Robotics and Intelligent Systems Wuhan University of Science and Technology Key Laboratory of Metallurgical Equipment and Control Technology Wuhan University of Science and Technology

During the production process of cold-rolled hot-dip galvanizing,the slag on the surface of the zinc pot will affect the quality of the *** zinc slag is mostly collected manually or by robots at *** effect of manual salvage is unstable and the operation is *** robot cannot identify the location of the zinc slag and can only salvage it according to a fixed rule,resulting in low *** response to the above problems,a zinc pot slag path planning method based on the greedy algorithm is proposed in this *** zinc pot area is divided,the image processing method is used to identify and locate the zinc slag to be *** the priority of the zinc pot,the obstacle avoidance problem and the restriction of the weight limit of the slag-removing tool are proposed in combination with the process *** three salvage strategies based on the greedy algorithm,the shortest distance,the maximum weight,and the minimum weight are proposed *** results show that the greedy algorithm strategy based on the shortest distance performs best,consumes the least energy,and the algorithm runs for a shorter *** can significantly improve the efficiency of zinc pot slag removal,realize intelligent control of slag removal technology,and can be applied to the actual production of zinc pot slag removal.

关键词： Slag from zinc pot Intelligent control greedy algorithm Path planning Shortest distance strategy

来源：评论

学校读者我要写书评

暂无评论

A Novel Public Health Intervention Strategy for the Control of Infectious Disease Outbreaks Among Dynamic Metapopulation Networks 20

A Novel Public Health Intervention Strategy for the Control ...

引用

2020 5th International Conference on Biomedical Imaging, Signal Processing

作者： Stephanie Wang Seven Lakes High School USA

ISBN: (纸本)9781450388269

Abstract. With the onset of various pandemics in the past few centuries, and most recently the COVID-19 pandemic, the importance of properly allocating resources to at-risk populations is increasing. In seasonal and commonly mutating strains of infectious diseases, public health officials aim to promote vaccination among at-risk communities to uphold the herd immunity phenomenon. However, there is often a lack of vaccine availability to provide to the majority of the population. The efficiency of current vaccination strategies utilized by public health officials in the face of limited resources has not been a topic of thorough study and can thus be improved in the parameters of percentage of people saved versus resources expended. In this study, a combination of contact network epidemiology and a mass action compartmental model were used to devise a simulated environment with a theoretical outbreak. Data from the Songliao Basin in China was compiled to emulate a bustling urban environment where outbreaks have the greatest capacity to propagate. Then, an evaluation of the effectiveness of a novel vaccination strategy based on the greedy algorithm in comparison to commonly used strategies for outbreak control is produced.

关键词： herd immunity network optimization Epidemiology public health greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

greedy Multi-cloud Selection Approach to Deploy an Application Based on Microservices 27

Greedy Multi-cloud Selection Approach to Deploy an Applicati...

引用

27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP)

作者： Carvalho, Juliana Vieira, Dario Trinta, Fernando Fed Univ Piaui UFPI Picos Brazil EFREI PARIS Paris France Fed Uniers Ceara UFC Fortaleza Ceara Brazil

ISBN: (纸本)9781728116440

The multi-cloud delivery model allows the deployment of a distributed application in a manner in which the software architect chooses the services that better meet the application and the software architect's requirements. However, choosing cloud services is a complex task for a software architect, as there are several cloud providers that offer many services, which makes the selection process from the user perspective a relevant research problem. Therefore, in this paper, we propose a multiple providers selection approach to host a distributed application based on microservices to facilitate the software architect's decision-making. Our approach differs from others because each microservice is deployed in a single provider that better meets requirements from the software architect's perspective. Hence, our approach selects various services of a single provider for a microservice, and a distinct provider for each microservice, which makes this a complex task. We also use multi-criteria decision-making to rank the cloud services, and we map the selection process to multi-choice knapsack problem, which we develop using a greedy algorithm. Furthermore, we implement a tool to evaluate our approach performance, and the results show our approach feasibility, varying the number of cloud providers and services, microservices and requirements.

关键词： multi-cloud selection microservices multi-requirements multi-choice knapsack problem greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Rationalization of Production Order Execution with Use of the greedy and Tabu Search algorithms 13th

Rationalization of Production Order Execution with Use of th...

引用

Int Joint Conf of the 13th Int Conf on Soft Comp Models in Ind and Environm Applicat (SOCO) / 11th Int Conf on Computat Intelligence in Secur for Informat Syst (CISIS) / 9th Int Conf on European Transnat Educ (ICEUTE)

作者： Musial, Kamil Kochanska, Joanna Burduk, Anna Wroclaw Univ Sci & Technol Fac Mech Engn Wybrzeze Wyspianskiego 27 PL-50370 Wroclaw Poland

ISBN: (纸本)9783319941202;9783319941196

In the paper, rationalization of production order execution in a large manufacturing company is suggested. Till now, the decision-making process was based on the human factor, which resulted in irregular utilization of manufacturing resources. The presented work was aimed at developing new order selection system. That would make it possible to utilize the admitted resources possibly best and thus to meet the deadlines and to adapt to specific production requirements. In the work, the greedy and Tabu Search algorithms were used. As a basis for the research employing, historical data were accepted. Each order were given a priority, production time, profit and penalty for failure. Additionally, the machine failure risk was calculated based on empirical measurements. Simulations of several subsequent working weeks were performed in order to analyse the results obtained thanks to the suggested methods and to compare them with the results presently reached by the company.

关键词： Execution of production orders Decision-making processes greedy algorithm Tabu search Meta-heuristics Intelligent optimisation methods of production systems

来源：评论

学校读者我要写书评

暂无评论

Maximizing power production in path and tree riverine networks

引用

SUSTAINABLE COMPUTING-INFORMATICS & SYSTEMS 2019年第Jun.期22卷 300-310页

作者： Johnson, Matthew P. Rybalov, Levi Zhao, Liang Bald, Samuel Lehman Coll Dept Comp Sci Bronx NY 10468 USA CUNY Grad Ctr PhD Program Comp Sci New York NY 10021 USA

A majority of electricity generation in the US is produced by thermoelectric power plants which require a constant supply of water for cooling. Many of these plants consequently eject large quantities of hot water into an adjacent river, causing thermal pollution, which harms the local ecosystems and aquatic life. Plants commonly lie within interconnected river networks, whence thermal pollution from plants upstream flows to downstream plants, causing less-effective cooling, and decreases in efficiency. Plants are managed individually, and government regulations combating thermal pollution take the form of local river temperature constraints. We propose analyzing this situation regionally, as an optimization problem, where we seek to balance the trade-off between satisfying power demand and obeying temperature limits. Our primary focus is fractional variants of this problem where we can specify the amount of power a plant will generate, up to its maximum capacity. After providing optimal schedules or algorithms for several special cases of this problem, we provide an optimal polynomial-time algorithm for this problem on river topologies taking the form of (a) a path graph and (b) a "merge-only" tree. We also investigate a 0/1 version of the problem (plants are either fully on or off), which is NP-hard already for path graphs. We provide a dynamic programming FPTAS for this case. Finally, we carry out an extensive performance evaluation comparing our fractional optimal algorithms to baseline heuristics in simulation. These experiments are performed both on synthetically generated problem instances and on problem instances constructed using real-world river network data, in particular the power plant network along the Hudson River in New York State. These experiments provide insight as to when naive greedy algorithms diverge from the optimal and on which problem instance parameters optimal performance is more sensitive too. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Thermal pollution Optimal PLANTS Hudson River Thermoelectric Power Plants Power production Water Supply greedy algorithm River networks Government Regulation

来源：评论

学校读者我要写书评

暂无评论

Dynamic Participant Selection for Large-Scale Mobile Crowd Sensing

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2019年第12期18卷 2842-2855页

作者： Li, Hanshang Li, Ting Wang, Weichao Wang, Yu Univ North Carolina Charlotte Coll Comp Informat Charlotte NC 28223 USA

With the rapid increasing of smart phones and the advances of embedded sensing technologies, mobile crowd sensing (MCS) becomes an emerging sensing paradigm for large-scale sensing applications. One of the key challenges of large-scale mobile crowd sensing is how to effectively select the minimum set of participants from the huge user pool to perform the tasks and achieve a certain level of coverage while satisfying some constraints. This becomes more complex when the sensing tasks are dynamic (coming in real time) and heterogeneous (with different temporal and spacial coverage requirements). In this paper, we consider such a dynamic participant selection problem with heterogeneous sensing tasks which aims to minimize the sensing cost while maintaining certain level of probabilistic coverage. Both offline and online algorithms are proposed to solve the challenging problem. Extensive simulations over a real-life mobile dataset confirm the efficiency of the proposed algorithms.

关键词： Sensors Task analysis Smart phones Heuristic algorithms Memory Data models Approximation algorithms Participant selection greedy algorithm caching mobile crowd sensing

来源：评论

学校读者我要写书评

暂无评论

A Latency-Aware Multiple Data Replicas Placement Strategy for Fog Computing

引用

JOURNAL OF SIGNAL PROCESSING SYSTEMS FOR SIGNAL IMAGE AND VIDEO TECHNOLOGY 2019年第10期91卷 1191-1204页

作者： Huang, Tiansheng Lin, Weiwei Li, Yin He, LiGang Peng, ShaoLiang South China Univ Technol Sch Comp Sci & Engn Guangzhou Guangdong Peoples R China Inst Software Applicat Technol Guangzhou Guangdong Peoples R China Chinese Acad Sci Guangzhou 511458 Guangdong Peoples R China Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Hunan Univ Coll Comp Sci & Elect Engn Changsha 410082 Hunan Peoples R China Hunan Univ Natl Supercomp Ctr Changsha Changsha 410082 Hunan Peoples R China Natl Univ Def Technol Sch Comp Sci Changsha 410073 Hunan Peoples R China

With the rapid increase of the number of IoT devices, transmitting big amount of data from these devices to data centers which are far away will cause problems like high latency or network congestions. Fog Computing provides a better solution for Fog-enabled latency sensitive data services to place data on Fog nodes which are closer to the data generators. However, recent studies only focus on the data placement problem of placing one single data replica to the proper Fog node. Under the situation that there are several data consumers whose topology positions are different subscribing the same data, one single data replica cannot meet the latency requirement of all the consumers. Hence, we build a multi-replica data placement model iFogStorM for Fog Computing to formulate the problem of how many data replicas need to be placed on Fog nodes and how to optimize the data placement. Furthermore, we propose a greedy algorithm based data replica placement strategy, MultiCopyStorage, to reduce the overall latency. MultiCopyStorage uses a pruning method to filter the inferior solutions calculates the overall latency and chooses the solution with the minimum overall latency as the final solution. We conducted experiments on iFogSim, a toolkit for modeling and simulation of Fog Computing, evaluated the proposed strategy with the CloudStorage strategy, Closest Node strategy, iFogStor strategy, and two kinds of heuristic strategy, iFogStorZ, and iFogStorG. The experiment result demonstrates that MultiCopyStorage strategy reduces the overall latency by 6% and 10% compared to iFogStor and iFogStorG strategy respectively. Meanwhile, execution time of the MultiCopyStorage is less than the heuristic strategy, iFogStorG and iFogStorZ, which proves that the proposed strategy can support real-time scheduling.

关键词： Data placement Fog computing greedy algorithm Internet of things Multiple data replicas

来源：评论

学校读者我要写书评

暂无评论

Linear Precoded Index Modulation

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2019年第1期67卷 350-363页

作者： Zhang, Hongming Jiang, Chunxiao Yang, Lie-Liang Basar, Ertugrul Hanzo, Lajos Univ Southampton Dept Elect & Comp Sci Southampton SO17 1UT Hants England Tsinghua Univ Dept Elect Engn Beijing 100084 Peoples R China Koc Univ Dept Elect & Elect Engn Commun Res & Innovat Lab CoreLab TR-34450 Istanbul Turkey

Index modulation (IM) is an attractive concept for next generation communication systems. However, as an emerging technique, there are still some challenges need to be tackled in this frontier. In this paper, we consider two aspects of IM, which are diversity and detection complexity. Specifically, we propose a linear precoding assisted index modulation (LPIM) scheme for orthogonal frequency division multiplexing (OFDM) systems. We commence by analyzing the diversity and coding gains of the proposed scheme. Moreover, a detailed codebook design criterion is proposed. Then, our LPIM codebook is designed based on the maximum diversity and coding gain criteria. In contrast to the signaling model of the existing full diversity precoder designed for OFDM, we introduce a modeling method to link the zero-valued IM symbols to the origin of a Lattice for implementing our full diversity precoder designed for OFDM-IM. Both analytical and computer simulation results are provided for characterizing the attainable performance of OFDM-LPIM, demonstrating that it is capable of achieving full diversity as well as an attractive coding gain. However, the maximum-likelihood (ML) detection complexity of OFDM-LPIM is excessive, hence a low-complexity generalized iterative residual check detector (GIRCD) is proposed, which is inspired by the existing sparse recovery algorithms. Finally, computer simulation results are provided for demonstrating that GIRCD can provide a beneficial trade-off between bit error ratio performance and complexity.

关键词： Index modulation OFDM transmit diversity algebraic number theory greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：