{"id":"W2569788251","doi":"10.1287/moor.2014.0699","title":"The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes","year":2015,"lang":"en","type":"article","venue":"Mathematics of Operations Research","topic":"Formal Methods in Verification","field":"Computer Science","cited_by":20,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"","keywords":"Mathematics; Simplex; Bounded function; Markov decision process; Combinatorics; Discounting; Polynomial; Simplex algorithm; Mathematical optimization; Markov chain; Discrete mathematics; Binary logarithm; Time complexity; Markov process; Applied mathematics; Linear programming; Statistics","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.003040986,0.001356082,0.001641606,0.0007704217,0.000905774,0.001996603,0.001828006,0.001104424,0.006312603],"category_scores_gemma":[0.01673712,0.0007473308,0.001856901,0.0008524655,0.002828493,0.002960109,0.003062463,0.004635978,0.001747685],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002097822,"about_ca_system_score_gemma":0.004343844,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0053768,"about_ca_topic_score_gemma":0.006102584,"domain_scores_codex":[0.9967678,0.001119159,0.000170084,0.00056121,0.000994659,0.0003871406],"domain_scores_gemma":[0.9901038,0.006766621,0.0004327181,0.001135373,0.001220046,0.0003414856],"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.0002531474,0.0001092751,0.0006950616,0.0002640107,0.00009086332,0.0001134163,0.0002126376,0.5360145,0.002286724,0.3820984,0.003510305,0.07435158],"study_design_scores_gemma":[0.00003158008,0.00002431454,0.00004968977,0.00001797282,0.00001142189,0.00001999888,0.00001261653,0.7724141,0.001085716,0.2250459,0.001272918,0.00001377954],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.005051892,0.0001074822,0.9913743,0.000236617,0.00002701809,0.00004926716,0.00006709278,0.000292495,0.002793807],"genre_scores_gemma":[0.3651893,0.0005121765,0.6248062,0.0003106925,0.00008894566,0.000453176,0.0003642362,0.0005075555,0.007767784],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.006312603,"threshold_uncertainty_score":0.02111781,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.2552575597432615,"score_gpt":0.5082352828044298,"score_spread":0.2529777230611683,"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."}}