{"id":"W2949270856","doi":"10.1137/1.9781611973105.88","title":"Online submodular welfare maximization: Greedy is optimal","year":2013,"lang":"en","type":"preprint","venue":"","topic":"Optimization and Search Problems","field":"Computer Science","cited_by":56,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"","keywords":"Submodular set function; Greedy algorithm; Competitive analysis; Maximization; Monotone polygon; Online algorithm; Mathematical optimization; Greedy randomized adaptive search procedure; Competitive equilibrium; Mathematics; Computer science; Mathematical economics; Upper and lower bounds","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.00445822,0.001626035,0.00263702,0.0008753389,0.00134425,0.004643232,0.002575637,0.003215023,0.006315528],"category_scores_gemma":[0.01957296,0.0007220553,0.001222063,0.002020037,0.002080856,0.006078472,0.002576708,0.003233636,0.001115612],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002779039,"about_ca_system_score_gemma":0.003694164,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001406376,"about_ca_topic_score_gemma":0.001661548,"domain_scores_codex":[0.9958938,0.001582433,0.0001168378,0.000858584,0.0007055602,0.0008427463],"domain_scores_gemma":[0.9878716,0.00868222,0.0008091701,0.001480106,0.000441699,0.0007151716],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.003109051,0.001559169,0.004741811,0.00103383,0.000407513,0.0003164951,0.0004059721,0.3423603,0.01366326,0.428558,0.03429583,0.1695487],"study_design_scores_gemma":[0.0002034468,0.0002172129,0.000562269,0.00006331622,0.00007116974,0.0003615484,0.0001082508,0.7241721,0.004761952,0.2647643,0.004684899,0.00002948755],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2409842,0.001730557,0.6937338,0.00723943,0.0002694979,0.0004592409,0.001239448,0.001908474,0.05243539],"genre_scores_gemma":[0.8362554,0.0009438039,0.1543117,0.00148938,0.0003559979,0.0003879796,0.0006076209,0.0004273346,0.005220804],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.006315528,"threshold_uncertainty_score":0.02357757,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.03280591326405214,"score_gpt":0.2694172725693951,"score_spread":0.2366113593053429,"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."}}