{"id":"W2952164293","doi":"10.48550/arxiv.1204.4526","title":"A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint","year":2012,"lang":"en","type":"preprint","venue":"arXiv (Cornell University)","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":21,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"Engineering and Physical Sciences Research Council","keywords":"Submodular set function; Matroid; Mathematics; Greedy algorithm; Combinatorics; Monotone polygon; Approximation algorithm; Randomized rounding; Rounding; Matroid partitioning; Weighted matroid; Maximization; Discrete mathematics; Constraint (computer-aided design); Function (biology); Algorithm; Mathematical optimization; Computer science; Graphic matroid","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":["metaepi_narrow"],"consensus_categories":[],"category_scores_codex":[0.0004910566,0.0004450229,0.0004974445,0.0004453135,0.0003005474,0.0002366459,0.002073849,0.0003617419,0.00003479825],"category_scores_gemma":[0.00004448447,0.0005439658,0.000401774,0.0007852942,0.0001441197,0.0004016114,0.001884696,0.0004700132,0.00006007724],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0002790628,"about_ca_system_score_gemma":0.0002556701,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00009535429,"about_ca_topic_score_gemma":0.00001396979,"domain_scores_codex":[0.9974614,0.0001529473,0.0002985143,0.001243473,0.0001697851,0.0006738271],"domain_scores_gemma":[0.9975854,0.0001604144,0.0002469728,0.001286292,0.0003365332,0.0003844264],"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.00004836409,0.0003259458,0.0002370731,0.0001083932,0.0001821971,0.00009256843,0.0004601185,0.01680616,0.00002934629,0.9606121,0.0007949627,0.02030279],"study_design_scores_gemma":[0.001223937,0.0001399913,0.0002623043,0.00008157156,0.00009573723,0.00001449521,0.00003850655,0.7427897,0.0002855731,0.2499119,0.00434713,0.0008090962],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.009278133,0.00005044743,0.9842657,0.0001719066,0.004121852,0.001139438,0.0001395333,0.0003651734,0.0004678129],"genre_scores_gemma":[0.8105079,0.00003919846,0.1882171,0.000188365,0.0005683764,0.00001577452,0.00009551574,0.00003993396,0.0003278309],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.8012297,"threshold_uncertainty_score":0.9997012,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.06039290440074062,"score_gpt":0.1978504408056005,"score_spread":0.1374575364048599,"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."}}