{"id":"W1916472382","doi":"10.37236/449","title":"Linear Programming and the Worst-Case Analysis of Greedy Algorithms on Cubic Graphs","year":2010,"lang":"en","type":"article","venue":"The Electronic Journal of Combinatorics","topic":"Advanced Graph Theory Research","field":"Computer Science","cited_by":15,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"Australian Research Council; Canada Research Chairs; University of Melbourne; Macquarie University","keywords":"Combinatorics; Mathematics; Heuristics; Bounding overwatch; Maximal independent set; Cubic graph; Vertex (graph theory); Greedy algorithm; Discrete mathematics; Graph; Chordal graph; Algorithm; Computer science; 1-planar graph; Line graph; Mathematical optimization","routes":{"ca_aff":true,"ca_fund":true,"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.005340755,0.0001591738,0.0004174892,0.0005456682,0.0003105745,0.00008156255,0.001536936,0.00006134694,0.000003072697],"category_scores_gemma":[0.0002458079,0.00008400839,0.00029626,0.00320982,0.0004737219,0.0002372303,0.0002113461,0.001677755,8.978349e-7],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00004953142,"about_ca_system_score_gemma":0.0001878366,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00001371258,"about_ca_topic_score_gemma":0.00002139226,"domain_scores_codex":[0.99769,0.0003862654,0.0004602395,0.0001779711,0.0006874556,0.000598025],"domain_scores_gemma":[0.9970473,0.001171157,0.0005312,0.0007159086,0.000429063,0.0001053877],"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.0001021655,0.0001081526,0.0002493353,0.000003972634,0.0005431474,0.00005244702,0.0005332822,0.0001725187,0.0001252342,0.9851881,0.000004674267,0.01291692],"study_design_scores_gemma":[0.001522044,0.0007962844,0.0002139443,0.00001073493,0.0003532639,0.001037992,0.0001435906,0.02244964,0.0009747736,0.9719716,0.000400533,0.0001255569],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.8369772,0.001821019,0.1589838,0.00146079,0.0003558848,0.0002803634,7.789299e-7,0.00002175974,0.00009846288],"genre_scores_gemma":[0.9988804,0.0003413277,0.0006417098,0.00004093584,0.00003561817,0.000004746468,1.955063e-7,0.00001103189,0.00004398509],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.1619033,"threshold_uncertainty_score":0.7289104,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.009681412868531011,"score_gpt":0.2806493101126358,"score_spread":0.2709678972441047,"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."}}