{"id":"W4313203312","doi":"10.1109/focs54457.2022.00064","title":"Maximum Flow and Minimum-Cost Flow in Almost-Linear Time","year":2022,"lang":"en","type":"article","venue":"2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)","topic":"Optimization and Search Problems","field":"Computer Science","cited_by":132,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto; University of Waterloo","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Minimum-cost flow problem; Mathematics; Minimum cut; Separable space; Combinatorics; Amortized analysis; Bounded function; Regular polygon; Scaling; Time complexity; Maximum flow problem; Flow (mathematics); Discrete mathematics; Directed graph; Approximation algorithm; Mathematical optimization; Flow network; Computer science; Data structure","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.0008325835,0.001704065,0.0009124433,0.001104946,0.0007990664,0.001713462,0.001682532,0.001414682,0.008048496],"category_scores_gemma":[0.007082187,0.0006563287,0.001049269,0.001552706,0.0008475307,0.003756389,0.001412012,0.001813704,0.002034647],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002167618,"about_ca_system_score_gemma":0.002975173,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.006984792,"about_ca_topic_score_gemma":0.009575842,"domain_scores_codex":[0.9989495,0.0001772308,0.00006627172,0.0003170058,0.000302404,0.00018763],"domain_scores_gemma":[0.9978395,0.00112079,0.0001869841,0.0004783315,0.0002901141,0.00008426804],"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.0006131968,0.0002564256,0.002216339,0.0003879997,0.0001031144,0.0001398118,0.000247116,0.5435408,0.00979362,0.06977117,0.02081807,0.3521123],"study_design_scores_gemma":[0.00005676206,0.00003104318,0.0003068309,0.00001630047,0.00001463915,0.00005970362,0.00004459832,0.9175959,0.00338469,0.07588129,0.002595382,0.00001274861],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.03779519,0.0002888965,0.9459522,0.0006176977,0.00007642456,0.0001762936,0.0008633588,0.006320792,0.007909143],"genre_scores_gemma":[0.2561299,0.000158404,0.7361989,0.0002195587,0.00007255997,0.0002514792,0.002198395,0.0009748014,0.003795906],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.008048496,"threshold_uncertainty_score":0.02692491,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01399420956229129,"score_gpt":0.2647044641196495,"score_spread":0.2507102545573582,"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."}}