{"id":"W2802261039","doi":"10.1016/j.tcs.2018.04.022","title":"Approximation and complexity of multi-target graph search and the Canadian traveler problem","year":2018,"lang":"en","type":"article","venue":"Theoretical Computer Science","topic":"Optimization and Search Problems","field":"Computer Science","cited_by":4,"is_retracted":false,"has_abstract":false,"ca_institutions":"","funders":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","keywords":"Graph; Computer science; Approximation algorithm; Theoretical computer science; Mathematics; Combinatorics; Mathematical optimization","routes":{"ca_aff":false,"ca_fund":false,"ca_venue":false,"about_ca":true,"invisible_to_affiliation_only":true},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.003309996,0.001971616,0.003444013,0.002730642,0.002662385,0.004736077,0.005965076,0.004548423,0.01558118],"category_scores_gemma":[0.02690474,0.00107787,0.001773219,0.006031092,0.003131175,0.00806679,0.00315366,0.004276777,0.0008714579],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.01275241,"about_ca_system_score_gemma":0.01212213,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.1977147,"about_ca_topic_score_gemma":0.1675705,"domain_scores_codex":[0.9970299,0.0009875415,0.00008446668,0.0005023847,0.0005956589,0.0007998903],"domain_scores_gemma":[0.9839041,0.01284906,0.0006368858,0.0008570043,0.0007958742,0.0009571476],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"simulation_or_modeling","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.001094584,0.0003709021,0.003106479,0.0003901385,0.0001209909,0.0001326949,0.0003158253,0.8390086,0.0004312427,0.1013216,0.02171985,0.03198703],"study_design_scores_gemma":[0.0001083218,0.00003662697,0.0004808475,0.00002839018,0.00003822671,0.00004390863,0.0001348648,0.9326005,0.0001578511,0.06500015,0.001350634,0.00001973113],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.4702344,0.007040381,0.4184178,0.01718143,0.0005344466,0.0006861132,0.006699459,0.00162665,0.07757936],"genre_scores_gemma":[0.8479118,0.001916782,0.1249464,0.0007724661,0.0002797547,0.0003205241,0.004221123,0.0005224761,0.0191088],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.1977147,"threshold_uncertainty_score":0.3931277,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.03937901021381209,"score_gpt":0.27466528492848,"score_spread":0.235286274714668,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}