{"id":"W1524471135","doi":"10.1145/2963170","title":"Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications","year":2016,"lang":"en","type":"article","venue":"ACM Transactions on Algorithms","topic":"Facility Location and Emergency Management","field":"Business, Management and Accounting","cited_by":39,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Matroid; Knapsack problem; Approximation algorithm; Oriented matroid; Facility location problem; Matroid partitioning; Mathematics; Weighted matroid; Combinatorics; Polynomial-time approximation scheme; Greedy algorithm; Randomized rounding; Set (abstract data type); Generalization; Computer science; Discrete mathematics; Mathematical optimization; Graphic matroid","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.002878568,0.002015269,0.002241964,0.001845977,0.00106594,0.003216061,0.003560989,0.002573359,0.01029528],"category_scores_gemma":[0.01143874,0.0009018905,0.002134115,0.005355208,0.0008741632,0.005804263,0.003398543,0.005152491,0.002406051],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003364334,"about_ca_system_score_gemma":0.002588712,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.006337186,"about_ca_topic_score_gemma":0.00801881,"domain_scores_codex":[0.9961727,0.001090368,0.000213805,0.0006726407,0.001282032,0.0005684487],"domain_scores_gemma":[0.9962908,0.001817374,0.0003244168,0.000810179,0.0005691429,0.0001880299],"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.0005301264,0.0006334723,0.0009620622,0.0004695003,0.0001327748,0.0001311483,0.0003369464,0.5740396,0.0022815,0.1550823,0.01852602,0.2468745],"study_design_scores_gemma":[0.00005192561,0.00005592379,0.000157602,0.00003300095,0.00002040404,0.00009150249,0.00006464422,0.9180337,0.0006358344,0.07403382,0.006807454,0.00001427736],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.01388827,0.002785347,0.9673542,0.001023576,0.0002315704,0.0001321785,0.0003256589,0.00111773,0.01314144],"genre_scores_gemma":[0.1802647,0.002030196,0.8076468,0.0005149069,0.0003823886,0.0003075745,0.001051215,0.0003702095,0.007432085],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.01029528,"threshold_uncertainty_score":0.03444111,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.03083915340769189,"score_gpt":0.2429966165842655,"score_spread":0.2121574631765736,"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."}}