DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2018.46

Coresets for Fuzzy K-Means with Applications

Authors: Johannes Blömer, Sascha Brauer, and Kathrin Bujna

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

The fuzzy K-means problem is a popular generalization of the well-known K-means problem to soft clusterings. We present the first coresets for fuzzy K-means with size linear in the dimension, polynomial in the number of clusters, and poly-logarithmic in the number of points. We show that these coresets can be employed in the computation of a (1+epsilon)-approximation for fuzzy K-means, improving previously presented results. We further show that our coresets can be maintained in an insertion-only streaming setting, where data points arrive one-by-one.

Cite as

Johannes Blömer, Sascha Brauer, and Kathrin Bujna. Coresets for Fuzzy K-Means with Applications. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 46:1-46:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:LIPIcs.ISAAC.2018.46,
  author =	{Bl\"{o}mer, Johannes and Brauer, Sascha and Bujna, Kathrin},
  title =	{{Coresets for Fuzzy K-Means with Applications}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{46:1--46:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.46},
  URN =		{urn:nbn:de:0030-drops-99942},
  doi =		{10.4230/LIPIcs.ISAAC.2018.46},
  annote =	{Keywords: clustering, fuzzy k-means, coresets, approximation algorithms, streaming}
}

Document

DOI: 10.4230/DagSemProc.07381.1

07381 Abstracts Collection – Cryptography

Authors: Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer

Published in: Dagstuhl Seminar Proceedings, Volume 7381, Cryptography (2008)

Abstract

From 16.09.2007 to 21.09.2007 the Dagstuhl Seminar 07381 ``Cryptography'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer. 07381 Abstracts Collection – Cryptography. In Cryptography. Dagstuhl Seminar Proceedings, Volume 7381, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:DagSemProc.07381.1,
  author =	{Bl\"{o}mer, Johannes and Boneh, Dan and Cramer, Ronald and Maurer, Ueli},
  title =	{{07381 Abstracts Collection – Cryptography}},
  booktitle =	{Cryptography},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7381},
  editor =	{Johannes Bl\"{o}mer and Dan Boneh and Ronald Cramer and Ueli Maurer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07381.1},
  URN =		{urn:nbn:de:0030-drops-12935},
  doi =		{10.4230/DagSemProc.07381.1},
  annote =	{Keywords: Cryptography, information security, public-key cryptography, cryptographic protocols, security proofs}
}

Document

DOI: 10.4230/DagSemProc.07381.2

07381 Executive Summary - Cryptography

Authors: Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer

Published in: Dagstuhl Seminar Proceedings, Volume 7381, Cryptography (2008)

Abstract

The topics covered in the seminar spanned most areas of cryptography, in one way or another, both in terms of the types of schemes (public-key cryptography, symmetric cryptography, hash functions and other cryptographic functions, multi-party protocols, etc.) and in terms of the mathematical methods and techniques used (algebra, number theory, elliptic curves, probability theory, information theory, combinatorics, quantum theory, etc.). The range of applications addressed in the various talks was broad, ranging from secure communication, key management, authentication, digital signatures and payment systems to e-voting and Internet security. While the initial plan had been to focus more exclusively on public-key cryptography, it turned out that this sub-topic branches out into many other areas of cryptography and therefore the organizers decided to expand the scope, emphasizing quality rather than close adherence to public-key cryptography. This decision turned out to be a wise one. What was common to almost all the talks is that rigorous mathematical proofs for the security of the presented schemes were given. In fact, a central topic of many of the talks were proof methodologies for various contexts.

Cite as

Johannes Blömer, Dan Boneh, Ronald Cramer, and Ueli Maurer. 07381 Executive Summary - Cryptography. In Cryptography. Dagstuhl Seminar Proceedings, Volume 7381, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{blomer_et_al:DagSemProc.07381.2,
  author =	{Bl\"{o}mer, Johannes and Boneh, Dan and Cramer, Ronald and Maurer, Ueli},
  title =	{{07381 Executive Summary - Cryptography}},
  booktitle =	{Cryptography},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7381},
  editor =	{Johannes Bl\"{o}mer and Dan Boneh and Ronald Cramer and Ueli Maurer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07381.2},
  URN =		{urn:nbn:de:0030-drops-12928},
  doi =		{10.4230/DagSemProc.07381.2},
  annote =	{Keywords: Cryptography, information security, public-key cryptography, cryptographic protocols, security proofs}
}

Search Results

Documents authored by Blömer, Johannes

Coresets for Fuzzy K-Means with Applications

Abstract

Cite as

07381 Abstracts Collection – Cryptography

Abstract

Cite as

07381 Executive Summary - Cryptography

Abstract

Cite as

Thanks for your feedback!

Could not send message