Document Open Access Logo

Sample Compression Schemes for Balls in Graphs

Authors Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, Yann Vaxès

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.31.pdf
  • Filesize: 0.88 MB
  • 14 pages

Document Identifiers

Author Details

Jérémie Chalopin
  • Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France
Victor Chepoi
  • Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France
Fionn Mc Inerney
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Sébastien Ratel
  • Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France
Yann Vaxès
  • Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France

Funding

This work was supported by the ANR project DISTANCIA (ANR-17-CE40-0015) and the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.

Cite As Get BibTex

Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample Compression Schemes for Balls in Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.31

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 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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Machine learning theory
Keywords
  • Proper Sample Compression Schemes
  • Balls
  • Graphs
  • VC-dimension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. H.-J. Bandelt and V. Chepoi. Metric graph theory and geometry: a survey. In J. E. Goodman, J. Pach, and R. Pollack, editors, Surveys on Discrete and Computational Geometry. Twenty Years later, volume 453 of Contemp. Math., pages 49-86. AMS, Providence, RI, 2008. Google Scholar
  2. H.-J. Bandelt, V. Chepoi, and D. Eppstein. Ramified rectilinear polygons: coordinatization by dendrons. Discr. Comput. Geom., 54:771-797, 2015. Google Scholar
  3. H.-J. Bandelt, V. Chepoi, and K. Knauer. COMs: complexes of oriented matroids. J. Combin. Th., Ser. A, 156:195-237, 2018. Google Scholar
  4. L. Beaudou, P. Dankelmann, F. Foucaud, M. A. Henning, A. Mary, and A. Parreau. Bounding the order of a graph using its diameter and metric dimension: A study through tree decompositions and VC dimension. SIAM J. Discr. Math., 32(2):902-918, 2018. Google Scholar
  5. S. Ben-David and A. Litman. Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes. Discr. Appl. Math., 86:3-25, 1998. Google Scholar
  6. A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler. Oriented Matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1993. Google Scholar
  7. N. Bousquet and S. Thomassé. VC-dimension and Erdős–Pósa property. Discr. Math., 338:2302-2317, 2015. Google Scholar
  8. J. Chalopin, V. Chepoi, F. Mc Inerney, S. Ratel, and Y. Vaxès. Sample compression schemes for balls in graphs. arXiv, 2022. URL: http://arxiv.org/abs/2206.13254.
  9. J. Chalopin, V. Chepoi, S. Moran, and M. K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. J. Comput. Syst. Sci., 127:1-28, 2022. Google Scholar
  10. V. Chepoi, B. Estellon, and Y. Vaxès. On covering planar graphs with a fixed number of balls. Discr. Comput. Geom., 37:237-244, 2007. Google Scholar
  11. V. Chepoi and M. Hagen. On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes. J. Combin. Th., Ser. B, 103:428-467, 2013. Google Scholar
  12. V. Chepoi, K. Knauer, and M. Philibert. Labeled sample compression schemes for complexes of oriented matroids. arXiv, 2021. URL: http://arxiv.org/abs/2110.15168.
  13. V. Chepoi, A. Labourel, and S. Ratel. Distance and routing labeling schemes for cube-free median graphs. Algorithmica, 83:252-296, 2021. Google Scholar
  14. V. Chepoi and D. Maftuleac. Shortest path problem in rectangular complexes of global nonpositive curvature. Computational Geometry, 46:51-64, 2013. Google Scholar
  15. A. W. M. Dress. Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups. Advances in Mathematics, 53:321-402, 1984. Google Scholar
  16. G. Ducoffe, M. Habib, and L. Viennot. Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension. In ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 1905-1922, 2020. Google Scholar
  17. S. Floyd and M. K. Warmuth. Sample compression, learnability, and the Vapnik-Chervonenkis dimension. Machine Learning, 21:269-304, 1995. Google Scholar
  18. M. Gromov. Hyperbolic groups. Essays in group theory, pages 75-263, 1987. Google Scholar
  19. D. Helmbold, R. Sloan, and M. K. Warmuth. Learning nested differences of intersection-closed concept classes. Machine Learning, 5:165-196, 1990. Google Scholar
  20. J. R. Isbell. Six theorems about injective metric spaces. Comment. Math. Helv., 39:65-76, 1964. Google Scholar
  21. U. Lang. Injective hulls of certain discrete metric spaces and groups. J. Topol. Anal., 5:297-331, 2013. Google Scholar
  22. N. Littlestone and M. K. Warmuth. Relating data compression and learnability. Unpublished, 1986. Google Scholar
  23. S. Moran and M. K. Warmuth. Labeled compression schemes for extremal classes. In ALT 2016, pages 34-49, 2016. Google Scholar
  24. S. Moran and A. Yehudayoff. Sample compression schemes for VC classes. J. ACM, 63:1-21, 2016. Google Scholar
  25. D. Pálvölgyi and G. Tardos. Unlabeled compression schemes exceeding the VC-dimension. Discr. Appl. Math., 276:102-107, 2020. Google Scholar
  26. M. Pilipczuk and S. Siebertz. Kernelization and approximation of distance-r independent sets on nowhere dense graphs. Eur. J. Comb., 94:103223, 2021. Google Scholar
  27. V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264-280, 1971. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact