{"id":"W2953059252","doi":"10.48550/arxiv.1308.2617","title":"Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses","year":2013,"lang":"en","type":"preprint","venue":"arXiv (Cornell University)","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":8,"is_retracted":false,"has_abstract":true,"ca_institutions":"McGill University","funders":"Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung; Nanyang Technological University; McGill University; Natural Sciences and Engineering Research Council of Canada; Ministry of Education, India; National Science Foundation","keywords":"Exponential time hypothesis; Combinatorics; Parameterized complexity; Hypergraph; Mathematics; Bipartite graph; Bounded function; Hardness of approximation; Upper and lower bounds; Approximation algorithm; Matching (statistics); Time complexity; Constant (computer programming); Discrete mathematics; Independent set; Vertex cover; Graph","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":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow"],"consensus_categories":[],"category_scores_codex":[0.0002072379,0.0002944052,0.0003033325,0.0003604697,0.0003830775,0.0004187129,0.0006883668,0.0002589732,0.00004992476],"category_scores_gemma":[0.00001876888,0.0003334034,0.00008416481,0.0003402414,0.0001225033,0.0006729254,0.002162809,0.0005506703,0.00003799863],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00007250129,"about_ca_system_score_gemma":0.00008955993,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0004643787,"about_ca_topic_score_gemma":0.00003049164,"domain_scores_codex":[0.9983184,0.0001328254,0.000196227,0.0009718446,0.0001184435,0.000262229],"domain_scores_gemma":[0.9987542,0.0001000035,0.0002288348,0.0006219209,0.0001263842,0.0001686403],"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.00003870672,0.0003691748,0.003061534,0.0005088748,0.0004069208,0.0001778067,0.005178043,0.009077152,0.002386745,0.9723891,0.0006639461,0.005741971],"study_design_scores_gemma":[0.000746264,0.00008347944,0.007644765,0.0001539468,0.00009881161,0.00004673094,0.0002027075,0.640425,0.0004853999,0.3489551,0.0003968533,0.0007609942],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.6505227,0.00003639202,0.347975,0.0001051918,0.0003945775,0.0002932034,0.000007651519,0.000173684,0.0004915299],"genre_scores_gemma":[0.9953236,0.0001070448,0.003842239,0.00004320193,0.00006904312,0.000002852378,0.00001769534,0.00001313914,0.0005811807],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.6313478,"threshold_uncertainty_score":0.9999118,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.06756875288534187,"score_gpt":0.1935105022347591,"score_spread":0.1259417493494172,"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."}}