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

Online Bidding algorithms with Strict Return on Spend (ROS) Constraint

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Vaze, Rahul Sinha, Abhishek School of Technology and Computer Science Tata Institute of Fundamental Research Mumbai400005 India

Auto-bidding problem under a strict return-on-spend constraint (ROSC) is considered, where an algorithm has to make decisions about how much to bid for an ad slot depending on the revealed value, and the hidden allocation and payment function that describes the probability of winning the ad-slot depending on its bid. The objective of an algorithm is to maximize the expected utility (product of ad value and probability of winning the ad slot) summed across all time slots subject to the total expected payment being less than the total expected utility, called the ROSC. A (surprising) impossibility result is derived that shows that no online algorithm can achieve a sub-linear regret even when the value, allocation and payment function are drawn i.i.d. from an unknown distribution. The problem is non-trivial even when the revealed value remains constant across time slots, and an algorithm with regret guarantee that is optimal up to logarithmic factor is derived. © 2025, CC BY-NC-ND.

关键词： consensus algorithm

Genetic algorithm with Border Trades (GAB)

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Lyu, Qingchuan Department of Computer Science Georgia Institute of Technology AtlantaGA United States Visa Inc. Foster CityCA United States

This paper introduces a novel approach to improving Genetic algorithms (GA) in large or complex problem spaces by incorporating new chromosome patterns in the breeding process through border trade activities. These strategies increase chromosome diversity, preventing premature convergence and enhancing the GA’s ability to explore the solution space more effectively. Empirical evidence demonstrates significant improvements in convergence behavior. This approach offers a promising pathway to addressing challenges in optimizing large or complex problem domains. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Convergence Analysis of a Greedy algorithm for Conditioning Gaussian Random Variables

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Winkle, Daniel Steinwart, Ingo Haasdonk, Bernard University of Stuttgart Faculty 8: Mathematics and Physics Stuttgart Germany

In the context of Gaussian conditioning, greedy algorithms iteratively select the most informative measurements, given an observed Gaussian random variable. However, the convergence analysis for conditioning Gaussian random variables remains an open problem. We adress this by introducing an operator M that allows us to transfer convergence rates of the observed Gaussian random variable approximation onto the conditional Gaussian random variable. Furthermore we apply greedy methods from approximation theory to obtain convergence rates. These greedy methods have already demonstrated optimal convergence rates within the setting of kernel based function approximation. In this paper, we establish an upper bound on the convergence rates concerning the norm of the approximation error of the conditional covariance operator. © 2025, CC0.

关键词： consensus algorithm

Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Peng, Bo Tang, Zhihao Gavin ITCS Shanghai University of Finance and Economics China

We revisit the celebrated Ranking algorithm by Karp, Vazirani, and Vazirani (STOC 1990) for online bipartite matching under the random arrival model, that is shown to be 0.696-competitive for unweighted graphs by Mahdian and Yan (STOC 2011) and 0.662-competitive for vertex-weighted graphs by Jin and Williamson (WINE 2021). In this work, we explore the limitation of the primal-dual analysis of Ranking and aim to bridge the gap between unweighted and vertex-weighted graphs. We show that the competitive ratio of Ranking is between 0.686 and 0.703, under our current knowledge of Ranking and the framework of primal-dual analysis. This confirms a conjecture by Huang, Tang, Wu, and Zhang (TALG 2019), stating that the primal-dual analysis could lead to a competitive ratio that is very close to 0.696. Our analysis involves proper discretizations of a variational problem and uses LP solver to pin down the numerical number. As a bonus of our discretization approach, our competitive analysis of Ranking applies to a more relaxed random arrival model. E.g., we show that even when each online vertex arrives independently at an early or late stage, the Ranking algorithm is at least 0.665-competitive, beating the 1 − 1/e ≈ 0.632 competitive ratio under the adversarial arrival model. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Multi-objective Pseudo Boolean Functions in Runtime Analysis: A Review

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Liang, Zimin Li, Miqing School of Computer Science University of Birmingham Edgbaston BirminghamB15 2TT United Kingdom

Recently, there has been growing interest within the theoretical community in analytically studying multi-objective evolutionary algorithms. This runtime analysis-focused research can help formally understand algorithm behaviour, explain empirical observations, and provide theoretical insights to support algorithm development and exploration. However, the test problems commonly used in the theoretical analysis are predominantly limited to problems with heavy "artificial" characteristics (e.g., symmetric objectives and linear Pareto fronts), which may not be able to well represent realistic scenarios. In this paper, we survey commonly used multi-objective functions in the theory domain and systematically review their features, limitations and implications to practical use. Moreover, we present several new functions with more realistic features, such as local optimality and nonlinearity of the Pareto front, through simply mixing and matching classical single-objective functions in the area (e.g., LeadingOnes, Jump and RoyalRoad). We hope these functions can enrich the existing test problem suites, and strengthen the connection between theoretic and practical research. © 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

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

Computing adjoint mismatch of linear maps

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Bresch, Jonas Lorenz, Dirk A. Schneppe, Felix Winkler, Maximilian Institute of Mathematics Technical University Berlin Straße des 17. Juni 136 Berlin10623 Germany Center for Industrial Mathematics Fachbereich 3 University of Bremen Postfach 33 04 40 Bremen28334 Germany

This paper considers the problem of detecting adjoint mismatch for two linear maps. To clarify, this means that we aim to calculate the operator norm for the difference of two linear maps, where for one we only have a black-box implementation for the evaluation of the map, and for the other we only have a black-box for the evaluation of the adjoint map. We give two stochastic algorithms for which we prove the almost sure convergence to the operator norm. The algorithm is a random search method for a generalization of the Rayleigh quotient and uses optimal step sizes. Additionally, a convergence analysis is done for the corresponding singular vector and the respective eigenvalue *** Codes 65F35, 15A60, 68W20 Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Semi-Streaming algorithms for Hypergraph Matching

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Reinstädtler, Henrik Ferdous, S.M. Pothen, Alex Uçar, Bora Schulz, Christian Heidelberg University Germany Pacific Northwest National Laboratory RichlandWA United States Purdue University West LafayetteIN United States CNRS and LIP UMR5668 CNRS ENS de Lyon Inria UCBL1 France Georgia Institute of Technology AtlantaGA United States

We propose two one-pass streaming algorithms for the NP-hard hypergraph matching problem. The first algorithm stores a small subset of potential matching edges in a stack using dual variables to select edges. It has an approximation guarantee of d(1+1Ε) and requires O((n/Ε) log2 n) bits of memory. The second algorithm computes, stores, and updates a single matching as the edges stream, with an approximation ratio dependent on a parameter α. Its best approximation ratio is (2d−1)+21√d(d−1) , and it requires only O(n) memory. We have implemented both algorithms and have engineered variants for optimizing matching weights, memory consumption, and running times. These include relaxations of the rule for admitting edges into the stack and using a second pass to improve the weight. The evaluation is done on large-sized hypergraphs from circuit design and sparse matrix computations. Our results show that the streaming algorithms achieve much better approximation factors in practice than the worst-case bounds, reducing memory required by up to 50 times and outperforming the offline Greedy algorithm. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm