{"id":"W6947992690","doi":"10.4230/lipics.icalp.2025.20","title":"Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity","year":2025,"lang":"en","type":"article","venue":"DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"Air Force Office of Scientific Research; Natural Sciences and Engineering Research Council of Canada; National Science Foundation","keywords":"Approximation algorithm; Rounding; Graph; Set cover problem; Strength of a graph; Set (abstract data type); Graph theory; Connected dominating set; Network planning and design; Graph algorithms","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.001959468,0.002202991,0.001608218,0.001620855,0.0008694088,0.001808091,0.003878584,0.002297757,0.006297506],"category_scores_gemma":[0.01006373,0.001027028,0.001762133,0.003862389,0.001255285,0.004529915,0.002119781,0.003583516,0.001122762],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003488974,"about_ca_system_score_gemma":0.002327675,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.007715452,"about_ca_topic_score_gemma":0.008745335,"domain_scores_codex":[0.997619,0.0006720945,0.0001088149,0.000479087,0.0006868382,0.000434251],"domain_scores_gemma":[0.9957628,0.002395557,0.0003425707,0.0009003994,0.0004403055,0.0001585014],"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.0002270539,0.0001638882,0.0006006925,0.0001970849,0.00006988615,0.0000832025,0.0001355254,0.8582892,0.001497555,0.04514658,0.007161849,0.08642749],"study_design_scores_gemma":[0.00003944884,0.00003121904,0.00006670811,0.00001326105,0.00001277402,0.00004061089,0.00001864338,0.9746361,0.0004272519,0.0230226,0.001684815,0.00000663181],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.01315449,0.0007675539,0.9785576,0.0005487598,0.00009287762,0.0001012878,0.000231111,0.001128546,0.005417705],"genre_scores_gemma":[0.2767369,0.00078157,0.7154483,0.0003872684,0.0001871157,0.0004639406,0.001303802,0.0003604589,0.004330594],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.007715452,"threshold_uncertainty_score":0.02531439,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02941959307669111,"score_gpt":0.2704119662591975,"score_spread":0.2409923731825064,"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."}}