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

34th International Symposium on algorithms and Computation, ISAAC 2023

作者： Cohen, Tomer Kulik, Ariel Shachnai, Hadas Computer Science Department Technion Haifa Israel CISPA Helmholtz Center for Information Security Saarbrücken Germany

ISBN: (纸本)9783959772891

We study the uniform 2-dimensional vector multiple knapsack (2VMK) problem, a natural variant of multiple knapsack arising in real-world applications such as virtual machine placement. The input for 2VMK is a set of items, each associated with a 2-dimensional weight vector and a positive profit, along with m 2-dimensional bins of uniform (unit) capacity in each dimension. The goal is to find an assignment of a subset of the items to the bins, such that the total weight of items assigned to a single bin is at most one in each dimension, and the total profit is maximized. Our main result is a (1 − ln 2 − Ε)-approximation algorithm for 2VMK, for every fixed Ε > 0, 2 thus improving the best known ratio of (1 − 1e − Ε) which follows as a special case from a result of [Fleischer at al., MOR 2011]. Our algorithm relies on an adaptation of the Round&Approx framework of [Bansal et al., SICOMP 2010], originally designed for set covering problems, to maximization problems. The algorithm uses randomized rounding of a configuration-LP solution to assign items to ≈ m · ln 2 ≈ 0.693 · m of the bins, followed by a reduction to the (1-dimensional) Multiple Knapsack problem for assigning items to the remaining bins. © Tomer Cohen, Ariel Kulik, and Hadas Shachnai;licensed under Creative Commons License CC-BY 4.0.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Parameterized approximation Scheme for Feedback Vertex Set 48

Parameterized Approximation Scheme for Feedback Vertex Set

引用

48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023

作者： Jana, Satyabrata Lokshtanov, Daniel Mandal, Soumen Rai, Ashutosh Saurabh, Saket Institute of Mathematical Sciences HBNI Chennai India Department of Computer Science University of California Santa Barbara Santa BarbaraCA United States Department of Mathematics IIT Delhi New Delhi India University of Bergen Bergen Norway

ISBN: (纸本)9783959772921

Feedback Vertex Set (FVS) is one of the most studied vertex deletion problems in the field of graph algorithms. In the decision version of the problem, given a graph G and an integer k, the question is whether there exists a set S of at most k vertices in G such that G− S is acyclic. It is one of the first few problems which were shown to be NP-complete, and has been extensively studied from the viewpoint of approximation and parameterized algorithms. The best-known polynomial time approximation algorithm for FVS is a 2-factor approximation, while the best known deterministic and randomized FPT algorithms run in time O∗(3.460k) and O∗(2.7k) respectively.1 In this paper, we contribute to the newly established area of parameterized approximation, by studying FVS in this paradigm. In particular, we combine the approaches of parameterized and approximation algorithms for the study of FVS, and achieve an approximation guarantee with a factor better than 2 in randomized FPT running time, that improves over the best known parameterized algorithm for FVS. We give three simple randomized (1 + ϵ) approximation algorithms for FVS, running in times O∗(2ϵk · 2.7(1−ϵ)k), O∗ ((( 1+4ϵ )(1+ϵ) · ( 3ϵ )ϵ)k) , and O∗(4(1−ϵ)k) respectively for every ϵ ∈ (0, 1). Combining these three algorithms, we obtain a factor (1 + ϵ) approximation algorithm for FVS, which has better running time than the best-known (randomized) FPT algorithm for every ϵ ∈ (0, 1). This is the first attempt to look at a parameterized approximation of FVS to the best of our knowledge. Our algorithms are very simple, and they rely on some well-known reduction rules used for arriving at FPT algorithms for FVS. © Satyabrata Jana, Daniel Lokshtanov, Soumen Mandal, Ashutosh Rai, and Saket Saurabh

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

An Improved approximation Algorithm for the Max-3-Section Problem 31

An Improved Approximation Algorithm for the Max-3-Section Pr...

引用

31st Annual European Symposium on algorithms, ESA 2023

作者： Katzelnick, Dor Pillai, Aditya Schwartz, Roy Singh, Mohit The Henry and Marilyn Taub Faculty of Computer Science Technion Haifa Israel H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology AtlantaGA United States

ISBN: (纸本)9783959772952

We consider the Max-3-Section problem, where we are given an undirected graph G = (V,E) equipped with non-negative edge weights w : E → R+ and the goal is to find a partition of V into three equisized parts while maximizing the total weight of edges crossing between different parts. Max-3-Section is closely related to other well-studied graph partitioning problems, e.g., Max-Cut, Max-3-Cut, and Max-Bisection. We present a polynomial time algorithm achieving an approximation of 0.795, that improves upon the previous best known approximation of 0.673. The requirement of multiple parts that have equal sizes renders Max-3-Section much harder to cope with compared to, e.g., Max-Bisection. We show a new algorithm that combines the existing approach of Lassere hierarchy along with a random cut strategy that suffices to give our result. © Dor Katzelnick, Aditya Pillai, Roy Schwartz, and Mohit Singh

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Joint Uplink Power Control, Downlink Beamforming, and Mode Selection for Secrecy Cell-Free Massive MIMO With Network-Assisted Full Duplexing

引用

IEEE SYSTEMS JOURNAL 2023年第1期17卷 720-731页

作者： Xia, Xinjiang Fan, Zhenqi Luo, Wuyang Lu, An Wang, Dongming Zhao, Xinsheng You, Xiaohu Purple Mt Labs Nanjing 211111 Peoples R China Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China State Grid Elect Power Res Inst Nanjing 211100 Peoples R China

In this article, we investigate a secrecy cell-free massive multiple-input multiple-output system with network-assisted full duplexing for both noncolluding eavesdropper (Eve) and colluding Eve cases, where the access points (APs) are designed to serve downlink users and uplink users simultaneously and flexibly in the presence of Eves. To confirm the secrecy transmission, we consider the problem of jointly optimizing duplex mode selection and secrecy transceivers to maximize the overall secrecy spectral efficiency, where the information signals at APs are injected with artificial noise (AN) to prevent interception of information by Eves. Considering that downlink secure beamforming, uplink transmission power, and uplink receivers are tightly coupled in both the objective function and the constraints, we propose a two-loop strategy to solve the optimization problem. In particular, we propose a quantum-inspired tabu search algorithm to find a better duplex mode in the outer loop for each iteration. Then, for the inner loop, we propose a successive convex approximation based iterative algorithm to optimize the transceivers and AN by fixing the duplex mode selection vectors obtained from the outer loop. To address the proposed inner loop design subproblem, we resolve the subproblem by a series of nonconvex-convex approximate methods, such as the equivalent transformation and the iterative concave-convex procedure. The simulation results show that the proposed solution can achieve a higher secrecy spectral efficiency gain than the fixed-mode duplex scheme and simple greedy duplex mode selection schemes and achieve secrecy spectral efficiency performance similar to that of the optimal exhaustive search solution for both noncolluding Eve and colluding Eve cases.

关键词： Uplink Downlink Massive MIMO Transceivers Transmitting antennas Array signal processing approximation algorithms Access point (AP) artificial noise (AN) cell-free massive multiple-input multiple-output (MIMO) network-assisted full duplexing (NAFD) security spectral efficiency

来源：评论

学校读者我要写书评

暂无评论

Autonomous Recharging and Flight Mission Planning for Battery-Operated Autonomous Drones

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2023年第2期20卷 1034-1046页

作者： Alyassi, Rashid Khonji, Majid Karapetyan, Areg Chau, Sid Chi-Kin Elbassioni, Khaled Tseng, Chien-Ming Khalifa Univ Dept EECS Abu Dhabi U Arab Emirates Australian Natl Univ Coll Engn & Comp Sci Canberra ACT 2601 Australia Ubiquiti Inc Taipei 21088 Taiwan

Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design challenge is to ensure the underlying algorithms can efficiently optimize the mission objectives along with recharging operations during long-haul flights. With this in view, the present work undertakes a comprehensive study on automated tour management systems for an energy-constrained drone: (1) We construct a machine learning model that estimates the energy expenditure of typical multi-rotor drones while accounting for real-world aspects and extrinsic meteorological factors. (2) Leveraging this model, the joint program of flight mission planning and recharging optimization is formulated as a multi-criteria Asymmetric Traveling Salesman Problem (ATSP), wherein a drone seeks for the time-optimal energy-feasible tour that visits all the target sites and refuels whenever necessary. (3) We devise an efficient approximation algorithm with provable worst-case performance guarantees and implement it in a drone management system, which supports real-time flight path tracking and re-computation in dynamic environments. (4) The effectiveness and practicality of the proposed approach are validated through extensive numerical simulations as well as real-world experiments.

关键词： Drones Batteries Routing Planning Power demand Charging stations approximation algorithms Unmanned aerial vehicles flight mission planning recharging optimization power consumption modeling approximation algorithm traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

A Novel Energy Efficient Multi-Dimensional Virtual Machines Allocation and Migration at the Cloud Data Center

引用

IEEE ACCESS 2023年 11卷 107480-107495页

作者： Sharma, Neeraj Kumar Bojjagani, Sriramulu Reddy, Y. C. A. Padmanabha Vivekanandan, Manojkumar Srinivasan, Jagadeesan Maurya, Anup Kumar SRM Univ AP Sch Engn & Appl Sci SEAS Dept Comp Sci & Engn Amaravati 522240 Andhra Pradesh India BV Raju Inst Technol Dept Comp Sci & Engn Narsapur 502313 Telangana India Vellore Inst Technol Sch Comp Sci Engn & Informat Syst Dept Software & Syst Engn Vellore 632014 Tamilnadu India Goa Inst Management Goa 403505 India

Due to the rapid utilization of cloud services, the energy consumption of cloud data centres is increasing dramatically. These cloud services are provided by Virtual Machines (VMs) through the cloud data center. Therefore, energy-aware VMs allocation and migration are essential tasks in the cloud environment. This paper proposes a Branch-and-Price based energy-efficient VMs allocation algorithm and a Multi-Dimensional Virtual Machine Migration (MDVMM) algorithm at the cloud data center. The Branch-and-Price based VMs allocation algorithm reduces energy consumption and wastage of resources by selecting the optimal number of energy-efficient PMs at the cloud data center. The proposed MDVMM algorithm saves energy consumption and avoids the Service Level Agreement (SLA) violation by performing an optimal number of VMs migrations. The experimental results demonstrate that our proposed Branch-and-Price based VMs allocation with VMs migration algorithms saves more than 31% energy consumption and improves 21.7% average resource utilization over existing state-of-the-art techniques with a 95% confidence interval. The performance of the proposed approaches outperforms in terms of SLA violation, VMs migration, and Energy SLA Violation (ESV) combined metrics over existing state-of-the-art VMs allocation and migration algorithms.

关键词： Data centers Resource management Cloud computing Energy consumption Energy efficiency approximation algorithms data center virtual machine physical machine energy-aware branch-and-price SLA ESV

来源：评论

学校读者我要写书评

暂无评论

Improved Learning-Based Design Space Exploration for Approximate Instance Generation

引用

IEEE ACCESS 2023年 11卷 18291-18299页

作者： Rajput, Muhammad Awais Alyami, Sultan Ahmed, Qazi Arbab Alshahrani, Hani Asiri, Yousef Shaikh, Asadullah Quaid E Awam Univ Engn Sci & Technol Dept Artificial Intelligence Nawabshah 67450 Pakistan Najran Univ Coll Comp Sci & Informat Syst Dept Comp Sci Najran 61441 Saudi Arabia Univ Azad Jammu & Kashmir UAJ&K Dept Software Engn Muzaffarabad 13100 Pakistan Najran Univ Coll Comp Sci & Informat Syst Dept Informat Syst Najran 61441 Saudi Arabia Najran Univ Sci & Engn Res Ctr Najran 61441 Saudi Arabia

Design methodologies for approximation of medium to large-scale accelerators have largely relied on search-based design space exploration. Due to the enormously sized solution space, Artificial Intelligence (AI) based heuristic search has remained one of the most common techniques to explore cost and performance trade-offs. As a sub-class of AI techniques, Monte Carlo Tree Search (MCTS) has recently shown great potential as an intelligent stochastic search algorithm to solve computational problems with large branching factors. MCTS employs reinforced learning that combines past statistics and stochastic processes to traverse new paths in the search tree. Inspired by the success of MCTS in the games domain (AlphaGo), it has been recently applied to explore the solution space of approximate circuits. In this paper, a modified MCTS-based intelligent search technique is proposed that can handle huge search space for approximation of fairly large benchmark circuits. The proposed learning-based heuristic for MCTS directs the search towards deeper nodes in the search tree resulting in a rather asymmetric tree to efficiently utilize the search budget on the exploration of more promising nodes in the design space. The modified MCTS algorithm is based on reinforced learning where an agent uses past information to improve the overall gain. Experimental results confirm that the proposed heuristics can reach out to deeper nodes in the search tree which account for larger area savings in the context of approximate computing. The modified search algorithm enables 34.23% more area savings than the original search algorithm.

关键词： Space exploration approximation algorithms Monte Carlo methods Hardware Deep-space communications Logic gates Artificial intelligence Approximate computing artificial intelligence design space exploration intelligent search

来源：评论

学校读者我要写书评

暂无评论

Multifocus Image Fusion Based on Convolutional Simultaneous Sparse approximation 1

引用

The 4th International Conference on Data Science, Machine Learning 2022

作者： Obulesu, G. Thulasi, M. Sai Padma Kusuma, K. Bhavya, G. Naidu, N. Kesava Department of ECE Annamacharya Institute of Technology and Sciences Rajampet India

ISBN: (数字)9789819920587

ISBN: (纸本)9789819920570

Convolutional simultaneous sparse approximation algorithms are based on the alternating direction approach of multipliers with various sparsity structures. Outdoor VL photos are improved using the NIR images. The NIR images utilised in this study are shown in grayscale and can be combined with the intensity parts of the VL photos, which are typically accessible in red, green, and blue (RGB) format. Using the sparse feature maps with the same supports, we try to approximate the input signals. Utilising two multimodal NIR-VL dictionaries that have already been learned and thus suggested CSSA approach for the problem concerned. An approach for fusing NIR and VL images is based on CSSA and CDL. On the basis of the SSA model, we address the CSSA problem with various sparsity structures as well as the convolutional feature learning problem in multimodal data/signals. We assess the suggested algorithms. © 2023, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

An Efficient Approximate Expectation Propagation Detector With Block-Diagonal Neumann-Series

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2023年第3期70卷 1403-1416页

作者： Wang, Huizheng Cheng, Bingyang Tan, Xiaosi You, Xiaohu Zhang, Chuan Southeast Univ Natl Mobile Commun Res Lab LEADS Nanjing 211189 Peoples R China Southeast Univ Frontiers Sci Ctr Mobile Informat Commun & Secur Nanjing 211189 Peoples R China Purple Mt Labs Nanjing 211189 Peoples R China

Expectation propagation (EP) achieves near-optimal performance for large-scale multiple-input multiple-output (L-MIMO) detection, however, at the expense of unaffordable matrix inversions. To tackle the issue, several low-complexity EP detectors have been proposed. However, they all fail to exploit the properties of channel matrices, thus resulting in unsatisfactory performance in non-ideal scenarios. To this end, in this paper, a block-diagonal Neumann-series-based expectation propagation approximation (BD-NS-EPA) algorithm is proposed, which is applicable for both ideal uncorrelated channels and the correlated channels with multiple-antenna user equipment system. First, a block-diagonal-based Neumann iteration is employed, which skillfully exerts the main information of the channels while reducing computational cost. An adjustable sorting message updating scheme then is introduced to reduce the update of redundant nodes during iterations. Numerical results show that, for 128 & times;32 MIMO with the non-ideal channel, the proposed algorithm exhibits 0.3 dB away from the original EP when bit error-rate (BER) = 10(& minus;3), at the cost of mere 3% normalized complexity. The implementation results on SMIC 65-nm CMOS technology suggest that the proposed detector can achieve 1.252 Gbps/W and 0.275 Mbps/kGE hardware efficiency, further demonstrating that the proposed detectors can achieve a good trade-off between error-rate performance and hardware efficiency.

关键词： Detectors MIMO communication Antennas Symbols approximation algorithms Gaussian distribution Covariance matrices Large-scale MIMO expectation propagation block-diagonal matrix Neumann-series approximation VLSI

来源：评论

学校读者我要写书评

暂无评论

Relaxed Actor-Critic With Convergence Guarantees for Continuous-Time Optimal Control of Nonlinear Systems

IEEE TRANSACTIONS ON INTELLIGENT VEHICLES

引用

IEEE TRANSACTIONS ON INTELLIGENT VEHICLES 2023年第5期8卷 3299-3311页

作者： Duan, Jingliang Li, Jie Ge, Qiang Li, Shengbo Eben Bujarbaruah, Monimoy Ma, Fei Zhang, Dezhao Univ Sci & Technol Beijing Sch Mech Engn Beijing 100083 Peoples R China Tsinghua Univ Sch Vehicle & Mobil Beijing 100084 Peoples R China Univ Calif Berkeley Dept Mech Engn Berkeley CA 94720 USA Beijing Idriverplus Technol Co Ltd Beijing 100192 Peoples R China

This paper presents the Relaxed Continuous-Time Actor-critic (RCTAC) algorithm, a method for finding the nearly optimal policy for nonlinear continuous-time (CT) systems with known dynamics and infinite horizon, such as the path-tracking control of vehicles. RCTAC has several advantages over existing adaptive dynamic programming algorithms for CT systems. It does not require the "admissibility" of the initialized policy or the input-affine nature of controlled systems for convergence. Instead, given any initial policy, RCTAC can converge to an admissible, and subsequently nearly optimal policy for a general nonlinear system with a saturated controller. RCTAC consists of two phases: a warm-up phase and a generalized policy iteration phase. The warm-up phase minimizes the square of the Hamiltonian to achieve admissibility, while the generalized policy iteration phase relaxes the update termination conditions for faster convergence. The convergence and optimality of the algorithm are proven through Lyapunov analysis, and its effectiveness is demonstrated through simulations and real-world path-tracking tasks.

关键词： Heuristic algorithms Convergence Vehicle dynamics Nonlinear dynamical systems Mathematical models approximation algorithms Infinite horizon Reinforcement learning continuous-time optimal control nonlinear systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：