Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Ashur, Stav; Har-Peled, Sariel https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-138116
URL:

;

On Undecided LP, Clustering and Active Learning

pdf-format:


Abstract

We study colored coverage and clustering problems. Here, we are given a colored point set, where the points are covered by k (unknown) clusters, which are monochromatic (i.e., all the points covered by the same cluster have the same color). The access to the colors of the points (or even the points themselves) is provided indirectly via various oracle queries (such as nearest neighbor, or separation queries). We show that one can correctly deduce the color of all the points (i.e., compute a monochromatic clustering of the points) using a polylogarithmic number of queries, if the number of clusters is a constant.
We investigate several variants of this problem, including Undecided Linear Programming and covering of points by k monochromatic balls.

BibTeX - Entry

@InProceedings{ashur_et_al:LIPIcs.SoCG.2021.12,
  author =	{Ashur, Stav and Har-Peled, Sariel},
  title =	{{On Undecided LP, Clustering and Active Learning}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13811},
  URN =		{urn:nbn:de:0030-drops-138116},
  doi =		{10.4230/LIPIcs.SoCG.2021.12},
  annote =	{Keywords: Linear Programming, Active learning, Classification}
}

Keywords: Linear Programming, Active learning, Classification
Seminar: 37th International Symposium on Computational Geometry (SoCG 2021)
Issue date: 2021
Date of publication: 02.06.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI