{"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":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.0005575101,0.000283273,0.0003039611,0.0001199934,0.0003157083,0.0001491132,0.001549909,0.0001153863,0.00001111961],"category_scores_gemma":[0.00002120245,0.0002112693,0.0002537498,0.0008332045,0.0003039313,0.0003126982,0.0004432723,0.000321604,0.000003696739],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.0001223978,"about_ca_system_score_gemma":0.0001283265,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0007782922,"about_ca_topic_score_gemma":0.00008228325,"domain_scores_codex":[0.9974603,0.0002784406,0.000498274,0.0006326795,0.0007245122,0.000405785],"domain_scores_gemma":[0.9980025,0.0001483516,0.0002766286,0.001320032,0.0001745497,0.00007790491],"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.00002296414,0.0009012559,0.002186992,0.0001268126,0.00005174511,0.000007855712,0.0008022469,0.002087749,0.006419525,0.9731246,0.001718886,0.01254943],"study_design_scores_gemma":[0.002715252,0.0009443537,0.05467756,0.0002287768,0.00005277305,0.00004114033,0.000067512,0.1918368,0.1164421,0.620891,0.01083533,0.001267367],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.136882,0.0001973264,0.7234284,0.05232142,0.003209949,0.004341499,0.0005597383,0.00100805,0.07805165],"genre_scores_gemma":[0.9699648,0.00001761869,0.0282504,0.0004970201,0.0001092831,0.00008601729,0.00003761558,0.00002551186,0.001011731],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.8330828,"threshold_uncertainty_score":0.861531,"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."}}