CISPA
Browse
cispa_all_3783.pdf (909.73 kB)

Sample Compression Schemes for Balls in Graphs

Download (909.73 kB)
conference contribution
posted on 2023-11-29, 18:22 authored by Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, Yann Vaxès
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.

History

Preferred Citation

Jérémie Chalopin, Victor Chepoi, Fionn Inerney, Sébastien Ratel and Yann Vaxès. Sample Compression Schemes for Balls in Graphs. In: MFCS International Symposium on Mathematical Foundations of Computer Science (MFCS). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

MFCS International Symposium on Mathematical Foundations of Computer Science (MFCS)

Legacy Posted Date

2022-09-23

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3783, title = "Sample Compression Schemes for Balls in Graphs", author = "Chalopin, Jérémie and Chepoi, Victor and Inerney, Fionn Mc and Ratel, Sébastien and Vaxès, Yann", booktitle="{MFCS International Symposium on Mathematical Foundations of Computer Science (MFCS)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC