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

6th International Symposium on Combinatorial Optimization

作者： Aba, Massinissa Ait Zaourar, Lilia Munier, Alix CEA LIST Comp & Design Environm Lab F-91191 Gif Sur Yvette France LIP6 UPMC 4 Pl Jussieu F-75005 Paris France

ISBN: (纸本)9783030532611;9783030532628

This work addresses the problem of scheduling parallel applications into hybrid platforms composed of two different types of resources. We focus on finding a generic approach to schedule applications represented by directed acyclic graphs that minimises makespan with performance guarantee. A three-phase algorithm is proposed;the first two phases consist in solving linear formulations to find the type of processor assigned to execute each task. In the third phase, we compute the start execution time of each task to generate a feasible schedule. Finally, we test our algorithm on a large number of instances. These tests demonstrate that the proposed algorithm achieves a close-to-optimal performance.

关键词： Scheduling DAG applications Makespan Hybrid platform CPU GPU approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings 26th

Approximation Ratios of RePair, LongestMatch and Greedy on U...

引用

26th International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Hucke, Danny Univ Siegen Siegen Germany

ISBN: (纸本)9783030326852;9783030326869

A grammar-based compressor computes for a given input w a context-free grammar that produces only w. So-called global grammar-based compressors (RePair, LongestMatch and Greedy) achieve impressive practical compression results, but the recursive character of those algorithms makes it hard to achieve strong theoretical results. To this end, this paper studies the approximation ratio of those algorithms for unary input strings, which is strongly related to the field of addition chains. We show that in this setting, RePair and LongestMatch produce equal size grammars that are by a factor of at most log(2)(3) larger than a smallest grammar. We also provide a matching lower bound. The main result of this paper is a new lower bound for Greedy of 1.348 ... , which improves the best known lower bound for arbitrary (not necessarily unary) input strings.

关键词： Data compression Grammar-based compression approximation algorithm Addition chain

来源：评论

学校读者我要写书评

暂无评论

Maximum Target Coverage Problem in Mobile Wireless Sensor Networks

引用

SENSORS 2021年第1期21卷 184-184页

作者： Liang, Dieyan Shen, Hong Chen, Lin Sun Yat Sen Univ Sch Comp Sci & Engn Guangzhou 510006 Peoples R China

We formulate and analyze a generic coverage optimization problem arising in wireless sensor networks with sensors of limited mobility. Given a set of targets to be covered and a set of mobile sensors, we seek a sensor dispatch algorithm maximizing the covered targets under the constraint that the maximal moving distance for each sensor is upper-bounded by a given threshold. We prove that the problem is NP-hard. Given its hardness, we devise four algorithms to solve it heuristically or approximately. Among the approximate algorithms, we first develop randomized (1-1/e)-optimal algorithm. We then employ a derandomization technique to devise a deterministic (1-1/e)-approximation algorithm. We also design a deterministic approximation algorithm with nearly Delta(-1) approximation ratio by using a colouring technique, where denotes the maximal number of subsets covering the same target. Experiments are also conducted to validate the effectiveness of the algorithms in a variety of parameter settings.

关键词： approximation algorithm integer programming mobile sensors target coverage wireless sensor network

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the Generalized Stacker Crane Problem 11th

Approximation Algorithms for the Generalized Stacker Crane P...

引用

11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Li, Jianping Liu, Xiaofei Li, Weidong Guan, Li Lichen, Junran Yunnan Univ Dept Math Kunming 650091 Yunnan Peoples R China

ISBN: (纸本)9783319711508;9783319711492

The stacker crane problem is treated as one modified arc routing problem. This problem is to find some route for stacker cranes on a construction site such that all arcs in a mixed graph G = (V, E boolean OR A;w) must be traversed at least once. In the real literature, since many different building materials must be handled, we consider the generalized stacker crane (GSC) problem, and the objective of this new problem is to determine a minimum weighted tour C traversing each arc e (in A) a number of times between the lower demand and upper demand. In this paper, we design two approximation algorithms for the GSC problem. The first algorithm uses some exact algorithm to solve the integral circulation problem, and the second algorithm uses some approximation algorithm to solve the metric traveling salesman problem. Combining these two approximation algorithms, we can design a 9/5-approximation algorithm to solve the GSC problem.

关键词： approximation algorithm Stacker crane problem Lower/upper demands

来源：评论

学校读者我要写书评

暂无评论

Vertex-Edge Domination in Unit Disk Graphs 6th

Vertex-Edge Domination in Unit Disk Graphs

引用

6th International Conference on algorithms and Discrete Applied Mathematics

作者： Jena, Sangram K. Das, Gautam K. Indian Inst Technol Gauhati India

ISBN: (纸本)9783030392185;9783030392192

Let G = (V, E) be a simple graph. A set D is an element of V is called a vertex-edge dominating set of G if for each edge e = (u, v) is an element of E, either u or v is in D or one vertex from their neighbor is in D. Simply, a vertex v is an element of V, vertex-edge dominates every edge (u, v), as well as every edge adjacent to these edges. The vertex-edge dominating problem is to find a minimum vertex-edge dominating set of G. Herein, we study the vertex-edge dominating set problem in unit disk graphs and prove that this problem is NP-hard in that class of graphs. We also show that the problem admits a polynomial time approximation scheme (PTAS) in unit disk graphs.

关键词： Dominating set Vertex-edge dominating set Unit disk graph approximation algorithm approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Optimal Device Selection for Federated Learning over Mobile Edge Networks

Optimal Device Selection for Federated Learning over Mobile ...

引用

40th IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Ching, Cheng-Wei Liu, Yu-Chun Yang, Chung-Kai Kuo, Jian-Jhih Su, Feng-Ting Natl Chung Cheng Univ Dept Comp Sci Minxiong Township Chiayi Taiwan Natl Chung Cheng Univ Dept Elect Engn Minxiong Township Chiayi Taiwan Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan

ISBN: (纸本)9781728170022

Data privacy preservation has drawn much attention with emerging machine learning applications. Federated Learning is thus developed to offer decentralized learning on user devices. However, it is difficult to jointly address multiple issues such as device selection, upload scheduling, and payment minimization. To jointly optimize the issues above, we first formulate a new optimization problem, named TRAIN, to minimize the training cost (including incentive payment and upload time) while ensuring the data requirement. We then prove the NP-hardness and propose a 3-approximation algorithm, named DETECT to obtain a near-optimal solution. Simulation results manifest that DETECT reduces the training cost by 50% compared with other traditional methods and achieves high accuracy and short convergence time.

关键词： federated learning approximation algorithm mobile edge network

来源：评论

学校读者我要写书评

暂无评论

Scheduling with Non-renewable Resources: Minimizing the Sum of Completion Times 6th

Scheduling with Non-renewable Resources: Minimizing the Sum ...

引用

6th International Symposium on Combinatorial Optimization

作者： Berczi, Kristof Kiraly, Tamas Omlor, Simon Eotvos Lorand Univ Dept Operat Res MTA ELTE Egervary Res Grp Budapest Hungary TU Hamburg Inst Algorithms & Complex Hamburg Germany

ISBN: (纸本)9783030532611;9783030532628

We consider single-machine scheduling problems with a non-renewable resource. In this setting, there are n jobs, each characterized by a processing time, a weight, and a resource requirement. At given points in time, certain amounts of the resource are made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that each job has the required resource amount available at the start of its processing. We consider the objective of minimizing the weighted sum of completion times. The main contribution of the paper is a PTAS for the case of 0 processing times (1 vertical bar rm = 1, p(j) = 0 vertical bar Sigma w(j)C(j)). In addition, we show strong NP-hardness of the case of unit resource requirements and weights (1 vertical bar rm = 1, a(j) = 1 vertical bar Sigma C-j), thus answering an open question of Gyorgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the latter problem.

关键词： Scheduling Non-renewable resources PTAS approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Scheduling Multiple Two-Stage Flowshops 1

引用

23rd International Computing and Combinatorics Conference (COCOON)

作者： Wu, Guangwei Wang, Jianxin Cent South Univ Sch Informat Sci & Engn Changsha Peoples R China Cent South Univ Forestry & Technol Coll Comp & Informat Engn Changsha Peoples R China

ISBN: (数字)9783319623894

ISBN: (纸本)9783319623894;9783319623887

This paper studies the problem that schedules n two-stage jobs on m multiple two-stage flowshops, with the objective of minimizing the makespan. The problem is NP-hard even when m is a fixed constant, and becomes strongly NP-hard when m is a part of input. A 17/6-approximation algorithm along with its analysis is presented for arbitrary m >= 2. This is the first approximation algorithm for multiple flowshops when the number m of flowshops is a part of input. The arbitrary m and the time complexity O(n log n + mn) of the algorithm demonstrate that the problem, which plays an important role in the current research in cloud computing and data centers, can be solved efficiently with a reasonable level of satisfaction.

关键词： Scheduling Multiple two-stage flowshops approximation algorithm Cloud computing

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Maximum Coverage with Group Budget Constraints 11th

Approximation Algorithms for Maximum Coverage with Group Bud...

引用

11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Guo, Longkun Li, Min Xu, Dachuan Fuzhou Univ Coll Math & Comp Sci Fuzhou 350116 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Beijing Univ Technol Coll Appl Sci Beijing 100124 Peoples R China

ISBN: (纸本)9783319711478;9783319711461

In this paper, we study the maximum coverage problem with group budget constraints (MCG) that generalizes the maximum coverage problem. Given a ground set U in which i E U has a non-negative weight w,, a positive integer k and a collection of sets S, the maximum coverage problem is to pick k sets of S to maximize the total weight of their union. In MCG, S is partitioned into groups g1,, c and the goal is to pick k sets from S to maximize the total weight of their union, with at most ni E Z sets being picked from group ci. For MCG with n,/ = 1, Vi, we first present a factor 1 eapproximation algorithm which runs in exponential time. Then we improve the runtime of the algorithm to 0 ( (m n q)3.5 L k3.5 q7 L) where 1,51 = m, =12, q is the number of groups, and L is the length of the input. The key idea of the improvement is to model selecting groups for MCG as computing a constrained flow in a corresponding auxiliary graph. It is also shown that the algorithm can be extended to solve MCG with general ni. Later, based on the main idea of partition we further improve the runtime of the algorithm to 0((m n q)3.5 L k(51.5 L), while compromise the approximation ratio to 1 e+-5-1, where (5 > 2 is any fixed integer. Consequently, we can balance approximation ratio and runtime of the algorithm by setting the value of S. This improves the previous best ratio of 0.5 on MCG due to Chekuri and Kumar [4].

关键词： Maximum coverage problem with group budget constraints approximation algorithm Auxiliary graph Network flow Randomized linear programming rounding Partition

来源：评论

学校读者我要写书评

暂无评论

Quasilinear approximation Scheme for Steiner Multi Cycle in the Euclidean plane 10th

Quasilinear Approximation Scheme for Steiner Multi Cycle in ...

引用

10th Latin and American algorithms, Graphs, and Optimization Symposium (LAGOS)

作者： Lintzmayer, Carla N. Miyazawa, Flavio K. Moura, Phablo F. S. Xavier, Eduardo C. Fed Univ ABC Ctr Math Comp & Cognit Santo Andre SP Brazil Univ Estadual Campinas Inst Comp Campinas SP Brazil

We propose a randomized approximation scheme for the Euclidean Steiner Multi Cycle problem which runs in quasilinear time. In this problem, we are given a set of n pairs of points (terminals) tau = {{t(i), t(i)'}(i=1)(n) in the Euclidean plane, and the objective is to find a collection of cycles of minimum cost such that t(i) and t(i)' belong to a same cycle, for each i is an element of {1, ... , n}. This problem extends the Steiner Cycle problem in the same way the Steiner Forest extends the Steiner Tree problem. Additionally, it has applications on routing problems with pickup and delivery locations.

关键词： Euclidean plane geometry Steiner approximation algorithm quasilinear

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：