{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.003623589,0.001788183,0.002692637,0.001513764,0.002188897,0.004370394,0.003069304,0.002539553,0.02137003],"category_scores_gemma":[0.01698114,0.0009807784,0.002164147,0.001533843,0.003076237,0.006480946,0.004389991,0.009167318,0.002469031],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005983052,"about_ca_system_score_gemma":0.002869532,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003339988,"about_ca_topic_score_gemma":0.004199938,"domain_scores_codex":[0.9974655,0.0005723126,0.00007032697,0.0004433071,0.0006940838,0.0007545339],"domain_scores_gemma":[0.9884573,0.009006075,0.0004878747,0.0009453486,0.0003409545,0.000762406],"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.0007812839,0.0003991306,0.001645281,0.0008482359,0.00009808214,0.000269563,0.0007378384,0.1554859,0.003144094,0.757301,0.02454301,0.05474662],"study_design_scores_gemma":[0.00007081809,0.00009993105,0.0005353055,0.0001269667,0.00004835623,0.0001450015,0.000116263,0.3864463,0.001179955,0.6041067,0.007094392,0.00002997234],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1962413,0.00662465,0.5544449,0.0119987,0.0006794952,0.0004999249,0.002829623,0.002699067,0.2239824],"genre_scores_gemma":[0.8224946,0.002851033,0.1431703,0.00231577,0.0005573623,0.0006510647,0.001492047,0.001024664,0.02544304],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.02137003,"threshold_uncertainty_score":0.07148987,"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."}}