Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering

Autor: Christian Sohler, Dan Feldman, Melanie Schmidt

Publikováno v: SIAM Journal on Computing. 49:601-657

We develop and analyze a method to reduce the size of a very large set of data points in a high dimensional Euclidean space R d to a small set of weighted points such that the result of a predetermined data analysis task on the reduced set is approxi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3b0801868438865ae303b5bd4f5ccb63
https://doi.org/10.1137/18m1209854

Fair Coresets and Streaming Algorithms for Fair k-means

Autor: Melanie Schmidt, Christian Sohler, Chris Schwiegelshohn

Publikováno v: Schmidt, M, Schwiegelshohn, C & Sohler, C 2020, Fair Coresets and Streaming Algorithms for Fair k-means . in E Bampis & N Megow (eds), Approximation and Online Algorithms-17th International Workshop, WAOA 2019, Revised Selected Papers . springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11926 LNCS, pp. 232-251, 17th International Workshop on Approximation and Online Algorithms, WAOA 2019, Munich, Germany, 12/09/2019 . https://doi.org/10.1007/978-3-030-39479-0_16
Approximation and Online Algorithms ISBN: 9783030394783
WAOA
Approximation and Online Algorithms-17th International Workshop, WAOA 2019, Munich, Germany, September 12–13, 2019, Revised Selected Papers
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Approximation and Online Algorithms

We study fair clustering problems as proposed by Chierichetti et al. [CKLV17]. Here, points have a sensitive attribute and all clusters in the solution are required to be balanced with respect to it (to counteract any form of data-inherent bias). Pre

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::531b1882cbc4ca9b62865d17de3f75f2
https://pure.au.dk/portal/da/publications/fair-coresets-and-streaming-algorithms-for-fair-kmeans(73a0b488-c6dc-4506-85ef-4154ff53178b).html

Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty

Autor: Hendrik Fichtenberger, Pan Peng, Christian Sohler

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::e62ffcc58bc339ed56d71e09e1723826
https://doi.org/10.1137/1.9781611975482.45

A characterization of graph properties testable for general planar graphs with one-sided error (It is all about forbidden subgraphs)

Autor: Artur Czumaj, Christian Sohler

Publikováno v: FOCS

The problem of characterizing testable graph properties (properties that can be tested with a number of queries independent of the input size) is a fundamental problem in the area of property testing. While there has been some extensive prior researc

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cbf5703d26c259e6f95975fb3d67ca9c

Approximating the Spectrum of a Graph

Autor: David Cohen-Steiner, Christian Sohler, Gregory Valiant, Weihao Kong

Publikováno v: KDD 2018-Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
KDD 2018-Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug 2018, London, United Kingdom
KDD

International audience; The spectrum of a network or graph $G=(V,E)$ with adjacency matrix $A$, consists of the eigenvalues of the normalized Laplacian $L= I - D^{-1/2} A D^{-1/2}$. This set of eigenvalues encapsulates many aspects of the structure o

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e81d03b038b7ea7d96264e5046b2dd98
https://hal.inria.fr/hal-01661199