{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001762255,0.002190826,0.004247174,0.001396869,0.003416563,0.006803368,0.00346293,0.004152918,0.0122684],"category_scores_gemma":[0.02074687,0.002265618,0.002024902,0.003945364,0.003369757,0.01928727,0.004715166,0.004992113,0.002389611],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.001931443,"about_ca_system_score_gemma":0.002074394,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003747476,"about_ca_topic_score_gemma":0.004438109,"domain_scores_codex":[0.9975969,0.0004020234,0.0001744771,0.0007870306,0.0004599377,0.0005796059],"domain_scores_gemma":[0.9612544,0.03003418,0.002281766,0.00379438,0.001200836,0.001434517],"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.007684512,0.00103106,0.01069733,0.00342978,0.0006250481,0.001574779,0.001851135,0.4146514,0.025488,0.2948872,0.09253469,0.1455452],"study_design_scores_gemma":[0.0003731965,0.0001072111,0.001307715,0.00007638032,0.00007732283,0.0003676128,0.0004976473,0.227247,0.002655786,0.7632121,0.004036059,0.00004201941],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.6718516,0.003842437,0.2598484,0.02073599,0.0008429731,0.000302758,0.006018068,0.002749447,0.03380834],"genre_scores_gemma":[0.842642,0.00234391,0.1227853,0.001886168,0.001325043,0.000366745,0.007863024,0.001423486,0.01936434],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.0122684,"threshold_uncertainty_score":0.04104185,"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."}}