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

arXiv 2024年

作者： Rautenbach, Dieter Werner, Florian Institute of Optimization and Operations Research Ulm University Ulm Germany

Graph isomorphism, subgraph isomorphism, and maximum common subgraphs are classical well-investigated objects. Their (parameterized) complexity and efficiently tractable cases have been studied. In the present paper, for a given set of forests, we study maximum common induced subforests and minimum common induced superforests. We show that finding a maximum subforest is NP-hard already for two subdivided stars while finding a minimum superforest is tractable for two trees but NP-hard for three trees. For a given set of k trees, we present an efficient greedy k2 − 12 + k1 -approximation algorithm for the minimum superforest problem. Finally, we present a polynomial time approximation scheme for the maximum subforest problem for any given set of forests. Copyright © 2024, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

The Bottom-Left Algorithm for the Strip Packing Problem

arXiv

引用

arXiv 2024年

作者： Hougardy, Stefan Zondervan, Bart Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics University of Bonn Germany Faculty of Mathematics and Computer Science University of Bremen Germany

The bottom-left algorithm is a simple heuristic for the Strip Packing Problem. It places the rectangles in the given order at the lowest free position in the strip, using the left most position in case of ties. Despite its simplicity, the exact approximation ratio of the bottom-left algorithm remains unknown. We will improve the more-than-40-year-old value for the lower bound from 5/4 to 4/3 − Ε. Additionally, we will show that this lower bound holds even in the special case of squares, where the previously known lower bound was 12/11 − Ε. These lower bounds apply regardless of the ordering of the rectangles. When squares are arranged in the worst possible order, we establish a constant upper bound and a 10/3−Ε lower bound for the approximation ratio of the bottom-left algorithm. This bound also applies to some online setting and yields an almost tight result there. Finally, we show that the approximation ratio of a local search algorithm based on permuting rectangles in the ordering of the bottom-left algorithm is at least 2 and that such an algorithm may need an exponential number of improvement steps to reach a local *** Codes 68W25, 68W40, 68Q25, 90C27 © 2024, CC BY-NC-ND.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Research on Multipoint Collaborative Target Recognition and Tracking Algorithm

Research on Multipoint Collaborative Target Recognition and ...

引用

Electronic Information Engineering and Computer Science (EIECS), 2021 International Conference on

作者： Yang Zhang Guang Yang Siqi Gao School of Electronic Information Engineering Changchun University of Science and Technology Changchun China

ISBN: (数字)9798331531409

ISBN: (纸本)9798331531416

Frame differencing method can adapt well to dynamic environments with changes in lighting and complex background transformations. However, its characteristic of determining whether an object is in motion by extracting the object's contour leads to misdetection and missed detection when detecting moving objects. Meanwhile, frame difference operation also increases the calculation processing time and thus generates a higher delay. To address the mentioned issues, the article proposes a multi-point collaborative object recognition algorithm. Firstly, perform grayscale processing on the image. Secondly, it employs an improved BM3D (Block Matching 3D) algorithm for denoising. Then the image data after noise removal is identified and tracked by an improved adaptive interframe difference algorithm. Finally, a multi-point collaborative FPGA-based object recognition and tracking system is designed to validate the algorithm. Experimental results show that, compared to traditional frame differencing methods, the improved algorithm reduces latency by approximately 200 microseconds and significantly enhances the accuracy of object recognition.

关键词： Wavelet transforms Target tracking Three-dimensional displays Target recognition Noise reduction Noise Collaboration Gray-scale approximation algorithms Delays

来源：评论

学校读者我要写书评

暂无评论

Achieving Optimal Complexity Guarantees for a Class of Bilevel Convex Optimization Problems

Achieving Optimal Complexity Guarantees for a Class of Bilev...

引用

American Control Conference (ACC)

作者： Sepideh Samadi Daniel Burbano Farzad Yousefian Department of Industrial and Systems Engineering Rutgers University Piscataway NJ USA Department of Electrical and Computer Engineering Rutgers University Piscataway NJ USA

ISBN: (数字)9798350382655

ISBN: (纸本)9798350382662

We design and analyze a novel regularized accelerated proximal gradient method for a class of bilevel optimization problems where from the optimal solution set of a composite convex optimization problem, we seek to find a solution that minimizes a secondary convex objective function. When the optimal solution set of the lower-level problem admits a weak sharpness property, we significantly improve existing iteration complexity to O(E- 0.5 ) for both suboptimality and infeasibility error metrics, where ∊ > 0 denotes an arbitrary scalar. We also obtain guarantees in absence of the weak sharpness property. In addition, contrary to some existing methods that require solving the optimization problem sequentially (initially solving an optimization problem to approximate the solution of the lower-level problem followed by a second scheme), our method concurrently solves the bilevel optimization problem. To the best of our knowledge, the proposed algorithm achieves the best-known iteration complexity, which matches the optimal complexity for single-level convex optimization. Preliminary numerical experiments on a sparse linear regression problem validate the efficacy of our approach.

关键词： Measurement Gradient methods Linear regression Linear programming approximation algorithms Convex functions Complexity theory

来源：评论

学校读者我要写书评

暂无评论

Oracle Complexity Reduction for Model-Free LQR: A Stochastic Variance-Reduced Policy Gradient Approach

Oracle Complexity Reduction for Model-Free LQR: A Stochastic...

引用

American Control Conference (ACC)

作者： Leonardo F. Toso Han Wang James Anderson Department of Electrical Engineering Columbia University in the City of New York New York NY USA

ISBN: (数字)9798350382655

ISBN: (纸本)9798350382662

We investigate the problem of learning an $\epsilon$ -approximate solution for the discrete-time Linear Quadratic Regulator (LQR) problem via a Stochastic Variance-Reduced Policy Gradient (SVRPG) approach. Whilst policy gradient methods have proven to converge linearly to the optimal solution of the model-free LQR problem, the substantial requirement for two-point cost queries in gradient estimations may be intractable, particularly in applications where obtaining cost function evaluations at two distinct control input configurations is exceptionally costly. To this end, we propose an oracle-efficient approach. Our method combines both one-point and two-point estimations in a dual-loop variance-reduced algorithm. It achieves an approximate optimal solution with only $\mathcal{O}\left(\log(1/\epsilon)^{\beta}\right)$ two-point cost information for $\beta\in(0,1)$ .

关键词： Gradient methods Costs Regulators Stochastic processes Estimation Cost function approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Sum Rate Maximization for IRS-Assisted Energy Harvesting Cognitive Radio Networks

Sum Rate Maximization for IRS-Assisted Energy Harvesting Cog...

引用

World Congress on Computing and Communication Technologies (WCCCT)

作者： Lilian Chiru Kawala Guoquan Li Liu Ting Amayika Kakati School of Communications and Information Engineering Chonqqing University of Posts and Telecommunications Chongqing China

ISBN: (数字)9798331512620

ISBN: (纸本)9798331512637

Cognitive Radio (CR) technology allows secondary users (SUs) to utilize the spectrum resources of primary users (PUs) without affecting PUs’ quality of service (QoS), addressing spectrum scarcity in future wireless communication systems. Energy Harvesting (EH)-powered Cognitive Radio Networks (EH-CRNs) equip secondary base stations with EH capabilities to address spectrum scarcity and RF energy harvesting simultaneously but face challenges in optimizing spectrum and EH efficiency. In this paper, we establish an EH-CRN system model assisted by Intelligent Reflecting Surface (IRS) for better transmission QoS and formulate an optimization problem to maximize secondary networks’ achievable throughput subject to constraints on the lowest false alarm probability, SU QoS, and IRS phase shift. To solve the non-convex problem, we propose a resource allocation algorithm based on alternating optimization and divide it into three subproblems to respectively optimize the detection probability, the energy harvesting, and the achievable rate of secondary users by using semidefinite relaxation (SDR), successive convex approximation (SCA), first-order Taylor expansion, and Gaussian randomization with sequential rank-one constraint relaxation (SROCR). Simulation results demonstrate the algorithm’s convergence and improved performance compared to benchmark schemes under consistent constraints.

关键词： Uncertainty Quality of service Benchmark testing Throughput approximation algorithms Taylor series Energy harvesting Cognitive radio Optimization Convergence

来源：评论

学校读者我要写书评

暂无评论

Trapezoidal Gradient Descent for Effective Reinforcement Learning in Spiking Networks

Trapezoidal Gradient Descent for Effective Reinforcement Lea...

引用

Ubiquitous Communication (Ucom), International Conference on

作者： Yuhao Pan Xiucheng Wang Nan Cheng Qi Qiu School of Electronic Engineering Xidian University Xi'an China School of Telecommunications Engineering Xidian University Xi'an China

ISBN: (数字)9798350374216

ISBN: (纸本)9798350374223

With the rapid development of artificial intelligence technology, the field of reinforcement learning has continuously achieved breakthroughs in both theory and practice. However, traditional reinforcement learning algorithms often entail high energy consumption during interactions with the environment. Spiking Neural Network (SNN), with their low energy consumption characteristics and performance comparable to deep neural networks, have garnered widespread attention. To reduce the energy consumption of practical applications of reinforcement learning, researchers have successively proposed the Pop-SAN and MDC-SAN algorithms. Nonetheless, these algorithms use rectangular functions to approximate the spike network during the training process, resulting in low sensitivity, thus indicating room for improvement in the training effectiveness of SNN. Based on this, we propose a trapezoidal approximation gradient method to replace the spike network, which not only preserves the original stable learning state but also enhances the model's adaptability and response sensitivity under various signal dynamics. Simulation results show that the improved algorithm, using the trapezoidal approximation gradient to replace the spike network, achieves better convergence speed and performance compared to the original algorithm and demonstrates good training stability.

关键词： Training Energy consumption Technological innovation Sensitivity Heuristic algorithms Neurons Reinforcement learning approximation algorithms Stability analysis Convergence

来源：评论

学校读者我要写书评

暂无评论

Enhancing Network Robustness Through Strategic Edge Addition Based on Natural Connectivity

Enhancing Network Robustness Through Strategic Edge Addition...

引用

International Conference on Wavelet Active Media Technology and Information Processing (ICWAMTIP)

作者： Wang Simin Wang Yilin Xie Zihan Dong Qiang School of Computer Science and Engineering University of Electronic Science and Technology of China Chengdu China Laboratory of Intelligent Collaborative Computing University of Electronic Science and Technology of China Chengdu China

ISBN: (数字)9798331519254

ISBN: (纸本)9798331519261

Natural connectivity serves as a pivotal metric for evaluating network robustness, reflecting the redundancy of alternative pathways between any two nodes and being mathematically expressed as the average eigenvalue of the adjacency matrix. Despite extensive research on the natural connectivity of numerous typical networks, there has been limited exploration into strategies for enhancing this metric. This paper introduces a link addition strategy aimed at maximizing natural connectivity, specifically targeting the addition of links between high-degree nodes with long-range distances. Experimental results, conducted on both synthetic and real-world networks, demonstrate that our proposed strategy attains near-optimal natural connectivity with remarkable computational efficiency, thereby proving its viability for large-scale network applications.

关键词： Measurement Network topology Refining Redundancy Information processing Media approximation algorithms Robustness Eigenvalues and eigenfunctions Computational efficiency

来源：评论

学校读者我要写书评

暂无评论

Optimizing Plant Health with Q-Learning: A Deep Reinforcement Learning Approach

Optimizing Plant Health with Q-Learning: A Deep Reinforcemen...

引用

International Conference on Computing and Networking Technology (ICCNT)

作者： Anushka Upadhyaya Rahul Department of Software Engineering Delhi Technological University New Delhi India

ISBN: (数字)9798350370249

ISBN: (纸本)9798350370270

Optimising Plant Health with Q-Learning: A Deep Reinforcement Learning Approach” introduces a novel approach to plant care, leveraging deep reinforcement learning (DRL) algorithms, such as Q-learning, to simulate diverse plant growth scenarios. The research aims to develop a system that provides a tailored approach to determine the best-case scenario for plant species’ maximum or optimum growth or development. The system integrates a comprehensive PlantVillage dataset with approximately 54,000 plant species covering 14 significant crops. This dataset is well labeled and considered as it fulfills the set environment for our agent to produce rewards on. The research contributes significantly to environmental sustainability and ecological awareness, fostering a deeper connection between humans and the natural environment by providing AI-powered cultivation strategies.

关键词： Q-learning Data analysis Green products Crops Deep reinforcement learning approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Collaborative Rule Caching Through Pairing of P4 Switches in SDNs

Efficient Collaborative Rule Caching Through Pairing of P4 S...

引用

IEEE Conference on Global Communications (GLOBECOM)

作者： Mohammad Saberi Mahdi Dolati Ali Movaghar Tooska Dargahi Ahmad Khonsari Department of Computer Engineering Sharif University of Technology Tehran Iran Manchester Metropolitan University Manchester UK Department of Electrical and Computer Engineering University of Tehran Tehran Iran School of Computer Science Institute for Research in Fundamental Sciences Tehran Iran

ISBN: (数字)9798350351255

ISBN: (纸本)9798350351262

Software-defined networks (SDNs) provide customizable traffic control by storing numerous rules in on-chip memories with minimal access latency. However, the current on-chip memory capacity falls short of meeting the growing demands of SDN control applications. While rule eviction and aggregation strategies address this challenge at the switch level, programmable data planes enable a more flexible approach through cooperative rule caching. However, current solutions rely on computationally intensive off-the-shelf solvers to perform rule placement across the network. In this paper, we present an efficient solution for the cooperative rule caching problem. We first present the design of a resource-efficient switch capable of caching rules for its neighbors alongside a lightweight protocol for retrieving cached rules. Then, we introduce RaSe, an approximation algorithm for minimizing rule lookup latency across the network through optimized cooperation-aware rule placement. We conduct a theoretical analysis of RaSe, followed by a P4-based proof-of-concept assessment in Mininet and a large-scale numerical evaluation using real-world network topology. In comparison with existing solver-based solutions, the proposed method obtains the solution 160 times faster and improves the average rule lookup latency by about 21% compared to several algorithmic baselines.

关键词： Protocols Network topology Scalability Switches Traffic control approximation algorithms Numerical simulation System-on-chip Software defined networking Optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：