{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.005482693,0.002852439,0.003274963,0.002968488,0.002655815,0.009757026,0.007485437,0.005137095,0.01348418],"category_scores_gemma":[0.04230866,0.002195721,0.004641976,0.008323804,0.007371082,0.03625742,0.007352286,0.0234001,0.002340662],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.007453881,"about_ca_system_score_gemma":0.003114928,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.004533333,"about_ca_topic_score_gemma":0.002853061,"domain_scores_codex":[0.990862,0.002251351,0.0004264032,0.002552624,0.002578382,0.001329183],"domain_scores_gemma":[0.9561601,0.03151468,0.002491833,0.007031551,0.001341081,0.001460722],"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.0008978088,0.000851791,0.003230261,0.001302382,0.000262422,0.0002538143,0.0009099782,0.09293991,0.003759579,0.7820221,0.02381858,0.08975132],"study_design_scores_gemma":[0.00007393375,0.00006099851,0.0005760342,0.00005972265,0.00006375956,0.0001526317,0.00009762512,0.1210949,0.001139653,0.8720836,0.004556414,0.00004071045],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1126151,0.01189645,0.7815688,0.03208966,0.001009254,0.0003267885,0.00195073,0.001843384,0.05669994],"genre_scores_gemma":[0.7467549,0.01326362,0.2004733,0.005262336,0.004180251,0.0008737379,0.003450879,0.001500702,0.02424036],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01348418,"threshold_uncertainty_score":0.05408192,"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."}}