{"id":"W2009786555","doi":"10.1109/focs.2012.55","title":"A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint","year":2012,"lang":"en","type":"article","venue":"","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":60,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"","keywords":"Matroid; Submodular set function; Greedy algorithm; Monotone polygon; Mathematics; Rounding; Function (biology); Combinatorics; Constraint (computer-aided design); Mathematical optimization; Approximation algorithm; Algorithm; Discrete mathematics; Combinatorial optimization; Computer science","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.001683999,0.001896045,0.001553793,0.001351314,0.0006390126,0.001878964,0.002580305,0.001953683,0.009193577],"category_scores_gemma":[0.00727708,0.0008560674,0.001408921,0.001995938,0.001164189,0.003051371,0.003195636,0.002619516,0.002781924],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00175934,"about_ca_system_score_gemma":0.002282572,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001729909,"about_ca_topic_score_gemma":0.002549445,"domain_scores_codex":[0.9985029,0.0004014284,0.00007440252,0.0003408955,0.0004636727,0.0002168334],"domain_scores_gemma":[0.9981284,0.001114279,0.000139828,0.0003610565,0.0001512957,0.0001051052],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0003655298,0.0004803282,0.0007612275,0.0005074888,0.0001274576,0.0001661728,0.0002214046,0.3433202,0.008917786,0.1433452,0.02172154,0.4800657],"study_design_scores_gemma":[0.0001275498,0.000118444,0.0001720632,0.00002853449,0.00002525527,0.000151502,0.00004066696,0.9175724,0.001758626,0.07635234,0.003631551,0.00002098327],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.004663142,0.0001809491,0.989702,0.0002560509,0.00004474928,0.0001112329,0.00008342609,0.0008068176,0.004151729],"genre_scores_gemma":[0.0920386,0.0002331896,0.9035602,0.00028939,0.0001061489,0.0003845981,0.0003340473,0.0003393115,0.002714613],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.009193577,"threshold_uncertainty_score":0.03075558,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01981169866179729,"score_gpt":0.2545320422452528,"score_spread":0.2347203435834555,"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."}}