{"id":"W2030970869","doi":"10.1145/1597036.1597045","title":"A better approximation ratio for the vertex cover problem","year":2009,"lang":"en","type":"article","venue":"ACM Transactions on Algorithms","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":156,"is_retracted":false,"has_abstract":true,"ca_institutions":"McMaster University","funders":"","keywords":"Mathematics; Combinatorics; Vertex cover; Cover (algebra); Relaxation (psychology); Vertex (graph theory); Maximum cut; Approximation algorithm; Set cover problem; Set (abstract data type); Discrete mathematics; Computer science; Graph","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.005101317,0.003560206,0.002747485,0.002032764,0.001039317,0.004581069,0.003983286,0.004144082,0.02482462],"category_scores_gemma":[0.0254202,0.0008472944,0.003130029,0.00296978,0.001544376,0.010881,0.003580556,0.008313023,0.005788654],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003254429,"about_ca_system_score_gemma":0.002572152,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002562769,"about_ca_topic_score_gemma":0.002963669,"domain_scores_codex":[0.9930823,0.002094771,0.0002093114,0.001621482,0.001774978,0.001217166],"domain_scores_gemma":[0.9860219,0.008052012,0.0005977625,0.003705475,0.0009581965,0.000664708],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.003141178,0.002080884,0.003196175,0.001331339,0.0004495121,0.0004887141,0.000588604,0.2611635,0.02516682,0.2588535,0.07528844,0.3682514],"study_design_scores_gemma":[0.0003504677,0.0003977418,0.0007308785,0.0001230443,0.0001551502,0.0007621582,0.0001591472,0.7947406,0.006352617,0.1777636,0.01840167,0.0000629965],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.0799201,0.006633948,0.8468265,0.01265601,0.001886283,0.0003286779,0.001310526,0.003653926,0.04678413],"genre_scores_gemma":[0.459565,0.003203072,0.5050095,0.004404626,0.002163604,0.0005921061,0.003535984,0.002442033,0.01908408],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.02482462,"threshold_uncertainty_score":0.08304662,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.0276875545897699,"score_gpt":0.2638624229823917,"score_spread":0.2361748683926218,"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."}}