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

Joint Client Association and Random Access Control for MU-MIMO WLANs

IEEE TRANSACTIONS ON MOBILE COMPUTING 2020年第12期19卷 2818-2832页

作者： Wong, Wangkit Chau, Kam-Wa Chan, S. -H. Gary Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Kowloon Clear Water Bay Hong Kong Peoples R China

In interfering WLANs, clients are usually non-uniformly distributed. Therefore, their throughput can be improved by association control. WLANs adopt DCF (Distributed Coordinating Function) for media access control. The transmit probability of an AP is governed by its CW (Contention Window). Random Access control is to determine the CW size and hence the transmit probability of each AP. Client association control and random access control are coupled. APs associated with more clients require higher channel access opportunities. On the other hand, APs with higher transmit probability should serve more clients. We study the novel problem of maximizing the proportional fairness of client throughput by joint association control and random access control. As the joint problem is non-convex, we first consider that client association is given and propose an optimal policy for random access control. Given the CWs of APs, we propose a factor-2 approximation algorithm, Greedy-Asso to address the client association problem. Inspired by the optimal access control policy and Greedy-Asso, we further propose a distributed algorithm, termed CARA to tackle the joint optimization problem. Extensive simulation and experimental studies show that it outperforms comparison schemes by a wide margin in terms of throughput and fairness.

关键词： WLANs distributed optimization load balancing association control approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Near-optimal and learning-driven task offloading in a 5G multi-cell mobile edge cloud

引用

COMPUTER NETWORKS 2020年 176卷 107276-107276页

作者： Xia, Qiufen Lou, Zheng Xu, Wenzheng Xu, Zichuan Dalian Univ Technol Int Sch Informat Sci & Engn Dalian Liaoning Peoples R China Dalian Univ Technol Sch Software Dalian Liaoning Peoples R China Sichuan Univ Coll Comp Sci Chengdu Sichuan Peoples R China

With development well underway, 5G is envisioned as an enabler of lighting fast mobile services, such as virtual reality, augmented reality, live video analytics, and etc. In particular, multi-cell Mobile Edge Clouds (MEC) with 5G base stations endowed with computing capability are able to promote the Quality of Services (QoS) of mobile users by executing tasks in the edge cloud. Due to the varying 5G network conditions and limited computation capacity of each base station in the multi-cell MEC, as well as the stringent QoS requirements, a fundamental and challenging problem is how to offload user tasks to the edge cloud, such that the energy consumption of mobile devices is minimized. In this paper, we first formulate the offline and online location-aware mobile task offloading problems in a multi-cell MEC. For the offline location-aware mobile task offloading problem, we then develop an exact solution and an approximation algorithm with an approximation ratio. For the online problem, we thirdly propose a novel deep reinforcement learning-based offloading algorithm for mobile users to obtain the optimal offloading policy. We finally conduct extensive experiments by simulations to evaluate the proposed algorithms against existing benchmarks. The experimental results show that the proposed algorithms are promising and outperform the benchmark algorithms by significantly reducing energy cost of mobile devices and delays experienced by mobile users.

关键词： Task offloading Mobile edge computing approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Complexity and algorithms for Semipaired Domination in Graphs

引用

THEORY OF COMPUTING SYSTEMS 2020年第7期64卷 1225-1241页

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

For a graph G = (V, E) with no isolated vertices, a set D subset of V is called a semipaired dominating set of G if (i) D is a dominating set of G, and (ii) D can be partitioned into two element subsets such that the vertices in each two element set are at distance at most two. The minimum cardinality of a semipaired dominating set of G is called the semipaired domination number of G, and is denoted by gamma(pr2)(G). TheMINIMUM SEMIPAIRED DOMINATION problem is to find a semipaired dominating set of G of cardinality gamma(pr2)(G). In this paper, we initiate the algorithmic study of the MINIMUM SEMIPAIRED DOMINATION problem. We show that the decision version of the MINIMUM SEMIPAIRED DOMINATION problem is NP-complete for bipartite graphs and chordal graphs. On the positive side, we present a linear-time algorithm to compute a minimum cardinality semipaired dominating set of interval graphs. We also propose a 1 + ln(2 Delta + 2)-approximation algorithm for the MINIMUM SEMIPAIRED DOMINATION problem, where Delta denotes the maximum degree of the graph and show that the MINIMUM SEMIPAIRED DOMINATION problem cannot be approximated within (1 - epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless P=NP.

关键词： Domination Semipaired domination Interval graphs Graph algorithm NP-complete approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Providing Service Continuity in Clouds Under Power Outage

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2020年第5期13卷 930-943页

作者： Wu, Weiwei Wang, Jianping Lu, Kejie Qi, Wen Shan, Feng Luo, Junzhou Southeast Univ Sch Comp Sci & Engn Nanjing 210096 Jiangsu Peoples R China City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China Univ Puerto Rico Dept Elect & Comp Engn Mayaguez PR 00682 USA Shanghai Univ Elect Power Sch Comp Engn Shanghai 200090 Peoples R China

In cloud computing, it is crucial to maintain service continuity, while power outage is one of the most common and serious threats. To improve the resilience of cloud against power outage, a service provider usually deploys emergency energy supply (e.g., UPSs and generators) in a data center. When a power outage at a data center happens, the cloud service provider needs to make the operation decision on which subset of VMs to keep running and which servers to host such VMs to minimize its loss (or maximize its profit) using the emergency energy supply while the selected VMs are running in the affected data center until they are finished, migrated to other data centers, or normal power supply of the affected data center has been restored. No prior research has theoretically studied such a cloud service continuity problem under power outage. In this paper, we tackle this challenge and investigate the cloud service continuity problem. Specifically, we consider that a profit is associated with maintaining the continuity of a service, denoted as service continuity profit. Based on that we first formulate an optimization problem that aims to maximize the total profit subject to energy constrains. After showing the hardness of the problem, we focus on the design of approximation algorithms for solving the problem, where we consider two practical cases. In the first one with sufficient number of servers for re-provisioning, we develop a constant approximation algorithm of which the worst-case performance approaches the optimal solution within a constant factor (approximate to 4.5-6.4). In the second one, we consider the general case with limited number of servers, and we develop an approximation algorithm with an approximation ratio of around 5.7-8. By combining these two algorithms together, we can achieve both good worst-case performance and average performance. Simulation results demonstrate the efficiency in terms of maximizing the service continuity profit of the propo

关键词： Power system faults Power system restoration Cloud computing approximation algorithms Servers Schedules Service continuity power outage cloud recovery VM consolidation energy-efficient scheduling approximation algorithm profit maximization

来源：评论

学校读者我要写书评

暂无评论

Dividing Splittable Goods Evenly and With Limited Fragmentation

引用

algorithmICA 2020年第5期82卷 1298-1328页

作者： Damaschke, Peter Chalmers Univ Dept Comp Sci & Engn S-41296 Gothenburg Sweden

A splittable good provided in n pieces shall be divided as evenly as possible among m agents, where every agent can take shares from at most F pieces. We call F the fragmentation and mainly restrict attention to the cases F = 1 and F = 2. For F = 1, the max-min and min-max problems are solvable in linear time. The case F = 2 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if m = n - 1, and a solution always exists in this case, in contrast to F = 1. Moreover, the problem is fixed-parameter tractable in the parameter 2m - n. (Note that this parameter measures the number of agents above the trivial threshold m = n/2.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximationpreserving reduction from our original splitting problem with fragmentation F = 2 to this averaging problem, and some approximation results in cases when m is close to either n or n/2.

关键词： Fair division Weighted graph Linear-time algorithm Parameterized algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

MORE: Multi-node Mobile Charging Scheduling for Deadline Constraints

引用

ACM TRANSACTIONS ON SENSOR NETWORKS 2020年第1期17卷 1–21页

作者： Yang, Panlong Wu, Tao Dai, Haipeng Rao, Xunpeng Wang, Xiaoyu Wan, Peng-Jun He, Xin Univ Sci & Technol China Hefei Anhui Peoples R China Natl Univ Def Technol Huangshan Rd 460 Hefei 230009 Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing Peoples R China Army Engn Univ PLA Commun Engn Nanjing Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA

Due to the merit without requiring charging cable, wireless power transfer technology has drawn rising attention as a new method to replenish energy for Wireless Rechargeable Sensor Networks. In this article, we study the mobile charger scheduling problem for multi-node recharging with deadline constraints. Our target is to maximize the overall effective charging utility and minimize the traveling time for moving as well. Instead of charging only once over a scheduling cycle, we incorporate the multi-node charging strategy with deadline constraints, where charging spots and tour are jointly optimized. Specifically, we formulate the effective charging utility maximization problem as a monotone submodular function optimization subject to a partition matroid constraint, and we propose a simple but effective 2-approximation greedy algorithm. After that, we derive the result of global scheduling and present the grid-based skip-substitute operation to further save the traveling time, which can increase the charging utility. Finally, we conduct the evaluation for the performance of our scheduling scheme. The simulation and field experiment results show that our algorithm excels in terms of effective charging utility.

关键词： Wireless energy transfer deadline-based charger scheduling matriod approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Interval Job Scheduling With Machine Launch Cost

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2020年第12期31卷 2776-2788页

作者： Ren, Runtian Zhu, Yuqing Li, Chuanyou Tang, Xueyan Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore Southeast Univ Sch Comp Sci & Engn Nanjing 210096 Peoples R China

We study an interval job scheduling problem in distributed systems. We are given a set of interval jobs, with each job specified by a size, an arrival time and a processing length. Once a job arrives, it must be placed on a machine immediately and run for a period of its processing length without interruption. The homogeneous machines to run jobs have the same capacity limits such that at any time, the total size of the jobs running on any machine cannot exceed its capacity. Launching each machine incurs a fixed cost. After launch, a machine is charged a constant cost per time unit until it is terminated. The problem targets to minimize the total cost incurred by the machines for processing the given set of interval jobs. We focus on the algorithmic aspects of the problem in this article. For the special case where all the jobs have a unit size equal to the machine capacity, we propose an optimal offline algorithm and an optimal 2-competitive online algorithm. For the general case where jobs can have arbitrary sizes, we establish a non-trivial lower bound on the optimal solution. Based on this lower bound, we propose a 5-approximation algorithm in the offline setting. In the non-clairvoyant online setting, we design a O(mu)-competitive Modified First-Fit algorithm which is near optimal (mu is the max/min job processing length ratio). In the clairvoyant online setting, we propose an asymptotically optimal O(root log mu)-competitive algorithm based on our Modified First-Fit strategy.

关键词： Job scheduling online algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The stochastic critical node problem over trees

引用

NETWORKS 2020年第3期76卷 381-401页

作者： Hosteins, Pierre Scatamacchia, Rosario Univ Gustave Eiffel COSYS ESTAS F-59666 Lille France Politecn Torino Dipartimento Ingn Gest & Prod Turin Italy

We tackle a stochastic version of the critical node problem (CNP) where the goal is to minimize the pairwise connectivity of a graph by attacking a subset of its nodes. In the stochastic setting considered, the outcome of attacks on nodes is uncertain. In our work, we focus on trees and demonstrate that over trees the stochastic CNP actually generalizes to the stochastic critical element detection problem where the outcome of attacks on edges is also uncertain. We prove the NP-completeness of the decision version of the problem when connection costs are one, while its deterministic counterpart was proved to be polynomial. We then derive a nonlinear model for the considered CNP version over trees and provide a corresponding linearization based on the concept ofprobability chains. Moreover, given the features of the derived linear model, we devise an exact Benders decomposition (BD) approach where we solve the slave subproblems analytically. A strength of our approach is that it does not rely on any statistical approximation such as the sample average approximation, which is commonly employed in stochastic optimization. We also introduce an approximation algorithm for the problem variant with unit connection costs and unit attack costs, and a specific integer linear model for the case where all the survival probabilities of the nodes in case of an attack are equal. Our methods are capable of solving relevant instances of the problem with hundreds of nodes within 1 hour of computational time. With this work, we aim to foster research on stochastic versions of the CNP, a problem tackled mainly in deterministic contexts so far. Interestingly, we also show a successful application of the concept of probability chains for problem linearizations significantly improved by decomposition methods such as the BD.

关键词： approximation algorithm Benders decomposition critical element detection critical node problem network interdiction probability chains stochastic integer programming trees

来源：评论

学校读者我要写书评

暂无评论

approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings

引用

algorithmS 2021年第2期14卷 65页

作者： Hucke, Danny Reh, Carl Philipp Univ Siegen Dept Elektrotech & Informat D-57068 Siegen Germany

A grammar-based compressor is an algorithm that receives a word and outputs a context-free grammar that only produces this word. The approximation ratio for a single input word is the size of the grammar produced for this word divided by the size of a smallest grammar for this word. The worst-case approximation ratio of a grammar-based compressor for a given word length is the largest approximation ratio over all input words of that length. In this work, we study the worst-case approximation ratio of the algorithms Greedy, RePair and LongestMatch on unary strings, i.e., strings that only make use of a single symbol. Our main contribution is to show the improved upper bound of O((log n)(8) center dot (log log n)(3)) for the worst-case approximation ratio of Greedy. In addition, we also show the lower bound of 1.34847194... for the worst-case approximation ratio of Greedy, and that RePair and LongestMatch have a worst-case approximation ratio of log(2)(3).

关键词： data compression grammar-based compression approximation algorithm addition chain

来源：评论

学校读者我要写书评

暂无评论

A primal-dual algorithm for the minimum partial set multi-cover problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第3期39卷 725-746页

作者： Ran, Yingli Shi, Yishuo Tang, Changbing Zhang, Zhao Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China Acad Sinica Inst Informat Sci Taibei 11529 Taiwan

In a minimum partial set multi-cover problem (MinPSMC), given an element set E, a collection of subsets S subset of 2E a cost wSon each set S is an element of S a covering requirement re\for each element e is an element of Eand an integer k, the goal is to find a sub-collection F subset of S to fully cover at least k elements such that the cost of F is as small as possible, where element e is fully covered by F if it belongs to at least re sets of FOn the application side, the problem has its background in the seed selection problem in a social network. On the theoretical side, it is a natural combination of the minimum partial (single) set cover problem (MinPSC) and the minimum set multi-cover problem (MinSMC). Although both MinPSC and MinSMC admit good approximations whose performance ratios match those lower bounds for the classic set cover problem, previous studies show that theoretical study on MinPSMC is quite challenging. In this paper, we prove that MinPSMC cannot be approximated within factor O(n12(loglogn)c)for some constant c under the ETH assumption. Furthermore, assuming rmax is a constant, where rmax=maxe is an element of Ere is the maximum covering requirement and f is the maximum number of sets containing a common element, we present a primal-dual algorithm for MinPSMC and show that its performance ratio is O(n) We also improve the ratio for a restricted version of MinPSMC which possesses a graph-type structure.

关键词： Partial set multi-cover problem Positive influence dominating set Densest l-subgraph problem Primal-dual approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：