{"doi":"10.1609/socs.v3i1.18236","title":"Search-Aware Conditions for Probably Approximately Correct Heuristic Search","abstract":"<jats:p>\n      \n        The notion of finding a solution that is approximately optimal with high probability was recently introduced to the field of heuristic search,formalized as Probably Approximately Correct Heuristic Search, or PAC search in short. A big challenge when constructing a PAC search algorithm is to identify when a given solution achieves the desired sub-optimality with the required confidence, allowing the search to halt and return the incumbent solution. In this paper we propose two novel methods for identifying when a PAC search can halt. Unlike previous work, the new methods provided in this paper become more knowledgeable as the search progresses. This can speedup the search, since the search can halt earlier with the proposed methods and still keeping the desired PAC solution quality guarantees.Experimental results indeed show a substantial speedup of the search in comparison to the previous approach for PAC search.\n      \n    </jats:p>","journal":"Proceedings of the International Symposium on Combinatorial Search","year":2021,"id":31468,"datarank":0.10397207708399181,"base_score":0.6931471805599453,"endowment":0.6931471805599453,"self_citation_contribution":0.10397207708399181,"citation_network_contribution":0.0,"self_endowment_contribution":0.10397207708399181,"citer_contribution":0.0,"corpus_percentile":null,"corpus_rank":null,"citation_count":1,"citer_count":0,"citers_with_citation_signal":0,"citers_with_endowment":0,"datacite_reuse_total":0,"is_dataset":false,"is_dataset_confidence":null,"is_data_producer":false,"deposit_databanks":null,"is_oa":false,"file_count":0,"downloads":0,"has_version_chain":false,"published_date":null,"fair_score":null,"fair_percentile":null,"algorithm_id":"datarank_citation_only_1hop_v6","ranking_scope":"data_only","authors":[{"id":166661,"name":"Ariel Felner","orcid":null,"position":1,"is_corresponding":false},{"id":168608,"name":"Robert Holte","orcid":null,"position":2,"is_corresponding":false},{"id":168607,"name":"Roni Stern","orcid":null,"position":0,"is_corresponding":false}],"reference_count":0,"raw_metadata":{"has_enrichment":true,"base_score":0.6931471805599453,"endowment":0.6931471805599453,"datacite_reuse_total":0,"file_count":0,"downloads":0,"views":0,"has_version_chain":false,"is_dataset":false,"is_oa":false,"pmid":"18998881","pmcid":null,"openalex_id":"https://openalex.org/W2397806795","authors":[],"funders":[],"total_grants":0,"fwci":0.0,"citation_percentile":0.00123751,"influential_citations":0,"citation_trend":[{"year":2018,"count":1}],"oa_status":"gold","license":null,"oa_locations":[{"url":"https://ojs.aaai.org/index.php/SOCS/article/download/18236/18027","host_type":"journal"},{"url":"https://ojs.aaai.org/index.php/SOCS/article/download/18236/18027","host_type":"BRONZE"},{"url":"https://ojs.aaai.org/index.php/SOCS/article/download/18236/18027","host_type":"publisher"},{"url":"https://doi.org/10.1609/socs.v3i1.18236","host_type":"journal"},{"url":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.308.304","host_type":""}],"fields_of_study":["AI-based Problem Solving and Planning","Machine Learning and Algorithms","Metaheuristic Optimization Algorithms Research","Computer Science"],"mesh_terms":[],"keywords":["Incremental heuristic search","Speedup","Beam search","Heuristic","Bidirectional search","Iterative deepening depth-first search","Computer science","Search algorithm","Best-first search","Beam stack search","Quality (philosophy)","Search problem","Field (mathematics)","Guided Local Search","Algorithm","Mathematical optimization","Mathematics","Artificial intelligence","Parallel computing"],"sdg_mappings":[],"linked_datasets":[],"clinical_trials":[],"software_tools":[],"database_accessions":[],"source":"live","citation_network_status":"fetched"},"created_at":"2026-06-09T07:14:57.290577Z","pmid":null,"pmcid":null,"fwci":null,"citation_percentile":null,"influential_citations":0,"oa_status":null,"license":null,"views":0,"total_file_size_bytes":0,"version_count":0,"fair_f":null,"fair_a":null,"fair_i":null,"fair_r":null,"fair_zscore":null,"fair_rationale":null,"fair_model":null,"fair_agent_version":null,"fair_fulltext_source":null,"fair_has_llm":null,"fair_computed_at":null,"clinical_trials":[],"software_tools":[],"db_accessions":[],"linked_datasets":[],"topics":[]}