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

Broadcast Channel Coding: Algorithmic Aspects and Non-Signaling Assistance

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第11期70卷 7563-7580页

作者： Fawzi, Omar Ferme, Paul Univ Claude Bernard Lyon 1 UCBL CNRS Inria ENS Lyon F-69342 Lyon France

We address the problem of coding for classical broadcast channels, which entails maximizing the success probability that can be achieved by sending a fixed number of messages over a broadcast channel. For point-to-point channels, Barman and Fawzi found a (1-e(-1))-approximation algorithm running in polynomial time, and showed that it is NP-hard to achieve a strictly better approximation ratio. Furthermore, these algorithmic results were at the core of the limitations they established on the power of non-signaling assistance for point-to-point channels. It is natural to ask if similar results hold for broadcast channels, exploiting links between approximation algorithms of the channel coding problem and the non-signaling assisted capacity region. In this work, we make several contributions on algorithmic aspects and non-signaling assisted capacity regions of broadcast channels. For the class of deterministic broadcast channels, we describe a (1-e(-1))(2)-approximation algorithm running in polynomial time, and we show that the capacity region for that class is the same with or without non-signaling assistance. Finally, we show that in the value query model, we cannot achieve a better approximation (1) ratio than ohm(1/root m) in polynomial time for the general broadcast channel coding problem, with m the size of one of the outputs of the channel.

关键词： nonlocal non-signaling Broadcast channel approximation algorithms approximation algorithms non-signaling approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Bayesian-Learning-Based Diffusion Least Mean Square algorithms Over Networks

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2024年第10期35卷 13217-13231页

作者： Huang, Fuyi Zhang, Sheng Zheng, Wei Xing Guangxi Univ Sch Comp Elect & Informat Guangxi Key Lab Multimedia Commun & Network Techno Nanning 530004 Guangxi Peoples R China Southwest Jiaotong Univ Sch Informat Sci & Technol Chengdu 611756 Sichuan Peoples R China Western Sydney Univ Sch Comp Data & Math Sci Sydney NSW 2751 Australia

To improve the learning performance of the conventional diffusion least mean square (DLMS) algorithms, this article proposes Bayesian-learning-based DLMS (BL-DLMS) algorithms. First, the proposed BL-DLMS algorithms are inferred from a Gaussian state-space model-based Bayesian learning perspective. By performing Bayesian inference in the given Gaussian state-space model, a variable step-size and an estimation of the uncertainty of information of interest at each node are obtained for the proposed BL-DLMS algorithms. Next, a control method at each node is designed to improve the tracking performance of the proposed BL-DLMS algorithms in the sudden change scenario. Then, a lower bound on the variable step-size of each node of the proposed BL-DLMS algorithms is derived to maintain the optimal steady-state performance in the nonstationary scenario (unknown parameter vector of interest is time-varying). Afterward, the mean stability and the transient and steady-state mean square performance of the proposed BL-DLMS algorithms are analyzed in the nonstationary scenario. In addition, two Bayesian-learning-based diffusion bias-compensated LMS algorithms are proposed to handle the noisy inputs. Finally, the superior learning performance of the proposed learning algorithms is verified by numerical simulations, and the simulated results are in good agreement with the theoretical results.

关键词： Bayes methods Inference algorithms Steady-state Estimation State-space methods approximation algorithms Transient analysis Adaptive learning networks Bayesian learning diffusion algorithms distributed estimation machine learning

来源：评论

学校读者我要写书评

暂无评论

CONSTANT-RATIO approximation FOR ROBUST BIN PACKING WITH BUDGETED UNCERTAINTY

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第4期36卷 2534-2552页

作者： Bougeret, Marin Dosa, Gyorgy Goldberg, Noam Poss, Michael Univ Montpellier CNRS LIRMM F-34095 Montpellier France Univ Pannonia Dept Math H-8200 Veszprem Hungary Bar Ilan Univ Dept Management IL-5290002 Ramat Gan Israel

We consider robust variants of the bin packing problem with uncertain item sizes. Specifically we consider two uncertainty sets previously studied in the literature. The first is budgeted uncertainty (the U-Gamma), in which at most \Gamma items deviate, each reaching its peak value, while other items assume their nominal values. The second uncertainty set, the U-Omega model, bounds the total amount of deviation in each scenario. We show that a variant of the Next-cover algorithm is a 2 approximation for the U-Omega model, and another variant of this algorithm is a 2 Gamma approximation for the U\Gamma model. Unlike the classical bin packing problem, it is shown that (unless P = NP) no asymptotic approximation scheme exists for the U-Gamma for Gamma-1. This motivates the question of the existence of a constant approximation factor algorithm for the U-Gamma model. Our main result is to answer this question by proving a (polynomial-time) 4.5 approximation algorithm, based on a dynamic-programming approach.

关键词： bin-packing robust optimization approximation algorithms Next-cover dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Bias-Compensated Normalized Iterative Wiener Filter Algorithm With Noisy Input

引用

IEEE SIGNAL PROCESSING LETTERS 2025年 32卷 1445-1449页

作者： Yuan, Hai Lu, Lu Zhu, Guangya Chen, Badong Sichuan Univ Coll Elect & Informat Engn Chengdu 610065 Peoples R China Sichuan Univ Coll Elect Engn Chengdu 610065 Peoples R China Xi An Jiao Tong Univ Inst Artificial Intelligence & Robot Xian 710049 Peoples R China

The iterative Wiener filter (IWF) algorithm can achieve a fast convergence rate. However, its performance may degrade when it encounters noisy input scenarios. To tackle this problem, a novel IWF algorithm incorporating bias-compensation (BC-IWF) is proposed, which can enhance the performance of the algorithm by estimating the input noise variance. The BC-IWF algorithm optimizes the step size for each iteration and updates along the direction of the gradient. To further reduce the steady-state error, a normalized IWF by making use of the bias-compensation scheme (BC-NIWF) algorithm is proposed. Moreover, the steady-state performance of the BC-NIWF algorithm is analyzed. Simulation results demonstrate the validity of the theoretical analysis and the BC-NIWF algorithm achieves improved misadjustment compared with the state-of-the-art algorithms.

关键词： Signal processing algorithms approximation algorithms Noise measurement Steady-state Vectors Wiener filters Convergence Artificial intelligence Training Simulation Bias compensation iterative Wiener filter noisy input model steady-state analysis

来源：评论

学校读者我要写书评

暂无评论

Sparse Unmixing in the Presence of Mixed Noise Using ℓ0-Norm Constraint and Log-Cosh Loss

引用

IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING 2024年 62卷 1页

作者： Chan, Yiu Yu Li, Xiao-Peng Mai, Jiajie Leung, Chi-Sing So, Hing Cheung City Univ Hong Kong Dept Elect Engn Hong Kong Peoples R China Shenzhen Univ Coll Elect & Informat Engn Shenzhen 518060 Peoples R China Shenzhen Univ State Key Lab Radio Frequency Heterogeneous Integr Shenzhen 518060 Peoples R China

Over the past two decades, sparse unmixing (SU) has gained significant attention in the realm of hyperspectral imaging. The aims of SU are to seek a subset of spectral signatures and estimate their fractional abundances to represent each mixed spectral pixel. Conventional SU methods often employ the Frobenius norm and thus cannot work satisfactorily in the presence of non-Gaussian noise. Second, the ideal & ell;(0)-norm is usually substituted with its convex or nonconvex approximation in most existing algorithms, which may degrade the recovery performance. To address these issues, this article proposes a novel approach, termed sparse unmixing using & ell;(0) -norm constraint and log-cosh loss (SUNNING). We exploit the & ell;(0) function to minimize the fitting errors subject to three constraints, namely, nonnegativity, sum-to-one, and upper bounded & ell;(0)-norm. Then, we adopt the projected gradient descent (PGD) framework to solve such an optimization problem. SUNNING includes two alternating steps, gradient descent and nonconvex projection, where an optimality of the solution is guaranteed. Also, we prove the convergence of SUNNING, including the objective value and variable sequence. In addition, to attain higher unmixing accuracy, we exploit the spectral library pruning (SLP) strategy to eliminate inactive endmembers, yielding an improved SUNNING. Experimental results on synthetic and real-world datasets exhibit improved robustness and effectiveness of the suggested methods over the state-of-the-art algorithms. MATLAB code is available at: https://***/freeLix-YY/ IEEE_TGRS2024_SparseUnmixing_SUNNING_demo

关键词： Noise Hyperspectral imaging TV Libraries Vectors Classification algorithms approximation algorithms Hyperspectral image (HSI) analysis & ell y-norm projected gradient descent (PGD) robust optimization sparse unmixing (SU)

来源：评论

学校读者我要写书评

暂无评论

Program Scheduling With Multi-Skill and External Resource Coordination Consideration Using Improved NSGA-II: Case Study

引用

IEEE ACCESS 2024年 12卷 177491-177503页

作者： Zhang, Heng Zhou, Jingbo Ruan, Huaying Qin, Yixuan Guizhou Univ Sch Mech Engn Guiyang 550025 Peoples R China Guizhou Space Appliance Co Ltd Guiyang 550009 Peoples R China Wuhan Polytech Univ Sch Life Sci & Technol Wuhan 430023 Peoples R China

Technology-driven startups often experience fluctuations in business volume and their delivery peak exceeds the conventional functional department's human resource staffing. Resource allocation is crucial for ensuring timely completion of project deliverables within resource constraints. This study tackles the scheduling challenge under the condition of composite skills, with the goal of efficiently allocating diverse human resources while adhering to constraints such as external labor coordination and skill compatibility. Initially, an integer programming model was formulated to minimize the overall project duration and equalize the workload among employees. Subsequently, an enhanced fast and elitist non-dominated sorting genetic algorithm (NSGA-II) was developed by integrating heuristic-based population initialization and adaptive genetic strategies. A case study was then developed based on the R program of technology-driven company S. The allocation model was solved using both the classic and improved versions of the algorithm. The outcomes indicate that the fitness of the final generation significantly exceeds that of the initial generation, and the refined algorithm outperforms the conventional one in reducing the project duration and enhancing balance, with the potential to reduce project duration by 9% and enhance the balance by 40%. Cluster analysis and statistical methods were applied to extract three pivotal traits of the optimal allocation scheme, providing a scientific reference and decision-making foundation for managerial resource-allocation strategies.

关键词： Resource management Job shop scheduling Research and development Genetic algorithms Dynamic scheduling approximation algorithms Investment Standards Fluctuations Costs External resource coordination multi-skill multi-objective optimization NSGA-II program scheduling resource constrained multi-project scheduling problem workload balance

来源：评论

学校读者我要写书评

暂无评论

Performance Analysis of Perturbation-Enhanced SC Decoders

引用

IEEE COMMUNICATIONS LETTERS 2025年第3期29卷 507-511页

作者： Liu, Zhicheng Yao, Liuquan Yuan, Shuai Yan, Guiying Ma, Zhiming Liu, Yuting Beijing Jiaotong Univ Sch Math & Stat Beijing 100044 Peoples R China Univ Chinese Acad Sci Beijing 101408 Peoples R China Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China

In this letter, we analyze the delay probability of the first error position in perturbation-enhanced Successive cancellation (SC) decoding for polar codes. Our findings reveal that, asymptotically, an SC decoder's performance does not degrade after one perturbation, and it improves with a probability of 1/2. This analysis explains the sustained performance gains of perturbation-enhanced SC decoding as code length increases.

关键词： Decoding Perturbation methods Polar codes Codes Noise Delays Probability density function Performance gain Iterative decoding approximation algorithms perturbation-enhanced SC decoding first error position delay probability

来源：评论

学校读者我要写书评

暂无评论

Improved Deterministic Distributed Maximum Weight Independent Set approximation in Sparse Graphs 27

Improved Deterministic Distributed Maximum Weight Independen...

引用

27th International Conference on Principles of Distributed Systems, OPODIS 2023

作者： Gil, Yuval Technion – Israel Institute of Technology Haifa Israel

ISBN: (纸本)9783959773089

We design new deterministic CONGEST approximation algorithms for maximum weight independent set (MWIS) in sparse graphs. As our main results, we obtain new ∆(1 + ϵ)-approximation algorithms as well as algorithms whose approximation ratio depend strictly on α, in graphs with maximum degree ∆ and arboricity α. For (deterministic) ∆(1 + ϵ)-approximation, the current state-of-the-art is due to a recent breakthrough by Faour et al. [SODA 2023] that showed an O(log2(∆W) · log(1/ϵ) + log∗ n)-round algorithm, where W is the largest node-weight (this bound translates to O(log2 n · log(1/ϵ)) under the common assumption that W = poly(n)). As for α-dependent approximations, a deterministic CONGEST (8(1 + ϵ) · α)-approximation algorithm with runtime O(log3 n· log(1/ϵ)) can be derived by combining the aforementioned algorithm of Faour et al. with a method presented by Kawarabayashi et al. [DISC 2020]. As our main results, we show the following. A deterministic CONGEST algorithm that computes an α1+τ-approximation for MWIS in O(log nlog α) rounds for any constant τ > 0. To the best of our knowledge, this is the fastest runtime of any deterministic non-trivial approximation algorithm for MWIS to date. Furthermore, for the large class of graphs where α = ∆1−Θ(1), it implies a deterministic ∆1−Θ(1)-approximation algorithm with a runtime of O(log nlog α) which improves upon the result of Faour et al. in both approximation ratio (by a ∆Θ(1) factor) and runtime (by an O(log n/log α) factor). A deterministic CONGEST algorithm that computes an O(α)-approximation for MWIS in O(ατ log n) rounds for any (desirably small) constant τ > 0. This improves the runtime of the best known deterministic O(α)-approximation algorithm in the case that α = O(poly log n). This also leads to a deterministic ∆(1 + ϵ)-approximation algorithm with a runtime of O(ατ log nlog(1/ϵ)) which improves upon the runtime of Faour et al. in the case that α = O(poly log n). A deterministic CONGEST algorithm that computes

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

AVERAGE SUBMODULARITY OF MAXIMIZING ANTICOORDINATION IN NETWORK GAMES

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2024年第5期62卷 2639-2663页

作者： Das, Soham Eksin, Ceyhun Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA

We consider the control of decentralized learning dynamics for agents in an anticoordination network game. In the antico ordination network game, there is a preferred action in the absence of neighbors' actions, and the utility an agent receives from the preferred action decreases as more of its neighbors select the preferred action, potentially causing the agent to select a less desirable action. The decentralized dynamics that are based on the synchronous best-response dynamics converge for the considered payoffs. Given a convergent action profile, we measure antico ordination by the number of edges in the underlying graph that have at least one agent in either end of the edge not taking the preferred action. A designer wants to find an optimal set of agents to control under a finite budget in order to achieve maximum antico ordination (MAC) on game convergence as a result of the dynamics. We show that the MAC is submodular in expectation over all realizations of the payoff interaction constants in bipartite networks. The proof relies on characterizing well-behavedness of MAC instances for bipartite networks, and designing a coupling between the dynamics and another distribution preserving selection protocol, for which we can show the diminishing returns property. Utilizing this result, we obtain a performance guarantee for the greedy optimization of MAC. Finally, we provide a computational study to show the effectiveness of greedy node selection strategies to solve MAC on general bipartite networks.

关键词： game theory submodular optimization antico ordination games approximation algorithms games on graphs

来源：评论

学校读者我要写书评

暂无评论

E-Bus-Based Standby Energy Sharing for EVs in the Event of Large-Scale Grid Outage

引用

IEEE INTERNET OF THINGS JOURNAL 2024年第23期11卷 37885-37898页

作者： Fan, Haitao Hei, Mengzhe Chen, Zuyu Xing, Yijia Hu, Yujiao Guo, Deke Zhang, Xin Zhao, Xiang Pan, Yan Cent South Univ Forestry & Technol Sch Comp Sci & Math Changsha 410004 Peoples R China Natl Univ Def Technol Natl Key Lab Informat Syst Engn Changsha 410073 Peoples R China Natl Univ Def Technol Lab Big Data & Decis Changsha 410073 Peoples R China Future Network Res Ctr Purple Mt Labs Nanjing 211111 Peoples R China Natl Univ Def Technol Natl Key Lab Parallel & Distributed Comp Changsha 410073 Peoples R China

Electric vehicles (EVs), which have become one of the most important commuting vehicles in the world, heavily depend on the support of robust and efficient grids. Many researchers focus on optimizing the charging of EVs by the grid. However, they overlook the emergency charging when the large-scale grid fails. Inspired by the DC-2-DC technology, EVs can achieve vehicle-2-vehicle (V2V) energy sharing between each other, which inspires us to study leveraging the significant number of electric buses (e-buses) as effective and cost-efficient standby energy to charge low-power EVs when a large-scale grid outage occurs, whereas the feasibility, scheduling algorithm, and performance of e-bus-based V2V energy sharing remain open questions. With this in mind, we first reveal that it is feasible for e-buses to serve as effective standby power for low-power EVs, after careful analysis of real-world data. Then, we conduct a data-driven estimation of the energy consumption to determine the volume of the V2V shared energy for large-scale EVs. Accordingly, we formulate the e-bus-based V2V energy sharing problem, whose two objectives are to maximize the total number of the sufficiently charged EVs and to minimize the distance of these EVs moving to the e-bus for charging. The first objective is to charge more low-power EVs with the limited energy volume of the e-buses and the second objective is to reduce the range anxiety of the low-power EV drivers. Observing that existing algorithm is time-consuming or inefficient, which cannot be applied for the problem instance with a large number of e-buses and EVs, we design a low-complexity approximation algorithm for the problem. Both theoretical analysis and comprehensive data-driven evaluation demonstrate that the proposed algorithm, 1) significantly optimizes the optimization objectives by 23.6% and 15.8% on average, and up to 34.8% and 34.0% in extreme cases, compared with the existing approximation algorithm and 2) achieves over 100x

关键词： Charging stations approximation algorithms Roads Vehicles Costs Electric vehicle charging Energy consumption Charging distance (CD) data driven E-bus energy sharing E-taxi GAP grid outage heuristic algorithm vehicle-2-vehicle (V2V)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：