Sample Compression Schemes for Balls in Graphs

Publication date 14 November 2023

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

d e l t a

-hyperbolic graphs.

Cites work

Cited in

(4)

This page was built for publication: Sample Compression Schemes for Balls in Graphs