{"id":"W4250124835","doi":"10.1109/focs.2007.4389538","title":"Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy","year":2007,"lang":"en","type":"article","venue":"Annual Symposium on Foundations of Computer Science","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"","keywords":"Semidefinite programming; Vertex cover; Approximation algorithm; Cover (algebra); Combinatorics; Vertex (graph theory); Linear programming; Mathematics; Time complexity; Omega; Computer science; Algorithm; Discrete mathematics; Mathematical optimization; Graph; Physics","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.003465049,0.0001984968,0.0002752987,0.0006118384,0.0003674485,0.0002120966,0.003644557,0.00006070321,0.00001098242],"category_scores_gemma":[0.0001216969,0.0001553783,0.0001611044,0.002614736,0.001122641,0.001358066,0.0004915929,0.0002195148,0.00001938049],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00007156524,"about_ca_system_score_gemma":0.0002759229,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0001375449,"about_ca_topic_score_gemma":0.00006395513,"domain_scores_codex":[0.9972261,0.0001016351,0.0006464605,0.000599297,0.0009158634,0.0005106073],"domain_scores_gemma":[0.9967759,0.001045119,0.0002452812,0.001196131,0.0006355578,0.0001019658],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.00005550596,0.0007875958,0.0008563925,0.0000502957,0.00001572539,0.000002567708,0.007156099,0.001700856,0.001695948,0.9337058,0.001639918,0.05233328],"study_design_scores_gemma":[0.005376221,0.005569228,0.1642658,0.0007849916,0.0000687268,0.0001429698,0.000796868,0.2478886,0.03600802,0.2963686,0.2401942,0.00253581],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.06276999,0.0000207591,0.9316121,0.002059646,0.0009656055,0.0004582694,0.00003525367,0.0000407882,0.002037569],"genre_scores_gemma":[0.8436739,0.000009569574,0.1552894,0.0008476273,0.00007873958,0.00001444602,0.000009584954,0.000006450353,0.00007030493],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.7809039,"threshold_uncertainty_score":0.6772555,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02778296570340137,"score_gpt":0.3161291337688953,"score_spread":0.288346168065494,"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."}}