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

Age of Information Diffusion on Social Networks

IEEE TRANSACTIONS ON NETWORKING 2025年第2期33卷 701-712页

作者： Li, Songhua Duan, Lingjie Singapore Univ Technol & Design Pillar Engn Syst & Design Singapore City 487372 Singapore

To promote viral marketing, major social platforms (e.g., Facebook Marketplace and Pinduoduo) repeatedly select and invite different users (as seeds) in online social networks to share fresh information about a product or service with their friends. Thereby, we are motivated to optimize a multi-stage seeding process of viral marketing in social networks, and adopt the recent notions of the peak and the average age of information (AoI) to measure the timeliness of promotion information received by network users. Our problem is different from the literature on information diffusion in social networks, which limits to one-time seeding and overlooks AoI dynamics or information replacement over time. As a critical step, we manage to develop closed-form expressions that characterize and trace AoI dynamics over any social network. For the peak AoI problem, we first prove the NP-hardness of our multi-stage seeding problem by a highly non-straightforward reduction from the dominating set problem, and then present a new polynomial-time algorithm that achieves good approximation guarantees (e.g., less than 2 for linear network topology). To minimize the average AoI, we also prove that our problem is NP-hard by properly reducing it from the set cover problem. Benefiting from our two-sided bound analysis on the average AoI objective, we build up a new framework for approximation analysis and link our problem to a much simplified sum-distance minimization problem. This intriguing connection inspires us to develop another polynomial-time algorithm that achieves a good approximation guarantee. Additionally, our theoretical results are well corroborated by experiments on a real social network.

关键词： approximation algorithms Minimization Information diffusion Information age Network topology Heuristic algorithms Monitoring Closed-form solutions Topology Receivers Age of information social network multi-stage seeding NP-hardness approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Adversarially Robust Neural Architectures

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2025年第5期47卷 4183-4197页

作者： Dong, Minjing Li, Yanxi Wang, Yunhe Xu, Chang City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China Univ Sydney Fac Engn Sch Comp Sci Darlington NSW 2008 Australia Huawei Technol Co Ltd Noahs Ark Lab Beijing 100085 Peoples R China

Deep Neural Networks (DNNs) are vulnerable to adversarial attacks. Existing methods are devoted to developing various robust training strategies or regularizations to update the weights of the neural network. But beyond the weights, the overall structure and information flow in the network are explicitly determined by the neural architecture, which remains unexplored. Thus, this paper aims to improve the adversarial robustness of the network from the architectural perspective. We explore the relationship among adversarial robustness, Lipschitz constant, and architecture parameters and show that an appropriate constraint on architecture parameters could reduce the Lipschitz constant to further improve the robustness. The importance of architecture parameters could vary from operation to operation or connection to connection. We approximate the Lipschitz constant of the entire network through a univariate log-normal distribution, whose mean and variance are related to architecture parameters. The confidence can be fulfilled through formulating a constraint on the distribution parameters based on the cumulative function. Compared with adversarially trained neural architectures searched by various NAS algorithms as well as efficient human-designed models, our algorithm empirically achieves the best performance among all the models under various attacks on different datasets.

关键词： Computer architecture Robustness Training Neural networks Optimization Neural architecture search Closed box approximation algorithms Perturbation methods Microprocessors Adversarial robustness neural architecture search

来源：评论

学校读者我要写书评

暂无评论

Beamforming Optimization for Robust Sensing and Communication in Dynamic mmWave MIMO Networks

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2025年第4期43卷 1354-1370页

作者： Li, Lei Zhang, Jiawei Chang, Tsung-Hui Chinese Univ Hong Kong Sch Sci & Engn Shenzhen 518172 Peoples R China Shenzhen Res Inst Big Data Shenzhen 518172 Peoples R China

Acquiring accurate channel state information (CSI) at low overhead is crucial for millimeter wave MIMO communications but is challenging in dynamic environments. In this work, we exploit the emerging integrated sensing and communication (ISAC) beamforming technique for concurrent CSI sensing and data transmission. Despite its low overhead, the corresponding ISAC transmit beamforming design faces a complex trade-off between CSI sensing accuracy and communication interference management. To address this, we formulate the beamforming design as an optimization problem minimizing the maximum Cram & eacute;r-Rao bound (CRB) of CSI sensing errors subject to the users' worst-case communication rates under CSI errors. To efficiently solve the problem, we step-by-step propose three algorithms. The first algorithm is based on the semidefinite relaxation and successive convex optimization techniques, which can serve as a benchmark algorithm but suffers high computational complexity. To efficiently handle the worst-case objective and rate constraints, we propose a complexity-reduced algorithm based on the primal-dual optimization method and first-order min-max algorithm. Furthermore, we dismiss SDR and employ the block coordinate descent method combined with cheap gradient descent steps to achieve a low-complexity algorithm. Extensive simulations show the proposed ISAC beamforming design and low-complexity algorithms can provide robust communication performance and significantly outperform existing schemes.

关键词： Sensors Array signal processing Millimeter wave communication Optimization Signal processing algorithms Minimax techniques Integrated sensing and communication Vectors Prediction algorithms approximation algorithms CSI acquisition ISAC robust beamforming low-complexity design

来源：评论

学校读者我要写书评

暂无评论

Accelerated Algorithm for Back-Projection Fully Focused SAR Altimetry

引用

IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING 2025年 63卷

作者： Hernandez-Burgos, Sergi Gibert, Ferran Broquetas, Antoni Villalvilla, Pol Egido, Alejandro Moyano, Gorka de la Cruz, Adrian Flores Fornari, Marco isardSAT SL Barcelona 08005 Catalonia Spain Univ Politecn Cataluna Signal Theory & Commun Dept Barcelona 08034 Catalonia Spain European Space Agcy European Space Res & Technol Ctr NL-2201 AZ Noordwijk Netherlands Stn Grp European Space Agcy ESA ESTEC NL-2201 AZ Noordwijk Netherlands

Fully focused (FF) synthetic aperture radar (SAR) back-projection algorithms for radar altimetry have gained attention in the altimetry community due to their improved azimuth resolution compared to traditional methods, such as the delay/Doppler algorithm. However, the significant computational cost of back-projection has limited its use in operational applications. This article presents an accelerated back-projection algorithm that reduces the runtime of the classic back-projection by a factor of 28 on a CPU-based architecture. When implemented on a GPU-based architecture, the accelerated back-projection achieves a speedup ranging from 8 to 13 times compared to the classic back-projection on the same GPU. In comparison to the classic back-projection running on a CPU, the combination of the accelerated back-projection and GPU processing results in an overall improvement of up to 1570 times. The accelerated algorithm maintains the accuracy of classic time-domain algorithms and allows for the processing of data in the order of the sensing time under a GPU-based architecture. The algorithm has been extensively validated using transponder and open ocean data. These results indicate that operational back-projection algorithms are feasible for current radar altimetry missions, such as Sentinel-6, and upcoming missions like CRISTAL and Sentinel-3 Next Generation.

关键词： Azimuth Synthetic aperture radar Focusing approximation algorithms Altimetry Surface waves Transponders Sea surface Spaceborne radar Lighting Accelerated algorithm accelerated back-projection back-projection delay/Doppler fully focused (FF) fully focused synthetic aperture radar (FF-SAR) GPU acceleration high-resolution radar altimetry omega-K open ocean radar altimetry real time altimetry synthetic aperture radar (SAR) transponder

来源：评论

学校读者我要写书评

暂无评论

Fast, Robust, and Learned Distribution-Based Sorting

引用

IEEE ACCESS 2025年 13卷 45198-45214页

作者： Ferragina, Paolo Odorisio, Mattia St Anna Sch Adv Studies Dept LEMbeDS Pisa Italy Univ Pisa Dept Comp Sci Pisa Italy

Despite a long history of research and achievements in designing sorting routines, new hardware features and application requirements pose advanced challenges that computer scientists are recently tackling through novel data-aware (learned) algorithms. This paper aims to better understand the strengths and limitations of learned sorters for numerical data, by addressing two main research and engineering questions: (Q1) Which is the best trade-off, in sorting items, between the efficacy of a "learned" model in approximating the distribution of the input data and its time-space complexity? and (Q2) Which algorithmic structure for distribution-based sorting is suited to leverage a learned model in order to achieve state-of-the-art performance? To answer Q1, we implement a variant of the best-known learned model (i.e., the two-layers RMI) and, also, design a fully new learned model that turns out to be space-time efficient and efficacious in approximating adversarial input distributions. We experimentally test them over 11 datasets of 200M and 800M 64-bit floating-point items, thus offering a comprehensive answer to Q1. We then address Q2 by plugging the best-learned models from above into a distribution-based sorting scheme that leads to three new sorters whose performance is tested over 33 datasets (real and synthetic) of sizes up to 800M items. Our experimental results will show that our sorters perform better than 6 (classic and learned) best-known sorters on 29 out of those 33 datasets, thus achieving new state-of-the-art tradeoffs.

关键词： Sorting Indexes Data models Partitioning algorithms approximation algorithms Synthetic data Proposals Hardware Numerical models Interpolation learned sort learned indexes learned-based data structures

来源：评论

学校读者我要写书评

暂无评论

On MAX-SAT with cardinality constraint

引用

THEORETICAL COMPUTER SCIENCE 2025年 1025卷

作者： Panolan, Fahad Yaghoubizade, Hannane Univ Leeds Sch Comp Leeds England Sharif Univ Technol Dept Math Sci Tehran Iran

We consider the weighted MAX-SAT problem with an additional constraint that at most k variables can be set to true. We call this problem k-WMAX-SAT. This problem admits a (1-1/e)-factor approximation algorithm in polynomial time [Sviridenko, Algorithmica (2001)] and it is proved that there is no (1-1/e+& varepsilon;)-factor approximation algorithm in f(k)& sdot;n(o(k)) time for Maximum Coverage, the unweighted monotone version of k-WMAX-SAT [Manurangsi, SODA 2020]. Therefore, we study two restricted versions of the problem in the realm of parameterized complexity. 1. When the input is an unweighted 2-CNF formula (the problem is called k-MAX-2SAT), we design an efficient polynomial-size approximate kernelization scheme. That is, we design a polynomial-time algorithm that given a 2-CNF formula psi and & varepsilon;>0, compresses the input instance to a 2-CNF formula psi(star) such that any c-approximate solution of psi(star) can be converted to a c(1-& varepsilon;)-approximate solution of psi in polynomial *** the input is a planar CNF formula, i.e., the variable-clause incidence graph is a planar graph, we show the following results: center dot There is an FPT algorithm for k-WMAX-SAT on planar CNF formulas that runs in 2O(k)& sdot;(C+V) time. center dot There is a polynomial-time approximation scheme for k-WMAX-SAT on planar CNF formulas that runs in time 2(O(1/& varepsilon;))& sdot;k & sdot;(C+V). The above-mentioned C and V are the number of clauses and variables of the input formul a respectively.

关键词： Parameterized algorithms approximation algorithms MAX-SAT MAX-2SAT

来源：评论

学校读者我要写书评

暂无评论

Robust Task Allocations by Distributing the Risk Among Agents: Theory and algorithms

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2025年 22卷 6475-6491页

作者： Sengupta, Raunak Nagi, Rakesh Sreenivas, Ramavarapu S. Univ Illinois Dept Ind & Enterprise Syst Engn Urbana IL 61801 USA Singapore Univ Technol & Design Engn Syst & Design Pillar Singapore 487372 Singapore

We address the problem of generating robust solutions for the makespan minimization problem on identical agents (parallel machines), under the assumption that only interval bounds of processing times are known. While there are various concepts of robustness in the literature, we prove using pathological examples that any of these criteria may result in allocations with undesirable characteristics. We identify key properties that must be satisfied for a solution to be considered truly robust. Given a set of jobs with associated loads and uncertainties, it is shown that an allocation that balances loads and uncertainties simultaneously is extremely robust and satisfies multiple other existing criteria of robustness within an acceptable approximation factor. Thus, robustness is achieved by distributing the uncertainty/risk among the agents along with the load. The problem of finding a robust allocation is reduced to a bi-criteria two-dimensional load balancing problem, with the two dimensions being the load and the uncertainty. We prove that for the case with 2 agents, an allocation that satisfies a 1.5-approximation on both dimensions simultaneously always exists and can be found efficiently, and is also the best possible guarantee. For the general case with any number of agents, we prove that an allocation that satisfies a 2-approximation on one dimension and a 2.5-approximation on the other always exists and can be found in pseudo-polynomial time. The approximation algorithms presented in this paper are complemented by interesting existential and structural results and contribute to the vector scheduling literature for two dimensions as well. Finally, an extensive numerical analysis is presented, where we demonstrate our algorithms' near-optimal performance and ability to generate allocations that satisfy multiple criteria of robustness simultaneously in a short amount of time. Note to Practitioners-This paper introduces a simple and provably effective methodology f

关键词： Resource management Uncertainty Robustness approximation algorithms Minimization Pathology Load management Robust scheduling task allocation multi-agent approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Sparse Regression LDPC Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2025年第1期71卷 167-191页

作者： Ebert, Jamison R. Chamberland, Jean-Francois Narayanan, Krishna R. Qualcomm Technol Inc San Diego CA 92121 USA Texas A&M Univ Dept Elect & Comp Engn College Stn TX 77843 USA

This article introduces a novel concatenated coding scheme called sparse regression LDPC (SR-LDPC) codes. An SR-LDPC code consists of an outer non-binary LDPC code and an inner sparse regression code (SPARC), whose respective field size and section sizes are equal. For such codes, an efficient decoding algorithm is proposed based on approximate message passing (AMP) that dynamically shares soft information between inner and outer decoders. This dynamic exchange of information is facilitated by a denoiser that runs belief propagation (BP) on the factor graph of the outer LDPC code within each AMP iteration. It is shown that this BP denoiser falls within the framework of non-separable denoising functions and subsequently, that state evolution holds for the proposed AMP-BP algorithm. Leveraging the rich structure of SR-LDPC codes, this article proposes an efficient low-dimensional approximate state evolution recursion that can be used for efficient hyperparameter tuning, thus paving the way for future work on optimal code design. Finally, numerical simulations demonstrate that SR-LDPC codes outperform contemporary codes over the AWGN channel for parameters of practical interest. SR-LDPC codes are shown to be viable means for obtaining shaping gains over the AWGN channel.

关键词： Codes Encoding Decoding Iterative decoding AWGN channels Vectors approximation algorithms Heuristic algorithms Sparse matrices Signal to noise ratio LDPC codes sparse regression codes (SPARCs) approximate message passing belief propagation shaping gain

来源：评论

学校读者我要写书评

暂无评论

Max-Sum-Based Data Associations for Tracking Point and Extended Targets

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 2025年第2期61卷 3059-3075页

作者： Ma, Weizhen Jing, Zhongliang Dong, Peng Leung, Henry Shanghai Jiao Tong Univ Sch Aeronaut & Astronaut Shanghai 200240 Peoples R China Univ Calgary Dept Elect & Comp Engn Calgary AB T2N 1N4 Canada

For multitarget tracking applications, data association is a fundamental problem of assigning measurements to their corresponding targets. In this article, we propose two algorithms for tracking point and extended targets, respectively, based on factor graph representations of the joint probability density functions. Both employ the max-sum (MS) algorithm to find the maximum a posteriori assignment such that the state of each target is updated with the most probable measurement(s). We model the single target densities as Gaussian distribution for point targets and gamma Gaussian inverse Wishart distribution for extended targets. Under linear Gaussian assumptions on the target models, the proposed algorithms provide analytical solutions to multitarget tracking problems. Specifically, the messages flowed in the factor graphs, existence probabilities and states of the targets are analytically calculated. These two algorithms have reduced computational load compared to the particle-based sum-product (SP) algorithms and avoid gating or clustering used by traditional multitarget tracking methods. We compare the proposed MS-based algorithms (MSAs) with the Poisson multi-Bernoulli mixture filters and the SP-based algorithms, and simulation results show that the MSAs have comparable or improved tracking performance.

关键词： Target tracking Filters Clustering algorithms approximation algorithms Probability density function Heuristic algorithms Aerospace and electronic systems Probabilistic logic Kinematics Extraterrestrial measurements Data association (DA) extended target tracking (ETT) factor graph max-sum (MS) algorithm point target tracking (PTT)

来源：评论

学校读者我要写书评

暂无评论

Colorful Star Motif Counting: Concepts, algorithms and Applications

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2025年第3期37卷 1105-1125页

作者： Qin, Hongchao Sen, Gao Li, Rong-Hua Chen, Hongzhi Yuan, Ye Wang, Guoren Beijing Inst Technol Dept Comp Sci Beijing 100811 Peoples R China Natl Univ Singapore Sch Comp Comp Sci Singapore 119077 Singapore ByteDanceInfrastruct Team Beijing 100098 Peoples R China

A colorful star motif is a star-shaped graph where any two nodes have different colors. Counting the colorful star motif can help to analyze the structural properties of real-life colorful graphs, model higher-order clustering, and accelerate the mining of the densest subgraph exhibiting h-clique characteristics in graphs. In this manuscript, we introduce the concept of colorful h-star in a colored graph and proposes two higher-order cohesive subgraph models, namely colorful h-star core and colorful h-star truss. We show that the colorful h-stars can be counted and updated very efficiently using a novel dynamic programming (DP) algorithm. Based on the proposed DP algorithm, we develop a colorful h-star core decomposition algorithm which takes O(hm) time, O(hn+m) space;and a colorful h-star truss decomposition algorithm which takes O(hm(1.5)) time, O(hm) space, where mm and n denote the number of edges and nodes of the graph respectively. Moreover, we also propose a graph reduction technique based on our colorful h-star core model to accelerate the computation of the approximation algorithm for h-clique densest subgraph mining. The results of comprehensive experiments on 11 large real-world datasets demonstrate the efficiency, scalability and effectiveness of the proposed algorithms.

关键词： Stars approximation algorithms Image color analysis Color Heuristic algorithms Clustering algorithms Computational modeling Wireless communication Dynamic programming Analytical models Colorful star K-core K-truss H-clique densest subgraph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：