{"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":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.000268682,0.0001836164,0.0001490141,0.0001204858,0.0006577545,0.000258477,0.001163748,0.00007491212,0.000044136],"category_scores_gemma":[0.00001915108,0.0001379814,0.0001863773,0.0004946274,0.0000572707,0.0005533231,0.00001044934,0.0002366999,0.00006175894],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00004406222,"about_ca_system_score_gemma":0.0000435985,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.000009477433,"about_ca_topic_score_gemma":0.000003349043,"domain_scores_codex":[0.9987016,0.00004200711,0.0002491428,0.0003929851,0.0003106185,0.0003036371],"domain_scores_gemma":[0.9983894,0.0004084414,0.00006639312,0.0009729752,0.00009874684,0.00006402734],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.00001182331,0.0001771736,5.679812e-7,0.000005964715,0.00003461677,0.00000100949,0.0004102856,0.0017345,0.0001191803,0.01291586,0.0008326843,0.9837564],"study_design_scores_gemma":[0.0009597231,0.0004527008,0.0006075534,0.00002800166,0.00003823356,0.00002328988,0.00003206939,0.8072985,0.003479594,0.1705465,0.0162154,0.0003183467],"study_design_candidate":"design_other","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.00008011792,0.00005426934,0.9811441,0.01697808,0.0005024229,0.0007054021,0.0000183926,0.0002224741,0.0002947644],"genre_scores_gemma":[0.09922127,0.0000485861,0.8943051,0.005196336,0.0001573444,0.0003308286,0.000009242757,0.00001749187,0.0007137958],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.983438,"threshold_uncertainty_score":0.5626717,"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."}}