{"id":"W2467644617","doi":"10.1007/s00224-015-9649-x","title":"On the Advice Complexity of the k-server Problem Under Sparse Metrics","year":2015,"lang":"en","type":"article","venue":"Theory of Computing Systems","topic":"Optimization and Search Problems","field":"Computer Science","cited_by":8,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Waterloo","funders":"","keywords":"Treewidth; Advice (programming); Combinatorics; Binary logarithm; Competitive analysis; Mathematics; Online algorithm; Metric space; Discrete mathematics; Upper and lower bounds; Sequence (biology); Metric (unit); Tree (set theory); Deterministic algorithm; Path (computing); Time complexity; Graph; Algorithm; Computer science; Pathwidth; Line graph","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.006391812,0.002024957,0.004818555,0.002247857,0.002161433,0.006033253,0.005597012,0.005806283,0.01908991],"category_scores_gemma":[0.08712261,0.001457072,0.001456605,0.003905392,0.00531318,0.01724506,0.005511644,0.007830597,0.001518933],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005153745,"about_ca_system_score_gemma":0.005132949,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.007358145,"about_ca_topic_score_gemma":0.006759627,"domain_scores_codex":[0.9934783,0.002748414,0.000310075,0.0008764483,0.001535522,0.001051256],"domain_scores_gemma":[0.8734667,0.1120906,0.003454947,0.004091833,0.003613921,0.003282044],"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.001206994,0.0003769221,0.003075483,0.0007630459,0.0001515354,0.0002643509,0.0007497999,0.2439651,0.00179893,0.6887338,0.02489131,0.03402265],"study_design_scores_gemma":[0.0001094889,0.00004868996,0.0005422097,0.00004585524,0.00002975157,0.00007066924,0.0001021743,0.4773383,0.0002115566,0.5206671,0.00080119,0.0000330338],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.3141484,0.006309311,0.5849891,0.03573401,0.0008123221,0.0004250627,0.003091337,0.001191835,0.05329864],"genre_scores_gemma":[0.8930582,0.00393094,0.07613857,0.001866992,0.001779699,0.000577081,0.002030386,0.0007918868,0.01982617],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01908991,"threshold_uncertainty_score":0.06386209,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.1207327124076679,"score_gpt":0.2864676065370435,"score_spread":0.1657348941293756,"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."}}