{"id":"W2005606079","doi":"10.1016/j.tcs.2013.03.014","title":"Fast balanced partitioning is hard even on grids and trees","year":2013,"lang":"en","type":"article","venue":"Theoretical Computer Science","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":25,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Waterloo","funders":"","keywords":"Combinatorics; Mathematics; Grid; Partition (number theory); Time complexity; Limit (mathematics); Reduction (mathematics); Approximation algorithm; Maximum cut; Graph partition; Discrete mathematics; Running time; Graph; 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.0005367853,0.0001803402,0.0001871091,0.0001572741,0.0005792666,0.0009220539,0.001531106,0.00004019194,0.0001363873],"category_scores_gemma":[0.00003976828,0.0001458308,0.00005313579,0.0007761308,0.00230869,0.0008689189,0.0008476937,0.0001968352,0.0002042744],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00002600048,"about_ca_system_score_gemma":0.00004116156,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00001010708,"about_ca_topic_score_gemma":5.677959e-7,"domain_scores_codex":[0.9978642,0.00006753786,0.0002106506,0.00074868,0.0005769995,0.0005319392],"domain_scores_gemma":[0.9986376,0.0002150108,0.0000475219,0.0006836544,0.000128456,0.0002877752],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.000001730631,0.0000341466,0.0001851571,0.000002908472,0.000002679568,0.00000266015,0.0004351214,0.00004021235,0.0002989853,0.9134709,0.000284018,0.08524146],"study_design_scores_gemma":[0.0001741298,0.000243491,0.02441425,0.00004272244,0.000001768988,0.00002079087,0.000007503739,0.5811967,0.002128471,0.3914375,0.0001219605,0.0002107403],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1369641,0.00001906649,0.8548797,0.004314432,0.0004668457,0.0001688635,0.000001883539,0.0002025697,0.002982555],"genre_scores_gemma":[0.8755996,0.000005559052,0.1221782,0.002061414,0.0001124286,0.00001408143,4.047739e-7,0.000004896575,0.00002346913],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.7386355,"threshold_uncertainty_score":0.8891387,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01291039760444712,"score_gpt":0.2348642270831152,"score_spread":0.221953829478668,"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."}}