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

16th International algorithms and Data Structures Symposium (WADS)

作者： Huang, Chien-Chung Kakimura, Naonori Ecole Normale Super CNRS Paris France Keio Univ Yokohama Kanagawa Japan

ISBN: (纸本)9783030247669;9783030247652

In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.4 - epsilon)-approximation algorithm requiring only a single pass through the data. This improves on the currently best (0.363 - epsilon)-approximation algorithm. The required memory space depends only on the size of the knapsack capacity and e.

关键词： Submodular functions Streaming algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Near Optimal Charging Scheduling for 3-D Wireless Rechargeable Sensor Networks with Energy Constraints 39

Near Optimal Charging Scheduling for 3-D Wireless Rechargeab...

引用

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

作者： Lin, Chi Guo, Chunyang Dai, Haipeng Wang, Lei Wu, Guowei Dalian Univ Technol Sch Software Technol Dalian 116023 Peoples R China Key Lab Ubiquitous Network & Serv Software Liaoni Dalian 116621 Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210024 Jiangsu Peoples R China

ISBN: (纸本)9781728125190

Wireless Rechargeable Sensor Network (WRSN) becomes a hot research issue in recent years owing to the breakthrough of wireless power transfer technology. Most prior arts concentrate on developing scheduling schemes in 2-D networks where mobile chargers are placed on the ground. However, few of them are suitable for 3-D scenarios, making it difficult or even impossible to popularize in practical applications. In this paper, we focus on the problem of charging a 3-D WRSN with an Unmanned Aerial Vehicle (UAV) to maximize charged energy within energy constraints. To deal with the problem, we propose a spatial discretization scheme to obtain a finite feasible charging spot set for UAV in 3-D environment and a temporal discretization scheme to determine charging duration for each charging spot. Then, we transform the problem into a submodular maximization problem with routing constraints, and present a cost-efficient approximation algorithm with a provable approximation ratio of e-1/4e(1 - epsilon) to solve it. Lastly, extensive simulations and test-bed experiments show the superior performance of our algorithm.

关键词： 3-D WRSN Spatial and Temporal Discretization approximation algorithm Submodular Optimization

来源：评论

学校读者我要写书评

暂无评论

Efficient Beacon Placement algorithms for Time-of-Flight Indoor Localization 19

Efficient Beacon Placement Algorithms for Time-of-Flight Ind...

引用

27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS)

作者： Wang, Haotian Rajagopal, Niranjini Rowe, Anthony Sinopoli, Bruno Gao, Jie SUNY Stony Brook Stony Brook NY 11794 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Washington Univ St Louis St Louis MO USA

ISBN: (纸本)9781450369091

Beacon-based time-of-flight indoor localization systems have shown great promise for applications ranging from indoor navigation to asset tracking. In large-scale deployments, a major practical challenge is detemiining the placement of a minimal number of beacons that ensures full coverage- each point in the domain lets line-of-sight paths to enough beacons to uniquely localize itself. Three beacons with line-of-sight paths are always enough, but two beacons within line of sight may also work, given a favorable geometry. In this paper, we propose two beacon placement algorithms that leverage the floor plan geometry with provable theoretical guarantees. First, we present a greedy algorithm using properties of sub-modular functions to place O(OPT " ln rn) beacons, where m is the number of discrete location points in the region that need to be localized, and OPT is the size of the optimal solution. Second, we present a random sampling algorillim [ital. places O(OPT " log(OPT)) beacons While localizing all targets. We evaluate our algorithms on both real-world and randomly generated floor plans. Our algorithms place on an average 6- 23% and 12% fewer beacons in real-world topologies and nuldondy generated floor plans respectively, as compared to prior work. We also present a study where we ask users to attempt to place nodes manually and discover that even humans Owl are well versed on the coverage problem find it hard to balance the trade-off between the number of beacons and area localized.

关键词： Indoor Localization Beacon Placement approximation algorithm Computational Geometry

来源：评论

学校读者我要写书评

暂无评论

approximations for Restrictions of The Budgeted and Generalized Maximum Coverage Problems 10th

Approximations for Restrictions of The Budgeted and Generali...

引用

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

作者： Piva, Breno Univ Fed Sergipe Dept Comp Sao Cristovao SE Brazil

In this paper we present approximation preserving reductions from the Budgeted and Generalized Maximum Coverage Problems to the Knapsack Problem with Conflict Graphs. The reductions are used to yield Polynomial Time approximation Schemes for special classes of instances of these problems. Using these approximation schemes, the existence of pseudo-polynomial algorithms are proven and, in more particular cases, these algorithms are shown to have polynomial time complexity. Moreover, the characteristics of the instances that admit these algorithms are analyzed.

关键词： Budgeted Maximum Coverage Generalized Maximum Coverage Knapsack with Conflict Graph approximation algorithm Pseudo-polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

A (2+ε)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

引用

OPERATIONS RESEARCH LETTERS 2018年第4期46卷 438-442页

作者： Sitters, Rene Yang, Liya Vrije Univ Amsterdam NL-1081 HV Amsterdam Netherlands CWI NL-1098 XG Amsterdam Netherlands East China Univ Sci & Technol Shanghai 200237 Peoples R China

We give a (2 + epsilon)-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability ... 详细信息

关键词： Scheduling approximation algorithm Precedence constraints Total weighted completion time

来源：评论

学校读者我要写书评

暂无评论

An effective approximation algorithm for the Malleable Parallel Task Scheduling problem

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2012年第5期72卷 693-704页

作者： Fan, Liya Zhang, Fa Wang, Gongming Liu, Zhiyong Chinese Acad Sci Inst Comp Technol Beijing 100190 Peoples R China Chinese Acad Sci Grad Univ Beijing 100049 Peoples R China IBM China Res Lab Beijing 100193 Peoples R China

The Malleable Parallel Task Scheduling problem (MPTS) is an extension of one of the most classic scheduling problems (P parallel to C-max). The only difference is that for MPTS, each task can be processed simultaneously by more than one processor. Such flexibility could dramatically reduce the makespan, but greatly increase the difficulty for solving the problem. By carefully analyzing some existing algorithms for MPTS, we find each of them suitable for some specific cases, but none is effective enough for all cases. Based on such observations, we introduce some optimization algorithms and improving techniques for MPTS, with their performance analyzed in theory. Combining these optimization algorithms and improving techniques gives rise to our novel scheduling algorithm OCM (Optimizations Combined for MPTS), a 2-approximation algorithm for MPTS. Extensive simulations on random datasets and SPLASH-2 benchmark reveal that for all cases, schedules produced by OCM have smaller makespans, compared with other existing algorithms. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Scheduling algorithm approximation algorithm Parallel computing

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for dominating nodes selection in multi-channel multi-radio wireless sensor networks

引用

INTERNATIONAL JOURNAL OF SENSOR NETWORKS 2012年第1期11卷 57-65页

作者： Li, Deying Liu, Lin Du, Hongwei Renmin Univ China Minist Educ Key Lab Data Engn & Knowledge Engn Beijing 100872 Peoples R China Renmin Univ China Sch Informat Beijing 100872 Peoples R China Harbin Inst Technol Shenzhen Grad Sch Shenzhen Dept Comp Sci & Technol Shenzhen 518055 Peoples R China

In this paper, we study the dominating selection optimisation problem with multiple channels and multiple radios in wireless sensor networks. The objective is to maximise the number of targets covered while selecting at most k nodes and at most k(i) channels with each selected node v(i). Our problem is a general case of the maximum coverage problem. We propose two algorithms: the first one is based on linear programming and PIPAGE rounding, in which its approximation ratio is 1/K(1-(1-1/m)(m)), where m is the number of the dominating nodes and K = max k(i). The second algorithm is based on greedy strategy with low time complexity. The simulation shows that the both two algorithms have good performance.

关键词： dominate node selection multi-channel multi-radio wireless sensor networks approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Simple linear time approximation algorithm for betweenness

引用

OPERATIONS RESEARCH LETTERS 2012年第6期40卷 450-452页

作者： Makarychev, Yury Toyota Technol Inst Chicago IL 60637 USA

We study the Betweenness problem. We are given a set of vertices and betweenness constraints. Each betweenness constraint of the form x similar to {y, z} requires that vertex x lies between vertices y and z. Our goal is to find a vertex ordering that maximizes the number of satisfied constraints. In 1995, Chor and Sudan designed an SDP algorithm that satisfies half of all constraints in a satisfiable instance. We present a simple combinatorial linear time algorithm with the same approximation guarantee. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Betweenness problem approximation algorithm Linear time algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximate Scheduling of DERs with Discrete Complex Injections 19

Approximate Scheduling of DERs with Discrete Complex Injecti...

引用

10th ACM International Conference on Future Energy Systems (e-Energy)

作者： Kuppannagari, Sanmukh Kannan, Rajgopal Prasanna, Viktor K. Univ Southern Calif Ming Hsieh Dept Elect & Comp Engn Los Angeles CA 90007 USA US Army Res Lab 12015 Waterfront Dr Playa Vista CA USA

ISBN: (纸本)9781450366717

Rapid penetration of renewable energy based Distributed Energy Resources (DER) has the potential to exacerbate the challenges inherent in grid frequency and voltage regulation. However, their real time controllability can be leveraged to not only mitigate such challenges, but improve the economics and quality of grid operations. A plethora of DER scheduling algorithms have been developed for fast and efficient scheduling of these resources. These algorithms schedule the complex - real and reactive power injected into (or drawn from) the grid by the DERs under various cost objective functions and grid constraints. However, a vast majority of such algorithms assume the feasible range of power injections to be continuous. In reality, the control options available for several DERs form a discrete space. This implies that the feasible range of power injections also forms a discrete space. This makes DER scheduling an NP-hard problem. Integer/Mixed Integer program based algorithms, which guarantee optimality in the objective value, have been developed. But these are prohibitively expensive in terms of computational time requirements. On the other hand, fast heuristic based solutions have also been developed. But as they do not provide any guarantee on the optimality of the objective, or on satisfying the constraints, they are unreliable for grid operations. Recent works have developed approximation algorithms which offer the best of both the approaches above: (near) optimality and low computational complexity, both of which are governed by a user defined accuracy parameter.. In this work, we significantly improve upon such existing works by developing an approximation algorithm which schedules DERs with complex injections (as opposed to only real injection) and whose runtime is polynomial (as opposed to exponential) in 1/epsilon. We provide theoretical analysis and support them with experimental results to validate the guarantees provided by our approximation algorithm.

关键词： DER Scheduling Discrete Complex Injection approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Distance Constrained Vehicle Routing Problem to Minimize the Total Cost 25th

Distance Constrained Vehicle Routing Problem to Minimize the...

引用

25th International Computing and Combinatorics Conference (COCOON)

作者： Yu, Wei Liu, Zhaohui Bao, Xiaoguang East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Shanghai Ocean Univ Coll Informat Technol Shanghai 201306 Peoples R China

ISBN: (纸本)9783030261764;9783030261757

Given lambda > 0, an undirected complete graph G = (V, E) with nonnegative edge-weight function obeying the triangle inequality and a depot vertex r is an element of V, a set {C-1, ... , C-k} of cycles is called a lambda-bounded r-cycle cover if V subset of boolean OR(k)(i=1) V (C-i) and each cycle C-i contains r and has a length of at most lambda. The Distance Constrained Vehicle Routing Problem with the objective of minimizing the total cost (DVRP-TC) aims to find a lambda-bounded r-cycle cover {C-1, ... , C-k} such that the sum of the total length of the cycles and gamma k is minimized, where gamma is an input indicating the assignment cost of a single cycle. For DVRP-TC on tree metric, we show a 2-approximation algorithm that is implied by the existing results and give an LP relaxation whose integrality gap has an upper bound of 5/2. In particular, when gamma = 0 we prove that this bound can be improved to 2. For the unrooted version of DVRP-TC, we devise a 5-approximation algorithm and show that a natural set-covering LP relaxation has a constant integrality gap of 25 using the rounding procedure given by Nagarajan and Ravi (2008).

关键词： Vehicle Routing Cycle cover Path cover approximation algorithm Integrality gap

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：