{"id":"W2125240990","doi":"10.1023/b:joco.0000038911.67280.3f","title":"On Approximate Graph Colouring and MAX-k-CUT Algorithms Based on the θ-Function","year":2004,"lang":"en","type":"article","venue":"Journal of Combinatorial Optimization","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":75,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Waterloo","funders":"Technische Universiteit Delft; Universiteit Utrecht; Deutsche Forschungsgemeinschaft","keywords":"Mathematics; Combinatorics; Semidefinite programming; Approximation algorithm; Bounded function; Graph; Relaxation (psychology); Discrete mathematics; Maximum cut; Algorithm; Mathematical optimization","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.0007405863,0.0001500163,0.0001892092,0.0002643182,0.0003158328,0.0002578866,0.000417974,0.00007445179,0.000008681693],"category_scores_gemma":[0.0001110314,0.0001079057,0.0001032709,0.0005085142,0.0000631202,0.0004146468,0.00005449668,0.000313337,0.000001587555],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00008135234,"about_ca_system_score_gemma":0.00008703222,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.000003408626,"about_ca_topic_score_gemma":1.693262e-7,"domain_scores_codex":[0.9986359,0.0001149206,0.0003484301,0.0001803495,0.0005512044,0.0001691243],"domain_scores_gemma":[0.9988024,0.0002504275,0.0003741907,0.0002532913,0.0002345111,0.00008523315],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"simulation_or_modeling","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.00009995332,0.0001801337,0.000008193223,0.000005166678,0.00001746854,0.000008809575,0.00007919567,0.6068959,0.00001334354,0.3912695,0.0001012103,0.001321088],"study_design_scores_gemma":[0.0025679,0.001525757,0.0001142006,0.0001162904,0.00002124119,0.00002655003,0.00001767848,0.625653,0.0005722026,0.3690809,0.0001501003,0.0001542325],"study_design_candidate":"simulation_or_modeling","study_design_consensus":"simulation_or_modeling","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.004961327,0.0000280071,0.9879391,0.002431826,0.003960817,0.0001697029,9.486333e-7,0.00004058622,0.0004676918],"genre_scores_gemma":[0.8414066,0.0000601955,0.1568731,0.001128836,0.0004894048,0.000008544741,0.000002304495,0.0000217099,0.000009262853],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.8364453,"threshold_uncertainty_score":0.4400265,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01223000613380427,"score_gpt":0.2180044899597861,"score_spread":0.2057744838259818,"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."}}