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

Load balancing edge server placement method with QoS requirements in wireless metropolitan area networks

IET COMMUNICATIONS 2020年第21期14卷 3907-3916页

作者： Li, Xingcun Zeng, Feng Fang, Guanyun Huang, Yinan Tao, Xunlin Cent South Univ Sch Comp Sci & Engn Changsha 410083 Peoples R China Univ Houston Dept Pharmaceut Hlth Outcomes & Policy Coll Pharm Houston TX 77204 USA Jingdezhen Ceram Inst Grad Sch Jingdezhen 333403 Peoples R China

Mobile edge computing (MEC) is concerned with moving complex tasks from data sources to nearby computing resources, which can reduce computing latency and remote cloud workload. Although there has been significant research in the field of MEC, research on edge server placement in wireless metropolitan area networks (WMANs) is overlooked, and the load balancing problem of edge servers is seldom discussed. From a practical perspective, how to place edge servers efficiently in WMANs while considering load balancing between edge servers is studied. A greedy algorithm is proposed that can balance the workload of edge servers more effectively. However, the performance of the greedy algorithm as the number of servers placed increases is not ideal. Therefore, the authors combine the greedy algorithm with a genetic algorithm (GA) to minimise the number of edge servers while ensuring load balancing between edge servers and quality of service (QoS) requirements for mobile users. Finally, they conduct simulation experiments and compare the proposed algorithms with other algorithms. The improved GA proposed is superior to the greedy algorithm in terms of load balancing and the number of servers. The experimental results demonstrate that the algorithm has excellent performance.

关键词： quality of service mobile computing greedy algorithms genetic algorithms resource allocation cloud computing metropolitan area networks QoS-aware edge server placement method wireless metropolitan area networks mobile edge computing load balancing problem edge servers greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

An Improved greedy Heuristic for the Minimum Positive Influence Dominating Set Problem in Social Networks

引用

algorithmS 2021年第3期14卷 79页

作者： Bouamama, Salim Blum, Christian Ferhat Abbas Univ Setif 1 Dept Comp Sci Mechatron Lab LMETR E1764200 Setif 19000 Algeria Artificial Intelligence Res Inst IIIA CSIC Campus UAB Bellaterra 08193 Spain

This paper presents a performance comparison of greedy heuristics for a recent variant of the dominating set problem known as the minimum positive influence dominating set (MPIDS) problem. This APX-hard combinatorial optimization problem has applications in social networks. Its aim is to identify a small subset of key influential individuals in order to facilitate the spread of positive influence in the whole network. In this paper, we focus on the development of a fast and effective greedy heuristic for the MPIDS problem, because greedy heuristics are an essential component of more sophisticated metaheuristics. Thus, the development of well-working greedy heuristics supports the development of efficient metaheuristics. Extensive experiments conducted on a wide range of social networks and complex networks confirm the overall superiority of our greedy algorithm over its competitors, especially when the problem size becomes large. Moreover, we compare our algorithm with the integer linear programming solver CPLEX. While the performance of CPLEX is very strong for small and medium-sized networks, it reaches its limits when being applied to the largest networks. However, even in the context of small and medium-sized networks, our greedy algorithm is only 2.53% worse than CPLEX.

关键词： greedy algorithm minimum positive influence dominating set problem heuristic search social network

来源：评论

学校读者我要写书评

暂无评论

Minimum Cost Reconfigurable Network Template Design With Guaranteed QoS

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2020年第2期68卷 1013-1024页

作者： Xu, Xiaoli Veitch, Darryl Li, Yonghui Vucetic, Branka Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China Univ Technol Sydney Sch Elect & Data Engn Ultimo NSW 2006 Australia Univ Sydney Sch Elect & Informat Engn Sydney NSW 2006 Australia Peng Cheng Lab Shenzhen 518055 Peoples R China

Conventional networks are based on layered protocols with intensive cross-layer interactions and complex signal processing at every node, making it difficult to meet the ultra-low latency requirement of mission critical applications in future communication systems. In this paper, we address this issue by proposing the concept of network template, which allows data to flow through it at the transmission symbol level, with minimal node processing. This is achieved by carefully calibrating the inter-connecting links among the nodes and pre-calculating the routing/network coding actions for each node, according to a set of preconfigured flows. In this paper, we focus on the minimum cost network template design to minimize the connections within the template, while ensuring that all the pre-defined configurations are feasible with the guaranteed throughput, latency and reliability. We show that the minimum cost network template design problem is difficult to solve optimally in general. We thus propose an efficient greedy algorithm to find a close-to-optimal solution. Simulation results show that the construction cost of the templates obtained by the proposed algorithm is very close to a lower bound. Furthermore, the construction cost increases only slightly with the number of pre-defined configurations, which confirms the flexibility of the network template design.

关键词： Ultra-low latency reconfigurable network template network coding linear optimization greedy algorithm quality-of-service (QoS)

来源：评论

学校读者我要写书评

暂无评论

APPROXIMATION LIMITATIONS OF PURE DYNAMIC PROGRAMMING

引用

SIAM JOURNAL ON COMPUTING 2020年第1期49卷 170-205页

作者： Jukna, Stasys Seiwert, Hannes Goethe Univ Frankfurt Inst Comp Sci D-60325 Frankfurt Germany Vilnius Univ Fac Math & Informat Inst Data Sci & Digital Technol LT-03225 Vilnius Lithuania

We prove the first, even superpolynomial, lower bounds on the size of tropical (min,+) and (max,+) circuits approximating given optimization problems. Many classical dynamic programming (DP) algorithms for optimization problems are pure in that they only use the basic min, max, + operations in their recursion equations. Tropical circuits constitute a rigorous mathematical model for this class of algorithms. An algorithmic consequence of our lower bounds for tropical circuits is that the approximation powers of pure DP algorithms and greedy algorithms are incomparable. That pure DP algorithms can hardly beat greedy in approximation is long known. New in this consequence is that the converse also holds.

关键词： dynamic programming greedy algorithm approximation lower bounds

来源：评论

学校读者我要写书评

暂无评论

Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2020年第1期21卷 1-49页

作者： Mokhtari, Aryan Hassani, Hamed Karbasi, Amin Univ Texas Austin Dept Elect & Comp Engn Austin TX 78712 USA Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA Yale Univ Dept Elect Engn & Comp Sci New Haven CT 06520 USA

This paper considers stochastic optimization problems for a large class of objective functions, including convex and continuous submodular. Stochastic proximal gradient methods have been widely used to solve such problems;however, their applicability remains limited when the problem dimension is large and the projection onto a convex set is computationally costly. Instead, stochastic conditional gradient algorithms are proposed as an alternative solution which rely on (i) Approximating gradients via a simple averaging technique requiring a single stochastic gradient evaluation per iteration;(ii) Solving a linear program to compute the descent/ascent direction. The gradient averaging technique reduces the noise of gradient approximations as time progresses, and replacing projection step in proximal methods by a linear program lowers the computational complexity of each iteration. We show that under convexity and smoothness assumptions, our proposed stochastic conditional gradient method converges to the optimal objective function value at a sublinear rate of O(1/t(1/3)). Further, for a monotone and continuous DR-submodular function and subject to a general convex body constraint, we prove that our proposed method achieves a ((1-1/e)OPT-epsilon) guarantee (in expectation) with O(1/epsilon(3)) stochastic gradient computations. This guarantee matches the known hardness results and closes the gap between deterministic and stochastic continuous submodular maximization. Additionally, we achieve ((1/e)OPT-epsilon) guarantee after operating on O(1/epsilon(3)) stochastic gradients for the case that the objective function is continuous DR-submodular but non-monotone and the constraint set is a down-closed convex body. By using stochastic continuous optimization as an interface, we also provide the first (1-1/e) tight approximation guarantee for maximizing a monotone but stochastic submodular set function subject to a general matroid constraint and (1/e) approximation guarantee

关键词： Stochastic optimization conditional gradient methods convex minimization submodular maximization gradient averaging Frank-Wolfe algorithm greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Discovering a junction tree behind a Markov network by a greedy algorithm

引用

OPTIMIZATION AND ENGINEERING 2013年第4期14卷 503-518页

作者： Szantai, Tamas Kovacs, Edith Budapest Univ Technol & Econ Inst Math H-1111 Budapest Hungary AVF Coll Management Budapest Dept Math H-1114 Budapest Hungary

In our paper (Annals of Operations Research, 193: 71-90, 2012) we introduced a special kind of k - 1-width junction tree, called k-th order cherry tree in order to approximate a joint probability distribution. The approximation is the best if the Kullback-Leibler divergence between the true joint probability distribution and the approximating one is minimal. Finding the best approximating k - 1-width junction tree probability distribution is NP-complete if 2 < k < d - 1, where d is the dimension of the joint probability distribution (see Karger and Srebro in 12th ACM-SIAM Symposium on Discrete algorithms (SODA), 2001, Malvestuto in Kybernetika 48:825-844, 2012). In Broad Research in Artificial Intelligence and Neuroscience (BRAIN), special issue on complexity in sciences and artificial intelligence, pp. 40-45, 2010 we also proved that the best approximating k - 1-width junction tree probability distribution can be embedded into a k-th order cherry tree probability distribution. We introduce here a greedy algorithm resulting very good approximations in reasonable computing time. We prove then that if the Markov network which encodes the conditional independences of the multivariate probability distribution fulfills some requirements then our greedy algorithm is able to find the true probability distribution. Our algorithm uses just the k-th order marginal probability distributions as input. We compare the results of the greedy algorithm proposed in this paper with the greedy algorithm proposed by Malvestuto (IEEE Trans. Syst. Man Cybern. 21:1287-1294, 1991).

关键词： greedy algorithm Conditional independence Markov network Triangulated graph Graphical models Cherry tree probability distribution Contingency table

来源：评论

学校读者我要写书评

暂无评论

RETRACTED: Energy efficient multi-tasking for edge computing using federated learning

引用

International Journal of Pervasive Computing and Communications 2022年第3期20卷 18-32页

作者： Mukesh Soni Nihar Ranjan Nayak Ashima Kalra Sheshang Degadwala Nikhil Kumar Singh Shweta Singh Department of CSE University Centre for Research and Development Chandigarh University Mohali India School of Information Science Presidency University Bengaluru India ECE Department Chandigarh Engineering College Landran India Department of Computer Engineering Sigma Institute of Engineering Vadodara India Department of CSE Maulana Azad National Institute of Technology Bhopal India Electronics and Communication Department IES College of Technology Bhopal India

Purpose The purpose of this paper is to improve the existing paradigm of edge computing to maintain a balanced energy usage. Design/methodology/approach The new greedy algorithm is proposed to balance the energy consumption in edge computing. Findings The new greedy algorithm can balance energy more efficiently than the random approach by an average of 66.59 percent. Originality/value The results are shown in this paper which are better as compared to existing algorithms.

关键词： Edge computing Federated learning Energy balancing greedy algorithm Multi-tasking

来源：评论

学校读者我要写书评

暂无评论

Effects of envelope and dictionary structure on the performance of matching pursuit

引用

IET SIGNAL PROCESSING 2020年第2期14卷 89-96页

作者： Rozanski, Piotr T. Univ Warsaw Coll Interfac Individual Studies Math & Nat Sci M Ul Stefana Banacha 2C PL-02097 Warsaw Poland

Matching pursuit is a greedy algorithm for computing a decomposition of the given signal as a linear combination of elements from an over-complete set (a 'dictionary'). This study generalises the construction of an optimal dictionary to non-Gaussian envelope functions, and demonstrates that optimising the dictionary with regard to the envelope function has a significant effect on the decomposition accuracy. The dictionary construction is then evaluated and compared for a range of possible envelope functions. Based on the results, a novel 'meta-exponential' envelope function is proposed and it is shown that for any given decomposition accuracy, it allows one to reduce the dictionary size (hence the computational time) by similar to 10% compared to the most common case of decomposition with Gabor dictionaries. More importantly, the results of a decomposition study on high-quality audio files are presented, confirming that both the choice of the envelope and adjusting the dictionary to a given envelope have a significant effect on the overall performance of matching pursuit.

关键词： greedy algorithms time-frequency analysis iterative methods signal representation dictionaries audio signal processing optimisation matching pursuit dictionary structure greedy algorithm given signal over-complete set optimal dictionary nonGaussian envelope functions dictionary construction possible envelope functions novel meta-exponential envelope function given decomposition accuracy dictionary size computational time Gabor dictionaries decomposition study given envelope

来源：评论

学校读者我要写书评

暂无评论

The b-branching problem in digraphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 283卷 565-576页

作者： Kakimura, Naonori Kamiyama, Naoyuki Takazawa, Kenjiro Keio Univ Fac Sci & Technol Dept Math Yokohama Kanagawa 2238522 Japan Kyushu Univ Inst Math Ind Fukuoka 8190395 Japan Hosei Univ Fac Sci & Engn Dept Ind & Syst Engn Tokyo 1848584 Japan

In this paper, we introduce the concept of b-branchings in digraphs, which is a generalization of branchings serving as a counterpart of b-matchings. Here b is a positive integer vector on the vertex set of a digraph D, and a b-branching is defined as a common independent set of two matroids defined by b: an arc set is a b-branching if it has, for every vertex v of D, at most b(v) arcs entering v, and it is an independent set of a certain sparsity matroid defined by b and D. We demonstrate that b-branchings yield an appropriate generalization of branchings by extending several classic results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b-branching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b-branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b-branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b(v) arcs sharing the terminal vertex v. (C) 2020 Elsevier B.V. All rights reserved.

关键词： greedy algorithm Packing Matroid intersection Sparsity matroid Arborescence

来源：评论

学校读者我要写书评

暂无评论

Convergence rate of the semi-supervised greedy algorithm

引用

NEURAL NETWORKS 2013年 44卷 44-50页

作者： Chen, Hong Zhou, Yicong Tang, Yuan Yan Li, Luoqing Pan, Zhibin Huazhong Agr Univ Coll Sci Wuhan 430070 Peoples R China Univ Macau Dept Comp & Informat Sci Macau 999078 Peoples R China Hubei Univ Fac Math & Comp Sci Wuhan 430062 Peoples R China

This paper proposes a new greedy algorithm combining the semi-supervised learning and the sparse representation with the data-dependent hypothesis spaces. The proposed greedy algorithm is able to use a small portion of the labeled and unlabeled data to represent the target function, and to efficiently reduce the computational burden of the semi-supervised learning. We establish the estimation of the generalization error based on the empirical covering numbers. A detailed analysis shows that the error has O(n(-1)) decay. Our theoretical result illustrates that the unlabeled data is useful to improve the learning performance under mild conditions. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Semi-supervised learning Sparse greedy algorithm Data-dependent hypothesis space Generalization error

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：