{"id":"W2369536682","doi":"10.1007/978-3-319-33461-5_4","title":"Approximating Min-Cost Chain-Constrained Spanning Trees: A Reduction from Weighted to Unweighted Problems","year":2016,"lang":"en","type":"book-chapter","venue":"Lecture notes in computer science","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":3,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Waterloo","funders":"","keywords":"Matroid; Rounding; Spanning tree; Degree (music); Approximation algorithm; Combinatorics; Minimum spanning tree; Mathematical optimization; Reduction (mathematics); Linear programming relaxation; Mathematics; Lagrangian relaxation; Computer science; Tree (set theory); Linear programming","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.001762434,0.002453146,0.003102061,0.001475662,0.000925735,0.003048678,0.006021384,0.003148655,0.01112593],"category_scores_gemma":[0.01311252,0.001656285,0.002125533,0.005202997,0.001322342,0.007045878,0.003859286,0.004733955,0.001954624],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.001999705,"about_ca_system_score_gemma":0.001750156,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003862771,"about_ca_topic_score_gemma":0.005154782,"domain_scores_codex":[0.9979955,0.0005301837,0.0001038893,0.0005632783,0.0005902507,0.0002170061],"domain_scores_gemma":[0.994161,0.00388925,0.0003383108,0.0008569143,0.0004606713,0.0002939038],"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.0003605363,0.0005001181,0.0008617642,0.001319306,0.0001742477,0.0001999245,0.0003408249,0.5902627,0.003244611,0.09495852,0.02792602,0.2798515],"study_design_scores_gemma":[0.00004496081,0.00005418568,0.0001642662,0.00006200037,0.00005081538,0.0001083647,0.00008096404,0.8413978,0.0006846953,0.1538181,0.003519688,0.00001413083],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.03147781,0.00163565,0.954457,0.0009098861,0.000221826,0.0002721614,0.0007989039,0.0007444473,0.009482375],"genre_scores_gemma":[0.1917473,0.001888175,0.7886991,0.0004966516,0.0004857189,0.0005518838,0.002420411,0.001185742,0.01252511],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01112593,"threshold_uncertainty_score":0.03721994,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02235592030043055,"score_gpt":0.2387335166019005,"score_spread":0.21637759630147,"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."}}