Skip to Main content Skip to Navigation
Reports

Sample Compression Schemes for Balls in Graphs

Abstract : 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 2 for trees, of size 3 for cycles, of size 4 for interval graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size 2 for trees and of size 4 for interval graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs.
Document type :
Reports
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03705798
Contributor : Fionn Mc Inerney Connect in order to contact the contributor
Submitted on : Monday, June 27, 2022 - 12:14:19 PM
Last modification on : Tuesday, June 28, 2022 - 2:19:31 PM

File

SCS_balls_graphs_journal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03705798, version 1

Collections

Citation

Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, Yann Vaxès. Sample Compression Schemes for Balls in Graphs. [Research Report] CISPA Helmholtz Center for Information Security, Saarbrücken, Germany; Aix-Marseile Université, France. 2022. ⟨hal-03705798⟩

Share

Metrics

Record views

19

Files downloads

0