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

Steiner trees in uniformly quasi-bipartite graphs

INFORMATION PROCESSING LETTERS 2002年第4期83卷 195-200页

作者： Gröpl, C Hougardy, S Nierhoff, T Prömel, HJ Humboldt Univ Inst Informat D-10099 Berlin Germany

The area of approximation algorithms for the Steiner tree problem in graphs has seen continuous progress over the last years. Currently the best approximation algorithm has a performance ratio of 1.550. This is still far away from 1.0074, the largest known lower bound on the achievable performance ratio. As all instances resulting from known lower bound reductions are uniformly quasi-bipartite, it is interesting whether this special case can be approximated better than the general case. We present an approximation algorithm with performance ratio 73/60 < 1.217 for the uniformly quasi-bipartite case. This improves on the previously known ratio of 1.279 of Robins and Zelikovsky. We use a new method of analysis that combines ideas from the greedy algorithm for set cover with a matroid-style exchange argument to model the connectivity constraint. As a consequence, we are able to provide a tight instance. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： analysis of algorithms approximation algorithms network design Steiner tree problem in graphs

来源：评论

学校读者我要写书评

暂无评论

3-D Path Planning Using Improved RRT* Algorithm for Robot-Assisted Flexible Needle Insertion in Multilayer Tissues

IEEE CANADIAN JOURNAL OF ELECTRICAL AND COMPUTER ENGINEERING

引用

IEEE CANADIAN JOURNAL OF ELECTRICAL AND COMPUTER ENGINEERING 2022年第1期45卷 50-62页

作者： Zhang, Yongkang Ju, Zhiyang Zhang, Hui Qi, Zhi Beihang Univ Sch Transportat Sci & Engn Beijing 100191 Peoples R China

In the field of minimally invasive surgery, flexible needles can avoid blood vessels and organs more flexibly compared to rigid needles. One of the main challenges when using flexible needles to reach lesions is planning a suitable path. Due to the non-holonomic characteristic of the flexible needle dynamics and the tissue deformation caused by the needle tip during the insertion, the accessibility and safety of the needle's states need to be considered in the path planning stage. In this article, we propose an adaptable algorithm by improving the canonical rapidly exploring random trees* (RRT*) algorithm to compute a path for the flexible needle to reach targets in a layered tissue environment. The improved RRT* algorithm that addresses the motion constraints of the flexible needle renders the computed path comparatively smoother and optimal in some approximation sense. In the proposed algorithm, a strategy of adapting some of its parameters for different tissues during the insertion is developed, which improves the safety of surgeries. Moreover, the path cost used in the algorithm takes the potential fields of surrounding obstacles into account, which is used to deal with the influence of the local movement of tissues during the needle puncture process. Simulations are conducted to verify the effectiveness of the proposed algorithm. The results show that the improved RRT* algorithm generates a smooth and safe path which satisfies the motion constraints of the flexible needle in layered tissue environment.

关键词： Needles Path planning Planning approximation algorithms Nonhomogeneous media Kinematics Inverse problems Flexible needle insertion multilayer tissues path planning rapidly exploring random trees* (RRT*)

来源：评论

学校读者我要写书评

暂无评论

Evolutionary Multimodal Multiobjective Optimization for Traveling Salesman Problems

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2024年第2期28卷 516-530页

作者： Liu, Yiping Xu, Liting Han, Yuyan Zeng, Xiangxiang Yen, Gary G. Ishibuchi, Hisao Hunan Univ Coll Comp Sci & Elect Engn Changsha 410082 Peoples R China Liaocheng Univ Sch Comp Sci Liaocheng 252059 Peoples R China Oklahoma State Univ Sch Elect & Comp Engn Stillwater OK 74078 USA Southern Univ Sci & Technol Dept Comp Sci & Engn Guangdong Prov Key Lab Brain Inspired Intelligent Shenzhen 518055 Peoples R China

Multimodal multiobjective optimization problems (MMOPs) are commonly seen in real-world applications. Many evolutionary algorithms have been proposed to solve continuous MMOPs. However, little effort has been made to solve combinatorial (or discrete) MMOPs. Searching for equivalent Pareto-optimal solutions in the discrete decision space is challenging. Moreover, the true Pareto-optimal solutions of a combinatorial MMOP are usually difficult to know, which has limited the development of its optimizer. In this article, we first propose a test problem generator for multimodal multiobjective traveling salesman problems (MMTSPs). It can readily generate MMTSPs with known Pareto-optimal solutions. Then, we propose a novel evolutionary algorithm to solve MMTSPs. In our proposed algorithm, we develop two new edge assembly crossover operators, which are specialized in searching for superior solutions to MMTSPs. Moreover, the proposed algorithm uses a new environmental selection operator to maintain a good balance between the objective space diversity and decision space diversity. We compare our algorithm with five state-of-the-art designs. Experimental results convincingly show that our algorithm is powerful in solving MMTSPs.

关键词： Pareto optimization Optimization Evolutionary computation Generators Traveling salesman problems Search problems approximation algorithms Combinatorial optimization evolutionary multimodal multiobjective optimization test problems traveling salesman problem (TSP)

来源：评论

学校读者我要写书评

暂无评论

Detail-Enhanced Multi-Scale Exposure Fusion in YUV Color Space

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY 2020年第8期30卷 2418-2429页

作者： Wang, Qiantong Chen, Weihai Wu, Xingming Li, Zhengguo Beihang Univ Sch Automat Sci & Elect Engn Beijing 100191 Peoples R China Anhui Univ Sch Elect Engn & Automat Hefei Peoples R China ASTAR Inst Infocomm Res Signal Proc Dept Singapore 138632 Singapore

It is recognized that existing multi-scale exposure fusion algorithms can be improved using edge-preserving smoothing techniques. However, the complexity of edge-preserving smoothing-based multi-scale exposure fusion is an issue for mobile devices. In this paper, a simpler multi-scale exposure fusion algorithm is designed in YUV color space. The proposed algorithm can preserve details in the brightest and darkest regions of a high dynamic range (HDR) scene and the edge-preserving smoothing-based multi-scale exposure fusion algorithm while avoiding color distortion from appearing in the fused image. The complexity of the proposed algorithm is about half of the edge-preserving smoothing-based multi-scale exposure fusion algorithm. The proposed algorithm is thus friendlier to the smartphones than the edge-preserving smoothing-based multi-scale exposure fusion algorithm. In addition, a simple detail-enhancement component is proposed to enhance fine details of fused images. The experimental results show that the proposed component can be adopted to produce an enhanced image with visibly enhanced fine details and a higher MEF-SSIM value. This is impossible for existing detail enhancement components. Clearly, the component is attractive for PC-based applications.

关键词： Image color analysis approximation algorithms Smoothing methods Image edge detection Complexity theory Heuristic algorithms Optimization High dynamic range exposure fusion image pyramid multi-scale fusion detail enhancement

来源：评论

学校读者我要写书评

暂无评论

FastDTW is Approximate and Generally Slower Than the Algorithm it Approximates

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2022年第8期34卷 3779-3785页

作者： Wu, Renjie Keogh, Eamonn J. Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA

Many time series data mining problems can be solved with repeated use of distance measure. Examples of such tasks include similarity search, clustering, classification, anomaly detection and segmentation. For over two decades it has been known that the Dynamic Time Warping (DTW) distance measure is the best measure to use for most tasks, in most domains. Because the classic DTW algorithm has quadratic time complexity, many ideas have been introduced to reduce its amortized time, or to quickly approximate it. One of the most cited approximate approaches is FastDTW. The FastDTW algorithm has well over a thousand citations and has been explicitly used in several hundred research efforts. In this work, we make a surprising claim. In any realistic data mining application, the approximate FastDTW is much slower than the exact DTW. This fact clearly has implications for the community that uses this algorithm: allowing it to address much larger datasets, get exact results, and do so in less time.

关键词： Time series analysis approximation algorithms Time measurement Task analysis Classification algorithms Data mining Heart beat Dynamic time warping time series analysis similarity measures data mining

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for the Steiner tree problem with bounded edge-length

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 123卷 20-36页

作者： Chen, Chi-Yeh Hsieh, Sun-Yuan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn 1 Univ Rd Tainan Taiwan

This work firstly studies the Steiner tree problem with bounded edge-length din which dis the ratio of the maximum edge cost to the minimum edge cost. This work analyzes the algorithm of Byrka et al. [19] and shows that the approximation ratio of dln4d/d+ln4-1 + epsilon for general graphs and approximation ratio of 73.d/60.d+13 + epsilon for quasi-bipartite graphs. The algorithm implies approximation ratio of 1.162 + epsilon for the problem on complete graphs with edge distances 1 and 2. This finding represents an improvement upon the previous best approximation ratio of 1.25. This work then presents a combinatorial two-phase heuristic for the general Steiner tree in greedy strategy that achieves an approximation ratio of 1.4295. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Steiner trees approximation algorithms Network design Randomized algorithms Greedy algorithms

来源：评论

学校读者我要写书评

暂无评论

Amplitude-Dependent Phase-Gradient Directional Beamforming for IRS: A Scalable Optimization Framework

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2024年第4期72卷 2354-2369页

作者： Mao, Zhuang Wang, Wei Xia, Qian Huang, Chongwen Pan, Xinhua Ye, Zhizhen Zhejiang Univ Coll Informat Sci & Elect Engn Hangzhou 310027 Peoples R China China Jiliang Univ Coll Informat Engn Hangzhou 310018 Peoples R China Zhejiang Univ Coll Mat Sci & Engn Hangzhou 310027 Peoples R China Zhejiang Univ Inst Wenzhou Wenzhou Key Lab Novel Optoelect & Nano Mat Wenzhou 325006 Peoples R China

Intelligent reflecting surface (IRS) usually consists of a large number of passive elements, for which the element-grouping strategies can be adopted to group adjacent elements into a sub-surface for lower computational complexity. For the grouped elements of a sub-surface, the linear gradient phase shift configuration can achieve directional IRS reflect beam towards the intended receiver. In this paper, we propose a practical scalable optimization framework for element-grouping IRS by adopting the amplitude-dependent phase-gradient directional beamforming, which induces a new amplitude-phase coupling to the reflected signal. Specifically, by deriving the phase-gradient condition from Fermat's principle, we propose a practical phase-gradient IRS reflection model. Under this practical model, the amplitude-phase coupling becomes complicated, which brings technical challenges to the IRS beamforming optimization. We study a joint transmit and reflect beamforming optimization problem to minimize the transmit power. By designing a trigonometric transformation to deal with the complicated amplitude-phase coupling, we propose a penalty-based phase control strategy under given element grouping. Subsequently, to solve the element-grouping combinatorial problem with performance guarantee, we propose a low-complexity IRS reflect beamforming algorithm based on Markov approximation. Simulation results demonstrate that the proposed algorithm achieves substantial performance gains compared to conventional schemes.

关键词： Array signal processing Optimization Wireless communication Couplings Mirrors approximation algorithms Performance gain Intelligent reflecting surface reflection coefficient directional beamforming amplitude-phase coupling

来源：评论

学校读者我要写书评

暂无评论

Friedkin-Johnsen Model for Opinion Dynamics on Signed Graphs

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2024年第12期36卷 8313-8327页

作者： Zhou, Xiaotian Sun, Haoxin Xu, Wanyue Li, Wei Zhang, Zhongzhi Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai 200433 Peoples R China Fudan Univ Acad Engn & Technol Shanghai 200433 Peoples R China

A signed graph offers richer information than an unsigned graph, since it describes both collaborative and competitive relationships in social networks. In this paper, we study opinion dynamics on a signed graph, based on the Friedkin-Johnsen model. We first interpret the equilibrium opinion in terms of a defined random walk on an augmented signed graph, by representing the equilibrium opinion of every node as a combination of all nodes' internal opinions, with the coefficient of the internal opinion for each node being the difference of two absorbing probabilities. We then quantify some relevant social phenomena and express them in terms of the & ell;(2) norms of vectors. We also design a nearly-linear time signed Laplacian solver for assessing these quantities, by establishing a connection between the absorbing probability of random walks on a signed graph and that on an associated unsigned graph. We further study the opinion optimization problem by changing the initial opinions of a fixed number of nodes, which can be optimally solved in cubic time. We provide a nearly-linear time algorithm with an error guarantee to approximately solve the problem. Finally, we execute extensive experiments on sixteen real-life signed networks, which show that both of our algorithms are effective and efficient, and are scalable to massive graphs with over 20 million nodes.

关键词： Laplace equations Social networking (online) Vectors approximation algorithms Optimization Mathematical models Heuristic algorithms Graph algorithm opinion dynamics opinion optimization polarization signed graph social network

来源：评论

学校读者我要写书评

暂无评论

CORE-POLARIZATION EFFECTS FOR THE (6S2) S-1(0) -] (6S6P) P-3(1)O P-1(1)O TRANSITIONS IN HG-LIKE IONS

引用

JOURNAL OF PHYSICS B-ATOMIC MOLECULAR AND OPTICAL PHYSICS 1993年第15期26卷 2303-2309页

作者： CHOU, HS CHI, HC HUANG, KN ACAD SINICA INST ATOM & MOLEC SCITAIPEI 106TAIWAN NATL TAIWAN UNIV DEPT PHYSTAIPEI 106TAIWAN

Excitation energies and oscillator strengths from the S-1(0) ground state to the first P-3(1)o, and P-1(1)o excited states of Hg-like ions are calculated by using the multiconfiguration relativistic random-phase approximation including excitation channels from core electrons. The discrepancies between the theoretical and experimental results are much reduced for the oscillator strengths but more enhanced for the excitation energies when these core-polarization effects are taken into account.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive Hammerstein Filtering via Recursive Non-Convex Projection

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2022年 70卷 2869-2882页

作者： Liu, Zhaoting Li, Chunguang Hangzhou Dianzi Univ Sch Commun Engn Hangzhou 310018 Peoples R China Zhejiang Univ Coll Informat Sci & Elect Engn Hangzhou 310027 Peoples R China Zhejiang Univ Zhejiang Prov Key Lab Informat Proc Commun & Netw Hangzhou 310027 Peoples R China

Hammerstein model with a static nonlinearity followed by a linear filter is commonly used in numerous applications. This paper focuses on adaptive filtering techniques for parameter identification of Hammerstein systems and output prediction of nonlinear systems. By formulating the underlying filtering problem as a recursive bilinear least-squares optimization with the non-convex feasible region constraint, we develop a recursive non-convex projected least-squares (RncPLS) algorithm based on alternating direction method of multipliers (ADMM). The RncPLS algorithm alternates between implementing ridge regression and projecting on the non-convex feasible set, which successively refines the system parameters. The convergence and accuracy properties of the proposed RncPLS algorithm are theoretically investigated. Moreover, extensive simulation results in the context of system identification, nonlinear predication, and acoustic echo cancellation, are also included to demonstrate the performance characteristics of the proposed algorithm.

关键词： Signal processing algorithms Prediction algorithms Optimization Convex functions Adaptive systems Adaptation models approximation algorithms System identification nonlinear prediction adaptive filtering parameter estimation Hammerstein

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：