{"id":"W2010996873","doi":"10.5555/1109557.1109577","title":"Combination can be hard: approximability of the unique coverage problem","year":2006,"lang":"en","type":"article","venue":"Symposium on Discrete Algorithms","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":94,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Alberta","funders":"","keywords":"Hardness of approximation; Combinatorics; Approximation algorithm; Mathematics; Bipartite graph; Matching (statistics); Binary logarithm; Set (abstract data type); Discrete mathematics; Logarithm; Maximization; Time complexity; Computer science; Mathematical optimization","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.002675143,0.001718356,0.002121473,0.001208412,0.001530304,0.005106105,0.003701368,0.002340999,0.01211212],"category_scores_gemma":[0.02008492,0.001163726,0.00284735,0.00267209,0.00163945,0.00919365,0.003611875,0.004646122,0.001329567],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002606704,"about_ca_system_score_gemma":0.001716147,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002211783,"about_ca_topic_score_gemma":0.002643168,"domain_scores_codex":[0.9953262,0.001100218,0.0002314597,0.001463197,0.001020456,0.0008585611],"domain_scores_gemma":[0.989467,0.007098258,0.0007913885,0.001719963,0.0004235731,0.000499922],"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.001670336,0.0008987318,0.009351426,0.001047379,0.0005691767,0.0008478492,0.000883688,0.555603,0.007842246,0.221577,0.0241442,0.175565],"study_design_scores_gemma":[0.0001268827,0.00008855906,0.0007786719,0.00007232985,0.0001589204,0.0007152603,0.0001694379,0.699049,0.004505774,0.2881131,0.00619374,0.00002849471],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2606708,0.00148163,0.6773912,0.005320068,0.000199284,0.0003613495,0.002073104,0.003320703,0.04918182],"genre_scores_gemma":[0.7823982,0.0006964897,0.2025414,0.0007163506,0.000291872,0.0004592724,0.002139853,0.0006487839,0.0101079],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01211212,"threshold_uncertainty_score":0.04051906,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01183958534583239,"score_gpt":0.2252779971216926,"score_spread":0.2134384117758601,"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."}}