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

22nd International Symposium on Experimental algorithms, SEA 2024

作者： Faraj, Marcelo Fonseca Großmann, Ernestine Joos, Felix Möller, Thomas Schulz, Christian Heidelberg University Heidelberg Germany

ISBN: (纸本)9783959773256

Increasing the connectivity of a graph is a pivotal challenge in robust network design. The weighted connectivity augmentation problem is a common version of the problem that takes link costs into consideration. The problem is then to find a minimum cost subset of a given set of weighted links that increases the connectivity of a graph by one when the links are added to the edge set of the input instance. In this work, we give a first implementation of recently discovered better-than-2 approximations. Furthermore, we propose three new heuristics and one exact approach. These include a greedy algorithm considering link costs and the number of unique cuts covered, an approach based on minimum spanning trees and a local search algorithm that may improve a given solution by swapping links of paths. Our exact approach uses an ILP formulation with efficient cut enumeration as well as a fast initialization routine. We then perform an extensive experimental evaluation which shows that our algorithms are faster and yield the best solutions compared to the current state-of-the-art as well as the recently discovered better-than-2 approximation algorithms. Our novel local search algorithm can improve solution quality even further. © Marcelo Fonseca Faraj.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On Robust Millimeter Wave Line-of-Sight MIMO Communications With Few-Bit ADCs

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2022年第12期21卷 11164-11178页

作者： Song, Xiaohang Ma, Sinuo Neuhaus, Peter Wang, Wenjin Gao, Xiqi Fettweis, Gerhard Tech Univ Dresden Vodafone Chair Mobile Commun Syst D-01062 Dresden Germany Huawei Technol Duesseldorf GmbH Munich Res Ctr D-80992 Munich Germany Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China Purple Mt Labs Nanjing 211111 Peoples R China Tech Univ Dresden Ctr Tactile Internet Human Inthe Loop CeTI D-01062 Dresden Germany

This work focuses on providing robust line-of-sight (LoS) spatial multiplexing at flexible communications distances and directions. Considering oblique LoS uniform linear arrays, we first derive the rank-deficient and orthogonal conditions for the LoS MIMO channel matrices. With this discovery, the topology of high spatial-resolution on one side of the link is shown with a wide full-rank-channel guarantee interval over distance and direction variations. Additionally, to reduce the implementation costs and power consumption, we propose to use low amplitude-resolution quantizers at the side of high spatial-resolution. With numerical evaluations on systems having few-bit analog-to-digital converters (ADCs), the proposed system design is shown to simultaneously achieve a higher spectrum efficiency and higher energy efficiency compared to a conventional single-stream high-amplitude-resolution over a wide signal-to-noise-ratio (SNR) range. Furthermore, we investigate channel equalization under the extreme case of using 1-bit ADCs. After providing a new viewpoint on the generalized approximate message passing (GAMP) algorithm from constrained Bethe free energy minimization, our simulations on bit-error-rates show that the GAMP algorithm can significantly reduce the performance degradation due to coarse quantization and can significantly outperform the Bussgang decomposition based linear minimum-mean-square-error estimator, especially at high SNRs.

关键词： MIMO communication Topology Quantization (signal) Energy efficiency Inference algorithms approximation algorithms Space division multiplexing Line-of-sight MIMO millimeter wave and terahertz communications 1-bit communications message passing

来源：评论

学校读者我要写书评

暂无评论

Fast Filtering of Search Results Sorted by Attribute

引用

ACM TRANSACTIONS ON INFORMATION SYSTEMS 2022年第2期40卷 1–24页

作者： Nardini, Franco Maria Trani, Roberto Venturini, Rossano ISTI CNR I-56126 Pisa PI Italy Univ Pisa I-56126 Pisa PI Italy

Modern search services often provide multiple options to rank the search results, e.g., sort "by relevance", "by price" or "by discount" in e-commerce. While the traditional rank by relevance effectively places the relevant results in the top positions of the results list, the rank by attribute could place many marginally relevant results in the head of the results list leading to poor user experience. In the past, this issue has been addressed by investigating the relevance-aware filtering problem, which asks to select the subset of results maximizing the relevance of the attribute-sorted list. Recently, an exact algorithm has been proposed to solve this problem optimally. However, the high computational cost of the algorithm makes it impractical for the Web search scenario, which is characterized by huge lists of results and strict time constraints. For this reason, the problem is often solved using efficient yet inaccurate heuristic algorithms. In this article, we first prove the performance bounds of the existing heuristics. We then propose two efficient and effective algorithms to solve the relevance-aware filtering problem. First, we propose OPT-Filtering, a novel exact algorithm that is faster than the existing state-of-the-art optimal algorithm. Second, we propose an approximate and even more efficient algorithm, epsilon-Filtering, which, given an allowed approximation error epsilon, finds a (1-epsilon)-optimal filtering, i.e., the relevance of its solution is at least (1-epsilon) times the optimum. We conduct a comprehensive evaluation of the two proposed algorithms against state-of-the-art competitors on two real-world public datasets. Experimental results show that OPT-Filtering achieves a significant speedup of up to two orders of magnitude with respect to the existing optimal solution, while epsilon-Filtering further improves this result by trading effectiveness for efficiency. In particular, experiments show that epsilon-Filtering can achieve quasi-opt

关键词： Relevance-aware filtering filtering algorithms approximation algorithms efficiency-effectiveness trade-offs

来源：评论

学校读者我要写书评

暂无评论

Efficient Processing of Sparse Tensor Decomposition via Unified Abstraction and PE-Interactive Architecture

引用

IEEE TRANSACTIONS ON COMPUTERS 2022年第2期71卷 266-281页

作者： Wang, Bangyan Deng, Lei Qu, Zheng Li, Shuangchen Zhang, Zheng Xie, Yuan Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA

We propose a novel architecture to efficiently perform sparse tensor decomposition/completion. As the generalization of vectors and matrices, tensors are widely used to process high-dimensional data. Sparse tensor decomposition (SpTD) is not only an emerging tensor analysis technique but also an effective tool to reduce the storage and computation costs of tensors. However, conventional general-purpose processors are inefficient to perform SpTD, mainly due to: i) variable sparsity degree and flexible buffer size requirement;ii) difficulties of fusing multiple execution kernels to pursue better performance. For domain-specific accelerator designers on the other hand, the diversity of decomposition algorithms is also an important problem that must be considered. To solve these challenges, we propose a unified abstraction for SpTD algorithms and design a specialized accelerator. First, we formulate two types of core kernels (SpLrMM and LrSampling) that serve as a standard form to fit a broad range of SpTD algorithms. Second, we design a sparse tensor engine (STE) to efficiently perform SpTD. STE uses a processing element (PE)-interactive architecture where PEs can be flexibly grouped together via Network-on-Chip (NoC) to share the buffer capacity, bandwidth, and compute resources. We evaluate our accelerator with extensive experiments, and it can achieve an average speedup of 45x over CPU and 29x over GPU.

关键词： Tensors Kernel Bandwidth approximation algorithms Sparse matrices Graphics processing units Memory management Domain-specific accelerator tensor decomposition sparse processing deadlock avoidance

来源：评论

学校读者我要写书评

暂无评论

Deep-Unfolding Beamforming for Intelligent Reflecting Surface Assisted Full-Duplex Systems

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2022年第7期21卷 4784-4800页

作者： Liu, Yanzhen Hu, Qiyu Cai, Yunlong Yu, Guanding Li, Geoffrey Ye Zhejiang Univ Coll Informat Sci & Elect Engn Hangzhou 310027 Peoples R China Imperial Coll London Dept Elect & Elect Engn London SW7 2AZ England

In this paper, we investigate an intelligent reflecting surface (IRS) assisted multi-user multiple-input multiple-output (MIMO) full-duplex (FD) system. We jointly optimize the active beamforming matrices at the access point (AP) and uplink users, and the passive beamforming matrix at the IRS to maximize the weighted sum-rate of the system. Since it is practically difficult to acquire the channel state information (CSI) for IRS-related links due to its passive operation and large number of elements, we conceive a mixed-timescale beamforming scheme. Specifically, the high-dimensional passive beamforming matrix at the IRS is updated based on the channel statistics while the active beamforming matrices are optimized relied on the low-dimensional real-time effective CSI at each time slot. We propose an efficient stochastic successive convex approximation (SSCA)-based algorithm for jointly designing the active and passive beamforming matrices. Moreover, due to the high computational complexity caused by the matrix inversion computation in the SSCA-based optimization algorithm, we further develop a deep-unfolding neural network (NN) to address this issue. The proposed deep-unfolding NN maintains the structure of the SSCA-based algorithm but introduces a novel non-linear activation function and some learnable parameters induced by the first-order Taylor expansion to approximate the matrix inversion. In addition, we develop a black-box NN as a benchmark. Simulation results show that the proposed mixed-timescale algorithm outperforms the existing single-timescale algorithm and the proposed deep-unfolding NN approaches the performance of the SSCA-based algorithm with much reduced computational complexity when deployed online.

关键词： Array signal processing approximation algorithms Artificial neural networks Wireless communication Optimization Full-duplex system Computational complexity Intelligent reflecting surface full-duplex deep-unfolding neural network mixed-timescale beamforming machine learning

来源：评论

学校读者我要写书评

暂无评论

Towards Revenue-Driven Multi-User Online Task Offloading in Edge Computing

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2022年第5期33卷 1185-1198页

作者： Ma, Zhi Zhang, Sheng Chen, Zhiqi Han, Tao Qian, Zhuzhong Xiao, Mingjun Chen, Ning Wu, Jie Lu, Sanglu Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Univ New Jersey Inst Technol Dept Elect & Comp Engn Newark NJ 07102 USA Univ Sci & Technol China Suzhou Inst Adv Study Sch Comp Sci & Technol Hefei 230052 Anhui Peoples R China Temple Univ Dept Comp & Informat Sci Philadelphia PA 19122 USA

Mobile Edge Computing (MEC) has become an attractive solution to enhance the computing and storage capacity of mobile devices by leveraging available resources on edge nodes. In MEC, the arrivals of tasks are highly dynamic and are hard to predict precisely. It is of great importance yet very challenging to assign the tasks to edge nodes with guaranteed system performance. In this article, we aim to optimize the revenue earned by each edge node by optimally offloading tasks to the edge nodes. We formulate the revenue-driven online task offloading (ROTO) problem, which is proved to be NP-hard. We first relax ROTO to a linear fractional programming problem, for which we propose the Level Balanced Allocation (LBA) algorithm. We then show the performance guarantee of LBA through rigorous theoretical analysis, and present the LB-Rounding algorithm for ROTO using the primal-dual technique. The algorithm achieves an approximation ratio of 2(1+xi)ln(d+1) with a considerable probability, where d is the maximum number of process slots of an edge node and xi is a small constant. The performance of the proposed algorithm is validated through both trace-driven simulations and testbed experiments. Results show that our proposed scheme is more efficient compared to baseline algorithms.

关键词： Task analysis Cloud computing approximation algorithms Wireless communication Software Resource management Optimization Mobile edge computing primal-dual technique online computation offloading revenue-optimal

来源：评论

学校读者我要写书评

暂无评论

Vertex Cover Optimization Using a Novel Graph Decomposition Approach

引用

Computers, Materials & Continua 2022年第10期73卷 701-717页

作者： Abdul Manan Shahida Bashir Abdul Majid Department of Mathematics University of GujratGujrat50700Pakistan Department of Physics University of GujratGujrat50700Pakistan

The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph *** MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a *** algorithm exits till date that can exactly solve the problem in a deterministic polynomial time ***,several algorithms are proposed that solve the problem approximately in a short polynomial time *** algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational *** MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising *** work aims to solve the MVCP approximately by a novel graph decomposition *** decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or *** order to reduce complexity of the algorithm a new strategy is also *** reduction strategy can be used for any algorithm solving *** on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the *** algorithms are tested using well known standard benchmark *** key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.

关键词： Combinatorial optimization graph theory minimum vertex cover problem maximum independent set maximum degree greedy approach approximation algorithms benchmark instances

来源：评论

学校读者我要写书评

暂无评论

Optimal intervention in economic networks using influence maximization methods

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2022年第3期300卷 1136-1148页

作者： Klages-Mundt, Ariah Minca, Andreea Cornell Univ Ctr Appl Math 657 Rhodes Hall Ithaca NY 14853 USA Cornell Univ Sch Operat Res & Informat Engn 222 Rhodes Hall Ithaca NY 14853 USA

We consider optimal intervention in the Elliott-Golub-Jackson network model (Elliott, Golub, and Jackson, 2014) and we show that it can be transformed into an influence maximization-like form, interpreted as the reverse of a default cascade. Our analysis of the optimal intervention problem extends well-established targeting results to the economic network setting, which requires additional theoretical steps. We prove several results about optimal intervention: it is NP-hard and cannot be approximated to a constant factor in polynomial time. In turn, we show that randomizing failure thresholds leads to a version of the problem which is monotone submodular, for which existing powerful approximations in polynomial time can be applied. In addition to optimal intervention, we also show practical consequences of our analysis to other economic network problems: (1) it is computationally hard to calculate expected values in the economic network, and (2) influence maximization algorithms can enable efficient importance sampling and stress testing of large failure scenarios. We illustrate our results on a network of firms connected through input-output linkages inferred from the World Input Output Database. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Risk analysis Economic networks NP hardness approximation algorithms Influence maximization

来源：评论

学校读者我要写书评

暂无评论

Image Reconstruction of Targets Undergoing Complex Motion Based on Optical Phased Array Compressed-Sensing Ghost Imaging Technology

引用

JOURNAL OF LIGHTWAVE TECHNOLOGY 2022年第24期40卷 7746-7756页

作者： Wang, Zihao Sun, Yanling Liao, Jiali Cao, Rui Wang, Chen Jin, Li Feng, Junbo Cao, Changqing Xidian Univ Sch Phys & Optoelect Engn Xian 710126 Peoples R China United Microelect Ctr CUMEC Xiyong Microelect Ind Pk Chongqing 400000 Peoples R China

Existing optical phased array (OPA) dynamic imaging techniques can only be used to perform image reconstruction of targets undergoing simple motion. This article proposes an imaging technique for targets undergoing complex motion based on recent research in the OPA-LiDAR field. To this end, the proposed technique combines two sub-algorithms: an OPA scanning algorithm and a compressed-sensing ghost imaging (CS-GI) technique. The reliability of the proposed technique is verified based on theoretical analysis, numerical calculations, and experimental validation. The first sub-algorithm is an innovative adaptive, single-target, motion state extraction algorithm, utilizing the inertia-free scanning characteristics of OPA. From this, the trajectory of the target can be reshaped accurately, and the target motion state can be calculated with an error of less than 3%. The second sub-algorithm is a CS-GI algorithm that requires a small number of samples to achieve a high-resolution OPA-based GI. The sampling ratio employed in the CS-GI algorithm corresponds to the root mean square error (RMSE) convergence of the reconstructed image is 1. The proposed technique for moving target imaging can be effectively used to perform motion trajectory reshaping and image reconstruction of targets undergoing fast and complex motion. We believe that this technique can be effectively used in the fields of vehicle-mounted LiDAR, unmanned systems, and medical imaging.

关键词： Image reconstruction Nanophotonics Phased arrays approximation algorithms Optical imaging Adaptive optics Compressed scanning ghost imaging imaging systems optical phased array silicon nanophononics

来源：评论

学校读者我要写书评

暂无评论

Symplectic algorithms for Stable Manifolds in Control Theory

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第6期67卷 3105-3111页

作者： Chen, Guoyuan Zhu, Gaosheng Zhejiang Univ Finance & Econ Sch Data Sci Hangzhou 310018 Peoples R China Harbin Inst Technol Sch Math Harbin 150001 Peoples R China

In this article, we propose a symplectic algorithm for the stable manifolds of the Hamilton-Jacobi equations combined with an iterative procedure in [N. Sakamoto and A. J. van der Schaft, "Analytical approximation methods for the stabilizing solution of the Hamilton-Jacobi equation," IEEE Trans. Autom. Control, 2008]. Our algorithm includes two key aspects. The first one is to prove a precise estimate for radius of convergence and the errors of local approximate stable manifolds. The second one is to extend the local approximate stable manifolds to larger ones by symplectic algorithms, which have better long-time behaviors than general-purpose schemes. Our approach avoids the case of divergence of the iterative sequence of approximate stable manifolds and reduces the computation cost. We illustrate the effectiveness of the algorithm by an optimal control problem with exponential nonlinearity.

关键词： Manifolds approximation algorithms Convergence Optimal control Iterative algorithms Feedback control Eigenvalues and eigenfunctions Hamiltonian systems Hamilton-Jacobi (HJ) equations optimal control stable manifolds symplectic algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：