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

Efficient algorithms for Minimizing the Kirchhoff Index via Adding Edges

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhou, Xiaotian Zehmakan, Ahad N. Zhang, Zhongzhi Shanghai Key Laboratory of Intelligent Information Processing School of Computer Science Fudan University Shanghai200433 China Research Institute of Intelligent Complex Systems Fudan University Shanghai200433 China School of Computing Australian National University Canberra Australia

The Kirchhoff index, which is the sum of the resistance distance between every pair of nodes in a network, is a key metric for gauging network performance, where lower values signify enhanced performance. In this paper, we study the problem of minimizing the Kirchhoff index by adding edges. We first provide a greedy algorithm for solving this problem and give an analysis of its quality based on the bounds of the submodularity ratio and the curvature. Then, we introduce a gradient-based greedy algorithm as a new paradigm to solve this problem. To accelerate the computation cost, we leverage geometric properties, convex hull approximation, and approximation of the projected coordinate of each point. To further improve this algorithm, we use pre-pruning and fast update techniques, making it particularly suitable for large networks. Our proposed algorithms have nearly-linear time complexity. We provide extensive experiments on ten real networks to evaluate the quality of our algorithms. The results demonstrate that our proposed algorithms outperform the state-of-the-art methods in terms of efficiency and effectiveness. Moreover, our algorithms are scalable to large graphs with over 5 million nodes and 12 million edges. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Distributed algorithm for Cooperative Joint Localization and Tracking Using Multiple-Input Multiple-Output Radars

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Kitchen, Astrid Holm Filtenborg Brøndt, Mikkel Sebastian Lundsgaard Jensen, Marie Saugstrup Pedersen, Troels Westerkam, Anders Malthe Aalborg University Aalborg Denmark

—We propose a distributed joint localization and tracking algorithm using a message passing framework, for multiple-input multiple-output radars. We employ the mean field approach to derive an iterative algorithm. The obtained algorithm features a small communication overhead that scales linearly with the number of radars in the system. The proposed algorithm shows good estimation accuracy in two simulated scenarios even below 0 dB signal to noise ratio. In both cases the ground truth falls within the 95% confidence interval of the estimated posterior for the majority of the track. © 2025, CC BY.

关键词： consensus algorithm

Decentralized Inference for Spatial Data Using Low-Rank Models

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Shi, Jianwei Abdulah, Sameh Sun, Ying Genton, Marc G. Statistics Program King Abdullah University of Science and Technology Thuwal23955 Saudi Arabia

Advancements in information technology have enabled the creation of massive spatial datasets, driving the need for scalable and efficient computational methodologies. While offering viable solutions, centralized frameworks are limited by vulnerabilities such as single-point failures and communication bottlenecks. This paper presents a decentralized framework tailored for parameter inference in spatial low-rank models to address these challenges. A key obstacle arises from the spatial dependence among observations, which prevents the log-likelihood from being expressed as a summation—a critical requirement for decentralized optimization approaches. To overcome this challenge, we propose a novel objective function leveraging the evidence lower bound, which facilitates the use of decentralized optimization techniques. Our approach employs a block descent method integrated with multi-consensus and dynamic consensus averaging for effective parameter optimization. We prove the convexity of the new objective function in the vicinity of the true parameters, ensuring the convergence of the proposed method. Additionally, we present the first theoretical results establishing the consistency and asymptotic normality of the estimator within the context of spatial low-rank models. Extensive simulations and real-world data experiments corroborate these theoretical findings, showcasing the robustness and scalability of the *** Codes 62M30 © 2025, CC BY.

关键词： consensus algorithm

Generalized exchange cluster algorithm to compute efficiently covariances and susceptibilities in Monte Carlo

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Assaraf, Roland Chevreau, Hilaire Sorbonne Université CNRS Paris France

We present a Monte Carlo method to compute efficiently susceptibilites or covariances of two physical variables. The method relies on a generalization of the exchange cluster algorithm to any model of interacting particles with any 2-body interactions. The principle is to select clusters of variables belonging to two independent replicas of the system. An improved estimator of the covariance of two physical variables (in one replica) is then proposed. This estimator has the zero-variance property in the limit where these variables are independent. In practice the scaling of the statistical fluctuations as a function of the number of degrees of freedom N is reduced from O(N2) to O(N). This lower scaling is illustrated on a Lennard Jones model. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Secant Line Search for Frank-Wolfe algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Hendrych, Deborah Besançon, Mathieu Martínez-Rubio, David Pokutta, Sebastian Zuse Institute Berlin Berlin Germany Berlin Institute of Technology Berlin Germany Université Grenoble Alpes Inria Laboratoire d’Informatique de Grenoble Grenoble France Signal Theory and Communications Department Carlos III University of Madrid Madrid Spain

We present a new step-size strategy based on the secant method for Frank-Wolfe algorithms. This strategy, which requires mild assumptions about the function under consideration, can be applied to any Frank-Wolfe algorithm. It is as effective as full line search and, in particular, allows for adapting to the local smoothness of the function, such as in Pedregosa et al. (2020), but comes with a significantly reduced computational cost, leading to higher effective rates of convergence. We provide theoretical guarantees and demonstrate the effectiveness of the strategy through numerical experiments. © 2025, CC BY.

关键词： consensus algorithm

New and Improved Bounds for Markov Paging

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Pabbaraju, Chirag Vakilian, Ali Stanford University United States Toyota Technological Institute Chicago United States

In the Markov paging model, one assumes that page requests are drawn from a Markov chain over the pages in memory, and the goal is to maintain a fast cache that suffers few page faults in expectation. While computing the optimal online algorithm (OPT) for this problem naively takes time exponential in the size of the cache, the best-known polynomial-time approximation algorithm is the dominating distribution algorithm due to Lund, Phillips and Reingold (FOCS 1994), who showed that the algorithm is 4-competitive against OPT. We substantially improve their analysis and show that the dominating distribution algorithm is in fact 2-competitive against OPT. We also show a lower bound of 1.5907-competitiveness for this algorithm—to the best of our knowledge, no such lower bound was previously known. © 2025, CC BY.

关键词： consensus algorithm

Multi-Stage Active Sequential Hypothesis Testing with Clustered Hypotheses

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Vershinin, George Cohen, Asaf Gurewitz, Omer The School of Electrical and Computer Engineering Ben-Gurion University of the Negev Israel

We consider the problem where an active Decision-Maker (DM) is tasked to identify the true hypothesis using as few as possible observations while maintaining accuracy. The DM collects observations according to its determined actions and knows the distributions under each hypothesis. We propose a deterministic and adaptive multi-stage hypothesis-elimination strategy where the DM selects an action, applies it repeatedly, and discards hypotheses in light of its obtained observations. The DM selects actions based on maximal separation expressed by the distance between the parameter vectors of each distribution under each hypothesis. Close distributions can be clustered, simplifying the search and significantly reducing the number of required observations. Our algorithms achieve vanishing Average Bayes Risk (ABR) as the error probability approaches zero, i.e., the algorithm is asymptotically optimal. Furthermore, we show that the ABR is bounded when the number of hypotheses grows. Simulations are carried out to evaluate the algorithm’s performance compared to another multi-stage hypothesis-elimination algorithm, where an improvement of several orders of magnitude in the mean number of observations required is observed. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Fair Clustering in the Sliding Window Model

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cohen-Addad, Vincent Jiang, Shaofeng H.-C. Yang, Qiaoyuan Zhang, Yubo Zhou, Samson Google Research NYC United States Peking University China Texas A&M University United States

We study streaming algorithms for proportionally fair clustering, a notion originally suggested by [CKLV17], in the sliding window model. We show that although there exist efficient streaming algorithms in the insertion-only model, surprisingly no algorithm can achieve finite multiplicative ratio without violating the fairness constraint in the sliding window. Hence, the problem of fair clustering is a rare separation between the insertion-only streaming model and the sliding window model. On the other hand, we show that if the fairness constraint is relaxed by a multiplicative (1 + Ε) factor, there exists a (1 + Ε)-approximate sliding window algorithm that uses poly(kΕ−1 log n) space. This achieves essentially the best parameters (up to degree in the polynomial) provided the aforementioned lower bound. We also implement a number of empirical evaluations on real datasets to complement our theoretical results. © 2025, CC BY.

关键词： consensus algorithm

On Tradeoffs in Learning-Augmented algorithms

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Benomar, Ziyad Perchet, Vianney CREST Ecole polytechnique ENSAE Fairplay joint team Palaiseau France CREST ENSAE Criteo AI LAB Fairplay joint team Paris France

The field of learning-augmented algorithms has gained significant attention in recent years. These algorithms, using potentially inaccurate predictions, must exhibit three key properties: consistency, robustness, and smoothness. In scenarios where distributional information about predictions is available, a strong expected performance is required. Typically, the design of these algorithms involves a natural tradeoff between consistency and robustness, and previous works aimed to achieve Pareto-optimal tradeoffs for specific problems. However, in some settings, this comes at the expense of smoothness. In this paper, we demonstrate that certain problems involve multiple tradeoffs between consistency, robustness, smoothness, and average performance. © 2025, CC BY.

关键词： consensus algorithm