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

17th International Conference on Combinatorial Optimization and Applications, COCOA 2024

作者： Zhang, Peng School of Software Shandong University Jinan250101 China

ISBN: (纸本)9789819644445

Labeled graph is a graph with labels defined on edges. Given a labeled graph G=(V,E) with label set L={1,2,⋯,q}, a source s∈V and a sink t∈V, the Labels-t Cut problem asks to find a minimum size label subset L′⊆L such that the removal of all edges from G with labels in L′ disconnects s and t. This problem is NP-hard. The current best approximation ratio of Label s-t Cut is O(n2/3OPT1/3), where OPT is the size of an optimal solution to the problem. This ratio is achieved by a simple purely combinatorial two-phase approximation algorithm. In this paper, we give a new but short (maybe the shortest) proof for the two-phase approximation algorithm. We also perform experiments for the algorithm. Experimental results show that the two-phase approximation algorithm has actually very good practical performance in random graphs. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Sum Rate and User Fairness of STAR-RIS Aided Communications

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2025年第5期14卷 1306-1310页

作者： Li, Haochen Mu, Xidong Liu, Yuanwei Chen, Yue Pan, Zhiwen Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China Queens Univ Ctr Wireless Innovat Belfast BT7 1NN North Ireland Univ Hong Kong Dept Elect & Elect Engn Hong Kong Peoples R China Queen Mary Univ London Sch Elect Engn & Comp Sci London E1 4NS England

A simultaneously transmitting and reflecting reconfigurable intelligent surface (STAR-RIS) aided communication system is investigated. A robust joint beamforming design problem under the imperfect channel state information (CSI) is formulated to maximize the weighted sum of the Jain's fairness index and the normalized system sum rate. To solve this non-convex problem, an alternating optimization (AO) algorithm is proposed, which leverages the S-Procedure, successive convex approximation (SCA), and semidefinite relaxation (SDR). Simulation results demonstrate that with proposed algorithm: 1) various trade-offs between sum rate and user fairness can be achieved;2) a larger trade-off region can be achieved by adopting STAR-RIS compared to conventional RIS;and 3) the performance degradation caused by imperfect CSI is less than 7% with our proposed robust beamforming approach.

关键词： Array signal processing Optimization Indexes System performance Stars Minimax techniques approximation algorithms Reconfigurable intelligent surfaces MIMO Lower bound Simultaneously transmitting and reflecting reconfigurable intelligent surface robust beamforming fairness

来源：评论

学校读者我要写书评

暂无评论

Performance Analysis of a 2D-MUSIC Algorithm for Parametric Near-Field Channel Estimation

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2025年第5期14卷 1496-1500页

作者： Gurgunoglu, Doga Kosasih, Alva Ramezani, Parisa Demir, Ozlem Tugfe Bjornson, Emil Fodor, Gabor KTH Royal Inst Technol Sch Elect Engn & Comp Sci S-10044 Stockholm Sweden TOBB ETU Dept Elect Elect Engn TR-06560 Ankara Turkiye Ericsson Res AB Wireless Access Networks SE-16480 Stockholm Sweden

In this letter, we address parametric channel estimation in a multi-user multiple-input multiple-output system within the radiative near-field of the base station array with aperture antennas. We investigate a two-dimensional multiple signal classification algorithm (2D-MUSIC) to estimate both the range and the azimuth angles of arrival for the users' channels, utilizing parametric radiative near-field channel models. We analyze the performance of the algorithm by deriving the Cram & eacute;r-Rao bound (CRB) for parametric estimation, and its effectiveness is compared against the least squares estimator, which is a non-parametric estimator. Numerical results indicate that the 2D-MUSIC algorithm outperforms the least squares estimator. Furthermore, the results demonstrate that the performance of 2D-MUSIC achieves the parametric channel estimation CRB, which shows that the algorithm is asymptotically consistent.

关键词： Channel estimation Antennas Vectors Multiple signal classification Aperture antennas Parametric statistics Lower bound Covariance matrices Azimuth approximation algorithms Radiative near-field aperture antennas MUSIC channel estimation Cram & eacute r-Rao lower bound

来源：评论

学校读者我要写书评

暂无评论

Bioinspired Quantum Oracle Circuits for Biomolecular Solutions of the Maximum Cut Problem

IEEE Transactions on Nanobioscience

引用

IEEE Transactions on Nanobioscience 2024年第3期23卷 499-506页

作者： Chang, Weng-Long Wong, Renata Chen, Yu-Hao Chung, Wen-Yu Chen, Ju-Chin Vasilakos, Athanasios V. National Kaohsiung University of Science and Technology Department of Computer Science and Information Engineering Kaohsiung City Taiwan National Taiwan University Physics Division National Center for Theoretical Sciences Taipei10617 Taiwan Chang Gung University Department of Artificial Intelligence Taoyuan33302 Taiwan National Taiwan University Department of Physics Taipei10617 Taiwan Grimstad4630 Norway

Given an undirected, unweighted graph with n vertices and m edges, the maximum cut problem is to find a partition of the n vertices into disjoint subsets V1 and V2 such that the number of edges between them is as large as possible. Classically, it is an NP-complete problem, which has potential applications ranging from circuit layout design, statistical physics, computer vision, machine learning and network science to clustering. In this paper, we propose a biomolecular and a quantum algorithm to solve the maximum cut problem for any graph G. The quantum algorithm is inspired by the biomolecular algorithm and has a quadratic speedup over its classical counterparts, where the temporal and spatial complexities are reduced to, respectively, O √ 2n/r ) and O (m2 ). With respect to oracle-related quantum algorithms for NP-complete problems, we identify our algorithm as optimal. Furthermore, to justify the feasibility of the proposed algorithm, we successfully solve a typical maximum cut problem for a graph with three vertices and two edges by carrying out experiments on IBM's quantum simulator. © 2002-2011 IEEE.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A mixed approximation algorithm for matching preclusion number in bipartite graphs

A mixed approximation algorithm for matching preclusion numb...

引用

2024 International Conference on Computer Application and Information Security, ICCAIS 2024

作者： Song, Shuyi Li, Chengjian Chu, Haokun Chen, Zhibin Faculty of Science Kunming University of Science and Technology Kunming China

ISBN: (纸本)9781510689312

The matching preclusion problem, originating from graph theory, is widely applied in various areas such as network reliability analysis and distributed system design. Through the examination of network behavior under edge failures, this paper delivers essential theoretical foundations for advancing reliability design and optimization in diverse fields. The matching preclusion number of a graph G = (V, E), denoted by mp(G), is the fewest edges E ' ⊆ E that must be removed to completely disrupt any perfect matching within the graph. Given a bipartite graph having perfect matchings, this paper considers how to find a minimum edge set whose deletion results a graph without any perfect matching. Due to the NP-hardness of the problem, we propose a mixed approximation algorithm for solving it. Our algorithm is actually a series of algorithms combined in which each of the algorithms solves a kind of bipartite graph with certain properties. To our best knowledge, our algorithm strengthens the previous best result with respect to approximation algorithms for bipartite graphs with perfect matchings. © The Authors.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Reward Maximization for Disaster Zone Monitoring with Heterogeneous UAVs

引用

IEEE/ACM Transactions on Networking 2024年第1期32卷 890-903页

作者： Xu, Wenzheng Wang, Chengxi Xie, Hongbin Liang, Weifa Dai, Haipeng Xu, Zichuan Wang, Ziming Guo, Bing Das, Sajal K. Sichuan University College of Computer Science Chengdu610065 China City University of Hong Kong Department of Computer Science Hong Kong Hong Kong Nanjing University Department of Computer Science and Technology Nanjing210023 China Dalian University of Technology School of Software Dalian116024 China Sichuan University Key Laboratory of Birth Defects and Related Maternal and Child Diseases West China Second Hospital College of Computer Science Chengdu610066 China Missouri University of Science and Technology Department of Computer Science RollaMO65409 United States

In this paper, we study the deployment of K heterogeneous UAVs to monitor Points of Interest (PoIs) in a disaster zone, where a PoI may represent a school building or an office building, in which people are trapped. A UAV can take images/videos of PoIs and send its collected information back to a nearby rescue station for decision-making. Unlike most existing studies that focused on only homogeneous UAVs, we here study the scheduling of K heterogeneous UAVs, where different UAVs have different energy capacities and functionalities that lead to different monitoring qualities (monitoring rewards) of each PoI. For example, one type of UAVs can take only visual images while the other type of UAVs can take both visual and thermal infrared images. In this paper, we investigate a problem of scheduling K heterogeneous UAVs to monitor PoIs so that the sum of monitoring rewards received by all UAVs is maximized, subject to energy capacity on each UAV. We propose the very first 13 -approximation algorithm for this scheduling problem. We also evaluate the performance of the proposed algorithm, using real parameters of commercial UAVs. Experimental results show that the performance of the proposed algorithm is promising, which is improved by 25%, compared with existing algorithms. © 1993-2012 IEEE.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A Cutting Plane-Based Distributed Algorithm for Non-Smooth Optimisation With Coupling Constraints

引用

IEEE CONTROL SYSTEMS LETTERS 2024年 8卷 1223-1228页

作者： Zhong, Tianyi Angeli, David Imperial Coll London Dept Elect & Elect Engn London SW7 2AZ England Univ Florence Dept Informat Engn I-50121 Florence Italy

In this letter, we study a general setup for constrained convex optimisation over time-varying networks. We propose a distributed algorithm, based on the cutting plane method, to address non-smooth optimisation challenges. Cutting plane-based approaches require constraint consensus which is structurally different from established consensus schemes. We bridge this gap by linking the cutting plane-based algorithm with a dynamic average tracking scheme. The distributed cutting plane algorithm is presented and its convergence is analysed. Its performance is investigated through a numerical example.

关键词： Optimization Heuristic algorithms approximation algorithms Linear approximation Estimation Distributed algorithms Couplings Cutting plane non-smooth optimisation dynamic average tracking distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient RRH Activation Management for 5G V2X

引用

IEEE Transactions on Mobile Computing 2024年第2期23卷 1215-1229页

作者： Ke, Jing-Wen Hwang, Ren-Hung Wang, Chih-Yu Kuo, Jian-Jhih Chen, Wei-Yu National Chung Cheng University Department of Computer Science Information Engineering Chiayi60102 Taiwan National Yang Ming Chiao Tung University College of Artificial Intelligence Tainan71150 Taiwan Taipei115 Taiwan

Vehicle-to-everything (V2X) communication is one of the key technologies of 5G New Radio to support emerging applications such as autonomous driving. Due to the high density of vehicles, Remote Radio Heads (RRHs) will be deployed as Road Side Units to support V2X. Nevertheless, activation of all RRHs during low-traffic off-peak hours may cause energy wasting. The proper activation of RRH and association between vehicles and RRHs while maintaining the required service quality are the keys to reducing energy consumption. In this work, we first formulate the problem as an Integer Linear Programming optimization problem and prove that the problem is NP-hard. Then, we propose two novel algorithms, referred to as 'Least Delete (LD)' and 'Largest-First Rounding with Capacity Constraints (LFRCC).' The simulation results show that the proposed algorithms can achieve significantly better performance compared with existing solutions and are competitive with the optimal solution. Specifically, the LD and LFRCC algorithms can reduce the number of activated RRHs by 86% and 89% in low-density scenarios. In high-density scenarios, the LD algorithm can reduce the number of activated RRHs by 90%. In addition, the solution of LFRCC is larger than that of the optimal solution within 7% on average. © 2002-2012 IEEE.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Cooperative Multi-Agent Q-Learning Using Distributed MPC

引用

IEEE CONTROL SYSTEMS LETTERS 2024年 8卷 2193-2198页

作者： Esfahani, Hossein Nejatbakhsh Velni, Javad Mohammadpour Clemson Univ Dept Mech Engn Clemson SC 29634 USA

In this letter, we propose a cooperative Multi-Agent Reinforcement Learning (MARL) approach based on Distributed Model Predictive Control (DMPC). In the proposed framework, the local MPC schemes are formulated based on the dual decomposition method in the context of DMPC and will be used to derive the local state (and action) value functions required in a cooperative Q-learning algorithm. We further show that the DMPC scheme can yield a framework based on the Value Function Decomposition (VFD) principle so that the global state (and action) value functions can be decomposed into several local state (and action) value functions captured from the local MPCs. In the proposed cooperative MARL, the coordination between individual agents is then achieved based on the multiplier-sharing step, a.k.a inter-agent negotiation in the DMPC scheme.

关键词： Q-learning approximation algorithms Couplings Costs Predictive control Multi-agent systems Linear programming Multi-agent Q-Learning distributed MPC cooperative control

来源：评论

学校读者我要写书评

暂无评论

Reliability-Based Decoding of Low-Density Lattice Codes Using Gaussian and Eisenstein Integers

IEEE OPEN JOURNAL OF THE COMMUNICATIONS SOCIETY

引用

IEEE OPEN JOURNAL OF THE COMMUNICATIONS SOCIETY 2024年 5卷 4322-4336页

作者： Wiriya, Warangrat Kurkoski, Brian M. Japan Adv Inst Sci & Technol Sch Informat Sci Grad Sch Adv Sci & Technol Nomi 9231292 Japan

This paper proposes reliability-based decoding for complex low-density lattice codes (CLDLC) which can be applied to both Gaussian and Eisenstein integers. Two major contributions are: first, a decoding algorithm for CLDLC using a likelihood-based reliability function is used to determine the number of complex Gaussian functions at the variable node. This allows each message to be approximated by a variable number of Gaussian functions depending upon its reliability. An upper bound on the Kullback-Leibler (KL) divergence of the approximation is formed to find selection thresholds via linear regression. Second, a construction of CLDLC using Eisenstein integers is given. Compared to Gaussian integers, this reduces the complexity of CLDLC decoding by exploiting the structure of the Eisenstein integers. The proposed CLDLC decoding algorithm has higher performance and lower complexity compared to existing algorithms. When the reliability-based algorithm is applied to Eisenstein integer CLDLC decoding, the complexity is reduced to O(n.t. 1.35(d-1)) at the volume-to-noise ratio of 6 dB, for lattice dimension n, with degree d inverse generator matrix and t decoding iterations. Decoding CLDLC using Eisenstein integers has lower complexity than CLDLC using Gaussian integers when n >= 49 .

关键词： Lattices Decoding Codes Reliability Complexity theory Iterative decoding approximation algorithms Complex low-density lattice codes low-density lattice codes parametric decoder lattice decoder Eisenstein integers Gaussian integers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：