On Parallel External-Memory Bidirectional Search

• URL: http://arxiv.org/abs/2412.21104v2
• Date: Tue, 31 Dec 2024 08:00:57 GMT
• Title: On Parallel External-Memory Bidirectional Search
• Authors: Lior Siag, Shahaf S. Shperberg, Ariel Felner, Nathan R. Sturtevant,
• Abstract summary: This paper presents a framework that integrates uni- and bi-directional best-first search algorithms.<n>We then develop a PEM variant of the state-of-the-art bidirectional search (BiHS) algorithm BAE* (PEM-BAE*)<n> Empirical evaluation shows that PEM-BAE* outperforms the PEM variants of A* and the MM algorithm, as well as a parallel variant of IDA*.
• Score: 16.87919636127611
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Parallelization and External Memory (PEM) techniques have significantly enhanced the capabilities of search algorithms when solving large-scale problems. Previous research on PEM has primarily centered on unidirectional algorithms, with only one publication on bidirectional PEM that focuses on the meet-in-the-middle (MM) algorithm. Building upon this foundation, this paper presents a framework that integrates both uni- and bi-directional best-first search algorithms into this framework. We then develop a PEM variant of the state-of-the-art bidirectional heuristic search (BiHS) algorithm BAE* (PEM-BAE*). As previous work on BiHS did not focus on scaling problem sizes, this work enables us to evaluate bidirectional algorithms on hard problems. Empirical evaluation shows that PEM-BAE* outperforms the PEM variants of A* and the MM algorithm, as well as a parallel variant of IDA*. These findings mark a significant milestone, revealing that bidirectional search algorithms clearly outperform unidirectional search algorithms across several domains, even when equipped with state-of-the-art heuristics.

Related papers

• Bidirectional Bounded-Suboptimal Heuristic Search with Consistent Heuristics [7.049213272184215]
  This paper focuses on bounded-suboptimal bidirectional search, where a bound on the suboptimality of the solution cost is specified.<n>We build upon the state-of-the-art optimal bidirectional search algorithm, BAE*, and introduce several variants of BAE* specifically tailored for the bounded-suboptimal context.
  arXiv  Detail & Related papers  (2025-11-13T12:56:35Z)
• AlphaResearch: Accelerating New Algorithm Discovery with Language Models [60.502137348923156]
  Large language models have made significant progress in complex but easy-to-verify problems, yet they still struggle with discovering the unknown.<n>We present textbfAlphaResearch, an autonomous research agent designed to discover new algorithms on open-ended problems.
  arXiv  Detail & Related papers  (2025-11-11T18:03:22Z)
• Hybrid ACO-CI Algorithm for Beam Design problems [0.4397520291340694]
  A novel hybrid version of the Ant colony optimization (ACO) method is developed using the sample space reduction technique of the Cohort Intelligence (CI) algorithm. The proposed work could be investigate for real world applications encompassing domains of engineering, and health care problems.
  arXiv  Detail & Related papers  (2023-03-29T04:37:14Z)
• A Gold Standard Dataset for the Reviewer Assignment Problem [117.59690218507565]
  "Similarity score" is a numerical estimate of the expertise of a reviewer in reviewing a paper. Our dataset consists of 477 self-reported expertise scores provided by 58 researchers. For the task of ordering two papers in terms of their relevance for a reviewer, the error rates range from 12%-30% in easy cases to 36%-43% in hard cases.
  arXiv  Detail & Related papers  (2023-03-23T16:15:03Z)
• Empirical Evaluation of Project Scheduling Algorithms for Maximization of the Net Present Value [0.0]
  This paper presents an empirical performance analysis of three project scheduling algorithms. The selected algorithms are: Recursive Search (RS), Steepest Ascent Approach (SAA) and Hybrid Search (HS)
  arXiv  Detail & Related papers  (2022-07-05T03:01:33Z)
• A survey on multi-objective hyperparameter optimization algorithms for Machine Learning [62.997667081978825]
  This article presents a systematic survey of the literature published between 2014 and 2020 on multi-objective HPO algorithms. We distinguish between metaheuristic-based algorithms, metamodel-based algorithms, and approaches using a mixture of both. We also discuss the quality metrics used to compare multi-objective HPO procedures and present future research directions.
  arXiv  Detail & Related papers  (2021-11-23T10:22:30Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  Bilevel optimization (BO) has arisen as a powerful tool for solving many modern machine learning problems. Existing gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations. We propose a novel BO algorithm, which adopts Evolution Strategies (ES) based method to approximate the response Jacobian matrix in the hypergradient of BO.
  arXiv  Detail & Related papers  (2021-10-13T19:36:50Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Critical Analysis: Bat Algorithm based Investigation and Application on Several Domains [1.1802674324027231]
  The idea of the algorithm was taken from the echolocation ability of bats. Bat Algorithm is given in-depth in terms of backgrounds, characteristics, limitations.
  arXiv  Detail & Related papers  (2021-01-18T19:25:12Z)
• On Population-Based Algorithms for Distributed Constraint Optimization Problems [12.21350091202884]
  We study an emerging class of incomplete algorithms that are broadly termed as population-based algorithms. Our first approach, Anytime Evolutionary DCOP or AED, exploits evolutionary optimization meta-heuristics to solve DCOPs. While in our second contribution, we show that population-based approaches can be combined with local search approaches.
  arXiv  Detail & Related papers  (2020-09-02T06:39:30Z)
• Performance Analysis of Meta-heuristic Algorithms for a Quadratic Assignment Problem [6.555180412600522]
  A quadratic assignment problem (QAP) is an optimization problem that belongs to the class of NP-hard ones. Heuristics and meta-heuristics algorithm are prevalent solution methods for this problem. This paper is one of comparative studies to apply different metaheuristic algorithms for solving the QAP.
  arXiv  Detail & Related papers  (2020-07-29T15:02:07Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.