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

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

A Stochastic Conjugate Subgradient algorithm for Two-stage Stochastic Programming

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhang, Di Sen, Suvrajeet Department of Industrial and System Engineering University of Southern California Los AngelesCA United States

Stochastic Optimization is a cornerstone of operations research, providing a framework to solve optimization problems under uncertainty. Despite the development of numerous algorithms to tackle these problems, several persistent challenges remain, including: (i) selecting an appropriate sample size, (ii) determining an effective search direction, and (iii) choosing a proper step size. This paper introduces a comprehensive framework, the Stochastic Conjugate Subgradient (SCS) framework, designed to systematically address these challenges. Specifically, The SCS framework offers structured approaches to determining the sample size, the search direction, and the step size. By integrating various stochastic algorithms within the SCS framework, we have developed a novel stochastic algorithm for two-stage stochastic programming. The convergence and convergence rates of the algorithm have been rigorously established, with preliminary computational results support the theoretical analysis. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Impatient Bandits: Optimizing for the Long-Term Without Delay

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhang, Kelly W. Baldwin-McDonald, Thomas Ciosek, Kamil Maystre, Lucas Russo, Daniel Imperial College London United Kingdom University of Manchester United Kingdom Spotify United States UiPath United States Columbia University United States

Increasingly, recommender systems are tasked with improving users’ long-term satisfaction. In this context, we study a content exploration task, which we formalize as a bandit problem with delayed rewards. There is an apparent trade-off in choosing the learning signal: waiting for the full reward to become available might take several weeks, slowing the rate of learning, whereas using short-term proxy rewards reflects the actual long-term goal only imperfectly. First, we develop a predictive model of delayed rewards that incorporates all information obtained to date. Rewards as well as shorter-term surrogate outcomes are combined through a Bayesian filter to obtain a probabilistic belief. Second, we devise a bandit algorithm that quickly learns to identify content aligned with long-term success using this new predictive model. We prove a regret bound for our algorithm that depends on the Value of Progressive Feedback, an information theoretic metric that captures the quality of short-term leading indicators that are observed prior to the long-term reward. We apply our approach to a podcast recommendation problem, where we seek to recommend shows that users engage with repeatedly over two months. We empirically validate that our approach significantly outperforms methods that optimize for short-term proxies or rely solely on delayed rewards, as demonstrated by an A/B test in a recommendation system that serves hundreds of millions of users. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

Potential-Based Greedy Matching for Dynamic Delivery Pooling

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Ma, Hongyao Ma, Will Romero, Matias Graduate School of Business Columbia University New YorkNY10027 United States

We study the pooling of multiple orders into a single trip, a strategy widely adopted by online delivery platforms. When an order has to be dispatched, the platform must determine which (if any) of the other available orders to pool it with, weighing the immediate efficiency gains against the uncertain, differential benefits of holding each order for future pooling opportunities. In this paper, we demonstrate the effectiveness of using the length of each job as its opportunity cost, via a potential-based greedy algorithm (PB). The algorithm is very simple, pooling each departing job with the available job that maximizes the savings in travel distance minus a half of its distance (i.e. the potential). On the theoretical front, we show that PB significantly improves upon a naive greedy algorithm in terms of worst-case performance: as the density of the market increases, the regret per job vanishes under PB but remains constant under naive greedy. In addition, we show that the potential approximates the marginal cost of dispatching each job in a stochastic setting with sufficient density. Moreover, we conduct extensive numerical experiments and show that despite its simplicity, PB consistently outperforms a number of benchmark algorithms, including (i) batching-based heuristics that are widely used in practice, and (ii) forecast-aware heuristics that estimate the marginal costs of dispatching different jobs using historical data. © 2025, CC BY.

关键词： consensus algorithm

A parallel algorithm for the odd two-face shortest k-disjoint path problem

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Chakraborty, Srijan Datta, Samir Chennai Mathematical Institute India

The shortest Disjoint Path problem (SDPP) requires us to find pairwise vertex disjoint paths between k designated pairs of terminal vertices such that the sum of the path lengths is minimum. The focus here is on SDPP restricted to planar graphs where all terminals are arbitrarily partitioned over two distinct faces with the additional restriction that each face is required to contain an odd number of terminals. We call this problem the Odd two-face planar SDPP. It is shown that this problem is solvable in randomized polynomial time and even in RNC. This is the first parallel (or even polynomial time) solution for the problem. Our algorithm combines ideas from the randomized solution for 2-SDPP by Björklund and Huslfeldt with its parallelization by Datta and Jaiswal along with the deterministic algorithm for One-face planar SDPP by Datta, Iyer, Kulkarni and Mukherjee. The proof uses a combination of two involutions to reduce a system of linear equations modulo a power of 2 to a system of triangular form that is, therefore, invertible. This, in turn, is proved by showing that the matrix of the equations, can be interpreted as (the adjacency matrix of) a directed acyclic graph (DAG). While our algorithm is primarily algebraic the proof remains combinatorial. We also give a parallel algorithm for the (A + B)-SDPP introduced by Hirai and Namba. © 2025, CC BY.

关键词： consensus algorithm

Revisited Convergence of Dolev et al’s BFS Spanning Tree algorithm

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Altisen, Karine Bozga, Marius Univ. Grenoble Alpes CNRS Grenoble INP VERIMAG Grenoble38000 France

We provide a constructive proof for the convergence of Dolev et al’s BFS spanning tree algorithm running under the general assumption of an unfair daemon. Already known proofs of this algorithm are either using non-constructive principles (e.g., proofs by contradiction) or are restricted to less general execution daemons (e.g., weakly fair). In this work, we address these limitations by defining the well-founded orders and potential functions ensuring convergence in the general case. The proof has been fully formalized in PADEC, a Coq-based framework for certification of self-stabilization algorithm. © 2025, CC BY.

关键词： 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

A note on algorithmic approach to inverting formal power series

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Adamus, Elżbieta Faculty of Applied Mathematics AGH University of Science and Technology al. Mickiewicza 30 Kraków30-059 Poland

In [2] an effective algorithm for inverting polynomial automorphisms was proposed. Some further improvements and an estimation of the computational complexity for the algorithm mentioned above were discussed in [1]. We extend its application to the case of formal power series over a field of arbitrary characteristic and illustrate the proposed approach with some *** Codes 13F25 © 2025, CC BY-NC-ND.

关键词： 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