1 Search Results for "Ashur, Stav"

Document
DOI: 10.4230/LIPIcs.SoCG.2021.12
On Undecided LP, Clustering and Active Learning

Authors: Stav Ashur and Sariel Har-Peled

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

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

Stav Ashur and Sariel Har-Peled. On Undecided LP, Clustering and Active Learning. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.12},
  URN =		{urn:nbn:de:0030-drops-138116},
  doi =		{10.4230/LIPIcs.SoCG.2021.12},
  annote =	{Keywords: Linear Programming, Active learning, Classification}
}
  • Refine by Author
  • 1 Ashur, Stav
  • 1 Har-Peled, Sariel

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Active learning
  • 1 Classification
  • 1 Linear Programming

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact