{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.006554182,0.0025974,0.002022985,0.002236707,0.001415835,0.004297741,0.00410197,0.001768361,0.006157382],"category_scores_gemma":[0.03001181,0.001317891,0.002380541,0.004712325,0.00347271,0.005337471,0.002310387,0.004895955,0.001143259],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.006395619,"about_ca_system_score_gemma":0.004676695,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0125799,"about_ca_topic_score_gemma":0.008759027,"domain_scores_codex":[0.9911299,0.003062101,0.0002686565,0.001194012,0.001922984,0.002422305],"domain_scores_gemma":[0.9669935,0.02654563,0.0024343,0.001677086,0.001464217,0.0008854376],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"simulation_or_modeling","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0005148487,0.0002456308,0.001469966,0.0004578816,0.0001400888,0.0001480211,0.0002292069,0.860347,0.00296145,0.09734231,0.006028248,0.03011534],"study_design_scores_gemma":[0.00003045993,0.00005789614,0.0002168888,0.0000210891,0.0000238848,0.0000345923,0.00004038835,0.9380585,0.0006134282,0.05997552,0.0009130945,0.00001427585],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.05818998,0.001936527,0.9148393,0.002558483,0.0001661534,0.0002461297,0.0007782431,0.00149179,0.01979339],"genre_scores_gemma":[0.6004329,0.002370198,0.3809085,0.001308135,0.0006198481,0.0009635819,0.001450963,0.001397735,0.010548],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.0125799,"threshold_uncertainty_score":0.04640371,"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."}}