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

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Kolman, Petr Department of Applied Mathematics Faculty of Mathematics and Physics Charles University Prague Czech Republic

ISBN: (纸本)9783959773652

The Spanning Tree Congestion (STC) problem is the following NP-hard problem: given a graph G, construct a spanning tree T of G minimizing its maximum edge congestion where the congestion of an edge e ∈ T is the number of edges uv in G such that the unique path between u and v in T passes through e;the optimal value for a given graph G is denoted STC(G). It is known that every spanning tree is an n/2-approximation for the STC problem. A longstanding problem is to design a better approximation algorithm. Our contribution towards this goal is an O(∆ · log3/2 n)-approximation algorithm where ∆ is the maximum degree in G and n the number of vertices. For graphs with a maximum degree bounded by a polylog of the number of vertices, this is an exponential improvement over the previous best approximation. Our main tool for the algorithm is a new lower bound on the spanning tree congestion which is of independent interest. Denoting by hb(G) the hereditary bisection of G which is the maximum bisection width over all subgraphs of G, we prove that for every graph G, STC(G) ≥ Ω(hb(G)/∆). © Petr Kolman.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Projection-Based algorithms for Tip Decomposition on Dynamic Bipartite Graphs

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2025年第2期37卷 626-640页

作者： Weng, Tongfeng Liu, Yumeng Sha, Mo Chen, Xinyuan Zhou, Xu Li, Kenli Tan, Kian-Lee Natl Univ Singapore Sch Comp Singapore 117417 Singapore Chinese Acad Sci Inst Software Beijing 100045 Peoples R China Alibaba Cloud Singapore 189554 Singapore Nanjing Univ Aeronaut & Astronaut Coll Automat Engn Nanjing 210016 Peoples R China Hunan Univ Coll Comp Sci & Elect Engn Changsha 410082 Peoples R China

This paper addresses the pressing need for effective k-tips decomposition in dynamic bipartite graphs, a crucial aspect of real-time applications that analyze and mine binary relationship patterns. Recognizing the dynamic nature of these graphs, our study is the first to provide a solution for k-tips decomposition in such evolving environments. We introduce a pioneering projection-based algorithm, coupled with advanced incremental maintenance strategies for edge modifications, tailored specifically for dynamic graphs. This novel approach not only fills a significant gap in the analysis of dynamic bipartite graphs but also substantially enhances the accuracy and timeliness of data-driven decisions in critical areas like public health. Our contributions set a new benchmark in the field, paving the way for more nuanced and responsive analyses in various domains reliant on dynamic data interpretation.

关键词： Bipartite graph Heuristic algorithms Maintenance Accuracy Pandemics Toy manufacturing industry Resource management Government Dynamic scheduling approximation algorithms community detection dynamic graph incremental algorithm tip number

来源：评论

学校读者我要写书评

暂无评论

Finding diameter-reducing shortcuts in trees

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 153卷

作者： Bilo, Davide Guala, Luciano Leucci, Stefano Sciarria, Luca Pepe Univ Roma Tor Vergata Dept Enterprise Engn Rome Italy Univ Aquila Dept Informat Engn Comp Sci & Math Laquila Italy

In the k-Diameter-Optimally Augmenting Tree Problem we are given a tree T of n vertices embedded in an unknown metric space. An oracle can report the cost of any edge in constant time, and we want to augment T with k shortcuts to minimize the resulting diameter. When k = 1, O(n log n)-time algorithms exist for paths and trees. We show that o(n(2)) queries cannot provide a better than 10/9-approximation for trees when k >= 3. For any constant epsilon > 0, we design a linear-time (1 + epsilon)-approximation algorithm for paths when k = o(root logn), thus establishing a dichotomy between paths and trees for k >= 3. Our algorithm employs an ad-hoc data structure, which we also use in a linear-time 4approximation algorithm for trees, and to compute the diameter of (possibly non-metric) graphs with n + k - 1 edges in time O (nk log n). (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).

关键词： Tree diameter augmentation Fast diameter computation approximation algorithms Time-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

Anomaly Detection With Infinite Set Dictionary Learning and Atom Dimension Adaptation

引用

IEEE ACCESS 2025年 13卷 36233-36246页

作者： Baltoiu, Andra Ilie-Ablachim, Denis C. Dumitrescu, Bogdan Natl Univ Sci & Technol POLITEHNICA Bucharest Fac Automat Control & Comp Bucharest 060042 Romania

Recent work on dictionary learning with set-atoms has shown benefits in anomaly detection. Instead of viewing an atom as a single vector, these methods allow building sparse representations with atoms taken from a set around a central vector;the set can be a cone or may have a probability distribution associated to it. We propose a method for adaptively adjusting the size of set-atoms in Gaussian and cone dictionary learning. The purpose of the algorithm is to match the atom sizes with their contribution in representing the signals. The proposed algorithm not only decreases the representation error, but also improves anomaly detection, for a class of anomalies called 'dependency'. We obtain better detection performance than state-of-the-art methods.

关键词： Atomic measurements Dictionaries Anomaly detection Standards Vectors Training Natural language processing Feature extraction approximation algorithms Stress Dictionary learning cone atoms Gaussian atoms anomaly detection

来源：评论

学校读者我要写书评

暂无评论

Dispersion problem on a convex polygon

引用

INFORMATION PROCESSING LETTERS 2025年 187卷

作者： Mishra, Pawan K. Rao, S. V. Das, Gautam K. Indian Inst Informat Technolgy Guwahati Dept Comp Sci & Engn Gauhati India Indian Inst Technol Guwahati Dept Comp Sci & Engn Gauhati India Indian Inst Technol Guwahati Dept Math Gauhati India

Given a set P = {p(1), p(2), ... , p(n)} of n points in R-2 and a positive integer k (<= n), we wish to find a subset S of P of size k such that the cost of a subset S, cost(S) = min{d(p, q) | p, q is an element of S}, is maximized, where d(p, q) is the Euclidean distance between two points p and q. The problem is called the max-min k-dispersion problem. In this article, we consider the max-min k-dispersion problem, where a given set P of n points are vertices of a convex polygon. We refer to this variant of the problem as the convex k-dispersion problem. We propose an 1.733-factor approximation algorithm for the convex k-dispersion problem. In addition, we study the convex k-dispersion problem for k = 4. We propose an iterative algorithm that returns an optimal solution of size 4 in O(n(3)) time.

关键词： Dispersion problem Convex polygon approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed ADMM With Linear Updates Over Directed Networks

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2025年第2期12卷 1396-1407页

作者： Rokade, Kiran Kalaimani, Rachel Kalpana Cornell Univ Sch Elect & Comp Engn Ithaca NY 14850 USA Indian Inst Technol Madras Dept Elect Engn Chennai 600036 Tamil Nadu India

Distributed optimization over a network of agents is ubiquitous in applications such as power system, robotics and statistical learning. In many settings, the communication network is directed, i.e., the communication links between agents are unidirectional. While several variations of gradient-descent-based primal methods have been proposed for distributed optimization over directed networks, an extension of dual-ascent methods to directed networks remains a less-explored area. In this paper, we propose a distributed version of the Alternating Direction Method of Multipliers (ADMM) with linear updates for directed networks using balancing weights, called BW-DADMM (Balancing Weights Directed ADMM). We show that if the objective function of the minimization problem is smooth and strongly convex, then BW-DADMM achieves a geometric rate of convergence to the optimal point. Our algorithm exploits the robustness inherent to ADMM by not enforcing accurate consensus, thereby significantly improving the convergence rate. We illustrate this by numerical examples, where we compare the performance of BW-DADMM with that of state-of-the-art ADMM methods over directed graphs.

关键词： Convex functions Optimization Directed graphs Convergence Standards Vectors Linear programming approximation algorithms Statistical learning Robustness Alternating Direction Method of Multipliers (ADMM) dual-ascent directed graphs distributed computing parallel computing

来源：评论

学校读者我要写书评

暂无评论

Learning-Based Adaptive Optimal Tracking Control for Flexible-Joint Robots With Quantized States: Theory and Experiment

引用

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS 2025年

作者： Sun, Wei Xie, Shiyu Su, Shun-Feng Liaocheng Univ Sch Math Sci Liaocheng 252000 Peoples R China Natl Taiwan Univ Sci & Technol Dept Elect Engn Taipei 106 Taiwan

This study aims to overcome a problem in the position tracking control of flexible-joint robots: realizing good position tracking for desired signal while conserving bandwidth and minimizing cost. The primary obstacle is that the weight update laws developed through the reinforcement learning (RL) scheme fail to guarantee a bounded quantized signal. Hence, an optimal controller is designed based on the bounded effect of the proposed fuzzy basis function, with the signal discontinuity problem caused by the quantized virtual controller addressed via command filter technique. Meanwhile, an adaptive law is designed to replace the model identification, allowing it to handle unknown structure impacts and reduce approximation behaviors. Besides, we establish an improved compensation signal to maintain boundedness via a first-order low-pass filter. Notably, the developed scheme guarantees boundedness of all signals. Finally, the justification of the proposed scheme can be further confirmed by the simulation and the comparison experiment on Quanser hardware experiment platform, which shows that the developed technology can achieve desired tracking performance.

关键词： Robots Fuzzy logic Quantization (signal) Vectors Process control Sun Backstepping approximation algorithms Adaptation models Rotors Flexible-joint robots optimal control reinforcement learning (RL) state quantization

来源：评论

学校读者我要写书评

暂无评论

On Hybrid Detection of Wireless Communications Over Interference Channels: A Generalized Framework

引用

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

作者： Yuan, Weijie Li, Shuangyang Wei, Zhiqiang Li, Yonghui Fan, Pingzhi Southern Univ Sci & Technol Sch Syst Design & Intelligent Mfg Shenzhen 518055 Peoples R China Tech Univ Berlin Dept Elect Engn & Comp Sci D-10587 Berlin Germany Xi An Jiao Tong Univ Sch Math & Stat Xian 710049 Peoples R China Univ Sydney Sch Elect & Informat Engn Sydney NSW 2006 Australia Southwest Jiaotong Univ Inst Mobile Commun Chengdu 611756 Peoples R China

Modern wireless systems face interference due to rising spectrum efficiency demands and increasingly aggressive network designs. Despite its optimality, the huge complexity of the maximum likelihood (ML) detection hinders its deployment in the future wireless communication systems, which require low latency and high energy efficiency. In this paper, we develop a novel generalized framework for data detection in interference channels. In particular, we factorize the joint likelihood function of the transmitted symbols to obtain the marginal distribution of a single symbol following the sum-product (SP) algorithm. Motivated by the fact that the complexity of the SP algorithm is dominated by the summation process, we introduce Gaussian and Gaussian mixture models to reduce the state space of symbols, which helps to reduce the detection complexity. The proposed hybrid detection framework consists of three kinds of symbol distributions, i.e., original discrete, Gaussian, and Gaussian mixture distributions. To strike a balance between complexity and error performance, we can simply modify the components of different symbol distributions, offering high flexibility in practical applications. Furthermore, we analyze the performance of our proposed detection scheme and discuss the design guidelines for the mixture Gaussian messages. Simulation results demonstrated the effectiveness of the proposed algorithm.

关键词： Complexity theory Symbols Message passing Interference Detectors approximation algorithms Wireless communication Convergence Interference channels Electronic mail Interference channel symbol detection factor graph Gaussian mixture model

来源：评论

学校读者我要写书评

暂无评论

StriPre: A VM Disk Migration Prefetching Algorithm

引用

IEEE ACCESS 2025年 13卷 37514-37521页

作者： Chen, Yuchi Xiong, Tianlei Shanghai Jiao Tong Univ Shanghai 200240 Peoples R China

Virtual machine (VM) cross-cloud migration involves relocating virtual machine instances between different cloud environments, offering advantages such as improved scalability, disaster recovery capabilities, and efficient resource allocation optimization. Two strategies exist for live migration: "pre-copy" and "post-copy". These methods are initially applied to memory migration, but their drawbacks, such as data redundancy and poor virtual machine IO performance are amplified in cross-cloud disk migration due to high network latency, limited transmission bandwidth, and large data volumes, thereby constraining the performance of cross-cloud virtual machine migration. To reduce the performance impact caused by the latency of cross-cloud migration, we present StriPre in this paper. StriPre is a prefetching algorithm based on disk access and striped feature design, leveraging the alternating characteristics of disk accesses and performing striping recognition on IO requests. Compared to the commonly used sequential prefetching in memory, StriPre's prefetch hit rate has increased by 1.2x to 2.2x. Our experiments have demonstrated that StriPre can effectively reduce the virtual machine startup time during cross-cloud disk migration. Under extreme cross-cloud latency of 160ms, StriPre can shorten the startup time by 3.48x compared to sequential prefetching.

关键词： Prefetching Virtual machines Costs Cloud computing Prediction algorithms approximation algorithms Real-time systems Kernel Business Accuracy Cross-cloud migration data prefetch algorithm cloud computing

来源：评论

学校读者我要写书评

暂无评论

Shared Recurrence Floating-Point Divide/Sqrt and Integer Divide/Remainder With Early Termination

引用

IEEE TRANSACTIONS ON COMPUTERS 2025年第2期74卷 740-748页

作者： Kim, Kevin Parry, Katherine Harris, David Turek, Cedar Maiuolo, Alessandro Thompson, Rose Stine, James Harvey Mudd Coll Claremont CA 91711 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Oklahoma State Univ Stillwater OK 74078 USA

Division, square root, and remainder are fundamental operations required by most computer systems. Floating-point and integer operations are commonly performed on separate datapaths. This paper presents the first detailed implementation of a shared recurrence unit that supports floating-point division/square root and integer division/remainder. It supports early termination and shares the normalization shifter needed for integer and subnormal inputs. Synthesis results show that shared double-precision dividers producing at least 4 bits per cycle are 9 - 18% smaller and 3 - 16% faster than separate integer and floating-point units.

关键词： Optical wavelength conversion Hardware Logic Computers approximation algorithms Adders Art Three-dimensional displays Reduced instruction set computing Computer architecture Division square root remainder SRT early termination

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：