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

arXiv 2024年

作者： Bamas, Étienne Morell, Sarah Rohwedder, Lars ETH AI Center Switzerland TU Berlin Germany Maastricht University Netherlands

We consider the problem of allocating indivisible resources to players so as to maximize the minimum total value any player receives. This problem is sometimes dubbed the Santa Claus problem and its different variants have been subject to extensive research towards approximation algorithms over the past two decades. In the case where each player has a potentially different additive valuation function, Chakrabarty, Chuzhoy, and Khanna [FOCS’09] gave an O(nΕ)-approximation algorithm with polynomial running time for any constant Ε > 0 and a polylogarithmic approximation algorithm in quasi-polynomial time. We show that the same can be achieved for monotone submodular valuation functions, improving over the previously best algorithm due to Goemans, Harvey, Iwata, and Mirrokni [SODA’09], which has an approximation ratio of more than √n. Our result builds up on a sophisticated LP relaxation, which has a recursive block structure that allows us to solve it despite having exponentially many variables and constraints. © 2024, CC0.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Non-convergence of Adam and other adaptive stochastic gradient descent optimization methods for non-vanishing learning rates

arXiv

引用

arXiv 2024年

作者： Dereich, Steffen Graeber, Robin Jentzen, Arnulf Institute for Mathematical Stochastics Faculty of Mathematics and Computer Science University of Münster Germany School of Data Science The Chinese University of Hong Kong CUHK-Shenzhen Shenzhen China School of Data Science Shenzhen Research Institute of Big Data The Chinese University of Hong Kong CUHK-Shenzhen Shenzhen China Institute for Analysis and Numerics Faculty of Mathematics and Computer Science University of Münster Germany

MSC Codes 60J22 (Primary), 65K10, 60J20, 65C40 (Secondary)Deep learning (DL) approximation algorithms – typically consisting of a class of deep artificial neural networks (DNNs) trained by a stochastic gradient descent (SGD) optimization method – are nowadays the key ingredients in many artificial intelligence (AI) systems and have revolutionized our ways of working and living in modern societies. For example, SGD methods are used to train powerful large language models (LLMs) such as versions of ChatGPT and Gemini, SGD methods are employed to create successful generative AI based text-to-image creation models such as Midjourney, DALL-E, and Stable Diffusion, but SGD methods are also used to train DNNs to approximately solve scientific models such as partial differential equation (PDE) models from physics and biology and optimal control and stopping problems from engineering. It is known that the plain vanilla standard SGD method fails to converge even in the situation of several convex optimization problems if the learning rates are bounded away from zero. However, in many practical relevant training scenarios, often not the plain vanilla standard SGD method but instead adaptive SGD methods such as the RMSprop and the Adam optimizers, in which the learning rates are modified adaptively during the training process, are employed. This naturally rises the question whether such adaptive optimizers, in which the learning rates are modified adaptively during the training process, do converge in the situation of non-vanishing learning rates. In this work we answer this question negatively by proving that adaptive SGD methods such as the popular Adam optimizer fail to converge to any possible random limit point if the learning rates are asymptotically bounded away from zero. In our proof of this non-convergence result we establish suitable pathwise a priori bounds for a class of accelerated and adaptive SGD methods, which are also of independent interest. Copyright © 2024,

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

DRL-Based Joint UAV Trajectory, Nest Scheduling and Resource Optimization for Multi-UAV Aided Power Inspection System

DRL-Based Joint UAV Trajectory, Nest Scheduling and Resource...

引用

International Conference on Computer and Communications (ICCC)

作者： Xuan Luo Yunfei Gao Rongtao Liao Bingyao Hu Ronghao Yang Information & Communication Branch State Grid Hubei Electric Power Company Wuhan China School of Electronic Information Wuhan University Wuhan China

ISBN: (数字)9798331507077

ISBN: (纸本)9798331507084

Unmanned aerial vehicle (UAV)-aided inspection system is considered a promising technology due to the high mobility and real-time monitoring capabilities. In this paper, we consider a multi-UAV aided power inspection system with no-fly zones (NFZs), where a set of UAVs complete capturing images/video tasks near the inspection points. In particular, the mobile nests are scheduled to recharge the UAV when its battery falls below a certain threshold. The goal of this paper is to minimize the total inspection time of the system by jointly optimizing the multi-UAV inspection tasks, UAV trajectories, and mobile nest scheduling. On the one hand, as the number of inspection points $M$ increases, the algorithm's complexity grows factorially, i.e., $\mathcal{O}(M-1)!$ . In addition, the formulated problem is a multivariable coupled non-convex problem, making it difficult to solve using traditional methods such as successive convex approximation or interior-point methods. To address these challenges, we first use the Kmeans++ algorithm to allocate the total tasks to each UAV, reducing the complexity of subsequent trajectory optimization. Then, for each UAV, we design its inspection trajectory based on an modified multi-step dueling double deep Q learning network (MSD-DDQN) algorithm and schedule the mobile nests for UAV recharging utilizing the A* algorithm. Finally, simulations validate the effectiveness of the proposed method. Compared to the baselines, the proposed approach accelerates the algorithm's convergence speed and reduces task completion time by nearly 37%.

关键词： Schedules Inspection Autonomous aerial vehicles approximation algorithms Scheduling Real-time systems Complexity theory Resource management Trajectory optimization Convergence

来源：评论

学校读者我要写书评

暂无评论

Spanners in Hypergraphs

Spanners in Hypergraphs

引用

IEEE International Conference on High Performance Computing Workshops (HiPCW)

作者： Maulein Pathak Yogish Sabharwal Neelima Gupta Department of Computer Science University of Delhi India Keshav Mahavidyalaya University of Delhi India IBM Research India India

ISBN: (数字)9798331509118

ISBN: (纸本)9798331509125

In this work, we explore parallel construction of spanners in hypergraphs. Spanners include all vertices and a subset of edges while ensuring shortest distances within an allowable stretch, making them crucial for efficiently approximating graph structures. We build on the state-of-the-art algorithm for parallel graphs spanners and extend it for hypergraphs focusing on optimizing the size without compromising stretch. We propose techniques to address memory and performance challenges when dealing with hypergraphs.

关键词： High performance computing Conferences Focusing approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

IUS-MAAC: Multi-Agent Attention-Critic for Task Offloading in Integrated User-Server Mobile Edge Computing

IUS-MAAC: Multi-Agent Attention-Critic for Task Offloading i...

引用

Chinese Automation Congress (CAC)

作者： Liang Zhu Shanxin Zhang Linbo Xie School of Internet of Things Engineering Jiangnan University Jiangsu China

ISBN: (数字)9798350368604

ISBN: (纸本)9798350368611

In recent years, the rapid development of computation-intensive mobile applications has posed significant challenges to the computational capabilities of user devices. In response to these challenges, Mobile Edge Computing (MEC), as an emerging technology, effectively alleviates the computational pressure on user devices. Task offloading, as the core mechanism of MEC, has become a focal point in current research. Deep Reinforcement Learning (DRL) has demonstrated its unique advantages in handling task offloading. However, current DRL-based task offloading methods primarily focus on the user level, considering factors such as limited battery life and computing capacity, thereby neglecting server performance. These methods often assume that servers have sufficient computational power and storage resources. Additionally, traditional DRL performs well in handling discrete or continuous actions but still faces challenges when dealing with hybrid action spaces. Based on these, the paper proposes a novel Integrated User-Server Multi-Agent Attention-Critic (IUS-MAAC) algorithm for MEC task offloading. This takes into account various constraints during the task offloading process and demonstrates better performance in handling hybrid spaces compared to existing Multi-Agent Deep Deterministic Policy Gradient (MADDPG) and heuristic algorithms. Based on our verification, the results show that the proposed algorithm has better convergence and improves the overall reward value by approximately 9.3% compared to other state-of-the-art algorithms.

关键词： Multi-access edge computing Automation Heuristic algorithms approximation algorithms Deep reinforcement learning Mobile applications Batteries Servers Faces Convergence

来源：评论

学校读者我要写书评

暂无评论

Inter-Satellite Routing algorithms for Dual-Layer Low Earth Orbit Satellite Internet

Inter-Satellite Routing Algorithms for Dual-Layer Low Earth ...

引用

IEEE International Conference on Communication and Information Systems (ICCIS)

作者： Pao Cheng Ping Du Yueyue Zhang Mingji Dong Yu Liang Yu Zhu Shanghai Key Laboratory of Satellite Network Shanghai Satellite Network Research Institute Co. Ltd. Shanghai China School of Information Science and Technology Fudan University Shanghai China

ISBN: (数字)9798331531171

ISBN: (纸本)9798331531188

In recent years, low-cost low Earth orbit (LEO) satellites provide shorter-latency and higher-throughput services when compared to the medium Earth orbit (MEO) and geostationary Earth orbit (GEO) satellites. However, existing research on multi-layer satellite constellations and inter-layer routing typically focuses on larger-span constellations and routing among LEO/MEO/GEO. Research on the multi-layer LEO satellite networks is currently in its early stages. Existing routing algorithms designed so far have not fully leveraged the advantages of cross-layer links. Therefore, this paper proposes a method for establishing inter-layer links and rules for a dual-layer LEO satellite network, along with a routing algorithm for such a dual-layer constellation. Firstly, a uniform distribution duallayer constellation configuration for LEO satellites is constructed, selecting the cross-layer linking satellites in LEOs. Secondly, to meet the requirement for long-term stable connections, a method for rapidly switching inter-layer links based on the periodic relative motion of satellites between layers is proposed, ensuring continuous and reliable transmission of inter-layer links within the satellite network. Furthermore, based on the rules for establishing inter-layer links and the dynamic relationships within the satellite network, time slot information for the dual-layer satellite network is established. Utilizing the Dijkstra’s algorithm, the shortest transmission path from source to destination nodes in the dual-layer satellite network model is computed to determine the effective routing within the satellite network. Finally, a dual-layer constellation simulation model is built based on the parameters of the Kuiper constellation, and simulation experiments are conducted. Simulation results demonstrate that the dual-layer constellation routing algorithm (DCRA) reduces the round trip time (RTT) by 15.3%. At distance of 14,000 km between the source and the destination nodes, th

关键词： Cross layer design Satellite constellations Satellites Heuristic algorithms Computational modeling Low earth orbit satellites Switches Routing approximation algorithms Planetary orbits

来源：评论

学校读者我要写书评

暂无评论

A Layerwise-Multi-Angle Approach to Fine-Tuning the Quantum Approximate Optimization Algorithm

A Layerwise-Multi-Angle Approach to Fine-Tuning the Quantum ...

引用

International Joint Conference on Neural Networks (IJCNN)

作者： Leonardo Lavagna Andrea Ceschini Antonello Rosato Massimo Panella Department of Information Engineering Electronics and Telecommunications (DIET) University of Rome "La Sapienza" Rome Italy

ISBN: (数字)9798350359312

ISBN: (纸本)9798350359329

This paper introduces a novel variational quantum algorithm built upon the established Quantum Approximate Optimization Algorithm also known as QAOA. Since the known parameter fixing strategy imposes constraints on QAOA to enhance tractability at the cost of some expressive power, the proposed layerwise approach integrates it with the existing Multi-Angle QAOA technique, which is characterized in turn by height-ened expressiveness through an increased number of parameters, albeit with increased optimization challenges. Consequently, the proposed layerwise-Multi-Angle QAOA combines the strengths of one variant with the limitations of the other, striking a balance in algorithmic design. The effectiveness of the proposed algorithm is assessed through experimental evaluations on the Maximum Cut problem. This study reveals promising results in heuristic predictions, with robustness both in terms of approximation ratio and optimization capabilities.

关键词： Costs Sensitivity Quantum algorithm approximation algorithms Prediction algorithms Robustness Quantum circuit

来源：评论

学校读者我要写书评

暂无评论

Joint Trajectory and Resource Optimization for Multi-UAV Cooperative Computation

Joint Trajectory and Resource Optimization for Multi-UAV Coo...

引用

IEEE International Conference on Communications Workshops, ICC

作者： Wenlong Xu Tiankui Zhang Xidong Mu Yuanwei Liu Yapeng Wang TianYi Shi School of Information and Communication Engineering Beijing University of Posts and Telecommunications Beijing China School of Faculty of Applied Sciences Macao Polytechnic University Macao China School of Electronic Engineering and Computer Science Queen Mary University of London London U.K.

ISBN: (数字)9798350304053

ISBN: (纸本)9798350304060

In the multiple unmanned aerial vehicle (UAV) mobile edge computing (MEC) systems, the cooperative computation among multiple UAVs can improve the overall computation service capability. Multi-UAV MEC systems can meet the quality of service requirements for computation intensive applications of ground terminals (GTs) in complex field environments, emergency disaster relief and other special scenarios. In this paper, a multi-UAV cooperative computation framework is proposed while taking the GT movement and random arrival of computation tasks into consideration. A long-term optimization problem is formulated for the joint optimization of UAV trajectory and resource allocation, subject to minimizing the total GT computation task completion time and the total system energy consumption. To solve this problem, a joint multiple time-scale optimization algorithm is proposed. In particular, the optimization problem is decomposed into a long time-scale multi-UAV trajectory planning subproblem and a short time-scale resource allocation subproblem. The proximal policy optimization algorithm is invoked to solve the long time-scale subproblem. The greedy algorithm and the successive convex approximation (SCA) method are employed to solve the short time-scale subproblem. Simulation results show that the proposed algorithm can quickly adapt to different degrees of environmental dynamics and outperforms the benchmark algorithm for different task requirements and available resources.

关键词： Heuristic algorithms Simulation Conferences Benchmark testing Autonomous aerial vehicles approximation algorithms Trajectory

来源：评论

学校读者我要写书评

暂无评论

Flexible Association and Placement for Open-RAN

Flexible Association and Placement for Open-RAN

引用

IEEE Conference on Computer Communications Workshops, INFOCOM Wksps

作者： Hiba Hojeij Guilherme Iecker Ricardo Mahdi Sharara Sahar Hoteit Véronique Vèque Stefano Secci CNRS CentraleSupélec Laboratoire des Signaux et Systèmes (L2S) Université Paris-Saclay Gif-sur-Yvette France IRIT/Toulouse INP University of Toulouse France Innovation Division Orange Paris France CEDRIC CNAM France

ISBN: (数字)9798350384475

ISBN: (纸本)9798350384482

In modern Open RAN architectures, the classic gNB radio protocol stack is disaggregated and implemented in different virtualized components, the Centralized Unit (CU), the Distributed Unit (DU), and the Radio Unit (RU). Each of these units is deployed throughout the cloud-enabled RAN infrastructure in order to achieve users' required Quality of Service (QoS). Within this framework, our study is dedicated to maximizing the admission of User Equipments (UEs) into the system while ensuring their specific QoS needs. We focus on two primary tasks: (i) establishing an association between UEs and RUs and (ii) placing CUs and DUs across the network's cloud hosts. We initially address these tasks by formulating the joint association-placement optimization problem, subject to the system's available resources and QoS-related constraints. Although it is an NP-Hard problem, we discuss how we can frame it into an Integer Linear Programming (ILP) model. Then, we propose an approximation algorithm based on the decomposition of the original ILP model. We show through exhaustive simulations that our proposed ILP model provides higher admissibility levels than other baseline models. Moreover, it significantly minimizes the deployment costs and increases the overall fairness. Finally, we remark that our decomposition algorithm presents a short optimality gap in practice, with up to 6% less admissions, while reducing the solution time by up to 98%.

关键词： Cloud computing Costs Protocols Optimization models Quality of service Open RAN approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Calculation of Electromagnetic Scattering Problem with Multiple Excitations by Sherman-Morrison-Woodbury Formula

Efficient Calculation of Electromagnetic Scattering Problem ...

引用

International Symposium on Antennas, Propagation and EM Theory (ISAPE)

作者： Yuting Shen Runze Liu Jianchang Cai Yang Bao College of Electronic and Optical Engineering & College of Flexible Electronics (Future Technology)) Nanjing University of Posts and Telecommunications Nanjing Jiangsu China

ISBN: (数字)9798350353129

ISBN: (纸本)9798350353136

In this article, the Sherman-Morrison-Woodbury (SMW) formula is applied to accelerate the direct solution of electromagnetic scattering problem with multiple excitations by electric field integral equation (EFIE). To reduce the calculation burden in method of moments (MoM), the dense discretized impedance matrix is transformed into several diagonal matrix blocks via the SMW formula. The low rank matrices are compressed by Lagrange interpolations. The adaptive cross approximation algorithm (ACA) is applied to reduce the storage costs for multiple right-hand sides (RHS) matrix, which can solve the monostatic radar cross section (RCS) over a wide angular band efficiently. The numerical results demonstrate both the effectiveness and accuracy of the proposed method.

关键词： Interpolation Radar cross-sections Accuracy Electromagnetic scattering Integral equations approximation algorithms Radar antennas Impedance Electric fields Method of moments

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：