2026-07-22T07:15:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16829 2024-03-06T10:58:26Z ddc:004 open_access

Sample Compression Schemes for Balls in Graphs Chalopin, Jérémie Chepoi, Victor Mc Inerney, Fionn Ratel, Sébastien Vaxès, Yann Proper Sample Compression Schemes Balls Graphs VC-dimension One of the open problems in machine learning is whether any set-family of VC-dimension d admits a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs. For balls of arbitrary radius r, we design proper sample compression schemes of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jérémie Chalopin and Victor Chepoi and Fionn Mc Inerney and Sébastien Ratel and Yann Vaxès 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.31 urn:nbn:de:0030-drops-168298 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.31 eng https://creativecommons.org/licenses/by/4.0/legalcode