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

IEEE High Performance Extreme Computing Conference (HPEC)

作者： Du, Zhihui Zhang, Sen Bader, David A. Hu, Jingkun New Jersey Inst Technol Dept Comp Sci Nework NJ 07102 USA SUNY Coll Oneonta Dept Math Comp Sci & Stat Oneonta NY 13820 USA Worldmoney Blockchain Management Ltd Hong Kong Peoples R China

ISBN: (纸本)9781728192192

Large fault-tolerant network systems with high Quality of Service (QoS) guarantee are critical in many real world applications and entail diverse replica placement problems. In this paper, the replica placement problem in terms of minimizing the replica placement cost subject to both QoS and fault-tolerant constraints is formulated as a binary integer linear programming problem first and then relaxed as a linear programming problem. Given the optimal fractional linear programming solution, we propose a two-step rounding algorithm to obtain its integer solution. In the first step, a half rounding algorithm is used to simplify the problem. In the second step, a cheapest amortized cost rounding algorithm uses a novel metric, named amortized cost, to make locally optimal rounding decision for the remaining vertices independently. Furthermore, a conflict resolution algorithm is presented to tackle the situations when different vertices make conflicting rounding decisions. Finally, we prove that the proposed two-step rounding algorithm has a 2-approximation ratio when the additional conflict cost meets a given constraint.

关键词： Replica Placement Quality of Service Fault Tolerance rounding algorithm Approximation Ratio

来源：评论

学校读者我要写书评

暂无评论

Efficient rounding for the Noncommutative Grothendieck Inequality 13

Efficient Rounding for the Noncommutative Grothendieck Inequ...

引用

45th Annual ACM Symposium on the Theory of Computing (STOC)

作者： Naort, Assaf Regevt, Oded Vidick, Thomas NYU Courant Inst New York NY 10003 USA MIT Cambridge MA 02139 USA

ISBN: (纸本)9781450320290

The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constant-factor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem.

关键词： Grothendieck inequality rounding algorithm semidefinite programming principal component analysis

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for the covering-type k-violation linear program

引用

OPTIMIZATION LETTERS 2019年第7期13卷 1515-1521页

作者： Takazawa, Yotaro Mizuno, Shinji Kitahara, Tomonari Tokyo Inst Technol Dept Ind Engn & Econ Meguro Ku 2-12-1 Ohokayama Tokyo 1528552 Japan

We study the covering-type k-violation linear program where at most k of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we present a simple (k + 1)approximation algorithm using a natural LP relaxation. We also show that the integrality gap of the LP relaxation is k + 1. This implies we can not get better approximation algorithms when we use the LP-relaxation as a lower bound of the optimal value.

关键词： Approximation algorithms Mixed integer program k-violation linear program Linear relaxation rounding algorithm

来源：评论

学校读者我要写书评

暂无评论

On linear and semidefinite programming relaxations for hypergraph matching

引用

MATHEMATICAL PROGRAMMING 2012年第1-2期135卷 123-148页

作者： Chan, Yuk Hei Lau, Lap Chi Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are the following: We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof of a result of Furedi, Kahn and Seymour, showing that the integrality gap is exactly for k-uniform hypergraphs, and is exactly k - 1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the fractional local ratio method, showing a new way to round linear programming solutions for packing problems. We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k - 2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most for k-uniform hypergraphs. The construction uses a result in extremal combinatorics. We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovasz -function provides an SDP relaxation with integrality gap at most . The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming

关键词： Linear programming Semidefinite programming Hypergraph matching rounding algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimization of Partially Offloading Mobile User Tasks to Fog Computing Networks

引用

IEEE SYSTEMS JOURNAL 2023年第3期17卷 4978-4989页

作者： Hu, Chia-Cheng Yango Univ Coll Artificial Intelligence Fuzhou 350015 Peoples R China

Due to the limited computing power and energy resources of lightweight mobile user devices, offloading their tasks to fog nodes is a promising solution. Partial offloading is a more efficient way to allocate and use the whole system's resources than binary offloading. In this article, three algorithms are proposed to address the three issues of partial offloading in fog computing. Different from the strategy of minimizing task delay or minimizing power consumption adopted in the existing works of literature, the first algorithm considers both of these two strategies concurrently. The second is proposed to maximize task admission under the constraints of the user device power and system resource. The third is proposed to expand the system resource with the least cost to improve the admission when the system resource is insufficient. The above three are non-deterministic polynomial-time (NP)-hard problems, which will be solved by adopting the strategy of rounding algorithm in this article. Through theoretical analysis, a small gap exists between the solved solution and the optimal one of the problem. Additionally, a large number of simulations will be carried out to verify that their performance is better than that of the recent related works and close to the best performance.

关键词： Task analysis Energy consumption Optimization Delays Performance evaluation Edge computing Costs Fog computing (FC) partial task offloading Index Terms rounding algorithm

来源：评论

学校读者我要写书评

暂无评论

How to Round Any CSP

How to Round Any CSP

引用

50th Annual IEEE Symposium on Foundations of Computer Science

作者： Raghavendra, Prasad Steurer, David Microsoft Res New England Cambridge MA 02142 USA Princeton Univ Dept Comp Sci Princeton NJ 08540 USA

ISBN: (纸本)9780769538501

A large number of interesting combinatorial optimization problems like MAX CUT, MAX k-SAT, and UNIQUE GAMES fall under the class of constraint satisfaction problems (CSPs). Recent work [32] by one of the authors identifies a semidefinite programming (SDP) relaxation that yields the optimal approximation ratio for every CSP, under the Unique Games Conjecture (UGC). Very recently [33], the authors also showed unconditionally that the integrality gap of this basic SDP relaxation cannot be reduced by adding large classes of valid inequalities (e.g., in the fashion of Sherali-Adams LP hierarchies). In this work, we present an efficient rounding scheme that achieves the integrality gap of this basic SDP relaxation for every CSP (and by [33] it also achieves the gap of much stronger SDP relaxations). The SDP relaxation we consider is stronger or equivalent to any relaxation used in literature to approximate CSPs. Thus, irrespective of the truth of the UGC, our work yields an efficient generic algorithm that for every CSP, achieves an approximation at least as good as the best known algorithm in literature. The rounding algorithm in this paper can be summarized succinctly as follows: Reduce the dimension of SDP solution by random projection, discretize the projected vectors, and solve the resulting CSP instance by brute force! Even the proof is simple in that it avoids the use of the machinery from unique games reductions such as dictatorship tests, Fourier analysis or the invariance principle. A common theme of this paper and the subsequent paper [33] is a robustness lemma for SDP relaxations which asserts that approximately feasible solutions can be made feasible by "smoothing" without changing the objective value significantly.

关键词： semidefinite programming approximation algorithms rounding algorithm integrality gap dimension reduction constraint satisfaction problem

来源：评论

学校读者我要写书评

暂无评论

How to square floats accurately and efficiently on the ST231 integer processor

How to square floats accurately and efficiently on the ST231...

引用

20th IEEE Symposium on Computer Arithmetic (ARITH)

作者： Jeannerod, Claude-Pierre Jourdan-Lu, Jingyan Monat, Christophe Revy, Guillaume Univ Lyon INRIA Lab LIP CNRSENS LyonINRIAUCBL Lyon France STMicroelect Compilat Expertise Ctr Grenoble France Univ Perpignan LIRMM CNRS UM2 DALI Res Team Perpignan France

ISBN: (纸本)9780769543185

We consider the problem of computing IEEE floating-point squares by means of integer arithmetic. We show how to exploit the specific properties of squaring in order to design and implement algorithms that have much lower latency than those for general multiplication, while still guaranteeing correct rounding. Our algorithms are parameterized by the floating-point format, aim at high instruction-level parallelism (ILP) exposure, and cover all rounding modes. We show further that their C implementation for the binary32 format yields efficient codes for targets like the ST231 VLIW integer processor from STMicroelectronics, with a latency at least 1.75x smaller than that of general multiplication in the same context.

关键词： algorithm design and analysis C implementation C language Encoding IEEE floating-point squares Libraries Parallel processing ST231 VLIW integer processor STMicroelectronics Signal processing algorithms Software VLIW binary32 format floating point arithmetic high instruction-level parallelism exposure integer arithmetics microprocessor chips rounding algorithm word length 32 bit

来源：评论

学校读者我要写书评

暂无评论

Service caching and user association in cache enabled multi-UAV assisted MEN for latency-sensitive applications

引用

COMPUTERS & ELECTRICAL ENGINEERING 2024年第PartB期119卷

作者： Somesula, Manoj Kumar Raju, Mekala Ratna Dorsala, Mallikarjun Reddy Brahma, Banalaxmi Mothku, Sai Krishna Dr BR Ambedkar Natl Inst Technol Jalandhar Dept Comp Sci & Engn Jalandhar 144008 Punjab India Natl Inst Technol Dept Comp Sci & Engn Tiruchirappalli 620015 India Indian Inst Informat Technol Sri City Dept Comp Sci & Engn Chittoor 517646 Andhra Pradesh India SRM Univ AP Dept Comp Sci & Engn Amaravati 522502 Andhra Pradesh India

The evolution of 5G (Fifth Generation) and B5G (Beyond 5G) wireless networks and edge IoT (Internet of Things) devices generates an enormous volume of data. The growth of mobile applications, such as augmented reality, virtual reality, network gaming, and self-driving cars, has increased demand for computation-intensive and latency-critical applications. However, these applications require high computation power and low communication latency, which hinders the large-scale adoption of these technologies in IoT devices due to their inherent low computation and low energy capabilities. MEC (mobile edge computing) is a prominent solution that improves the quality of service by offloading the services near the users. Besides, in emergencies where network failure exists due to natural calamities, UAVs (Unmanned Aerial Vehicles) can be positioned to reinstate the networking ability by serving as flying base stations and edge servers for mobile edge networks. This article explores computation service caching in a multi-unmanned aerial vehicle-assisted MEC system. The limited resources at the UAV node induce added problems of assigning the existing restricted edge resources to satisfy the user requests and the associate of users to utilize the finite resources effectively. To address the above mentioned problems, we formulate the service caching and user association problem by placing the diversified latency-critical services to maximize the time utility with the deadline and resource constraints. The problem is formulated as an integer linear programming (ILP) problem for service placement in mobile edge networks. An approximation algorithm based on the rounding technique is designed to solve the formulated ILP problem. Moreover, a genetic algorithm is designed to address the larger instance of the problem. Simulation results indicate that the proposed service placement schemes considerably enhance the cache hit ratio, load on the cloud and time utility performance compared

关键词： Beyond 5G networks UAVs Autonomous applications rounding algorithm Heuristic algorithm Service placement and user association

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：