Scholarlink

Abstract <p> We analyze the complexity of one extremal problem of choosing a subset of<InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11754_2025_5352_Article_IEq1.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(p\)</EquationSource> </InlineEquation> points in a given finite set in a metric space. The chosen subset of points isrequired to describe given clusters in the best way from the point of view of some geometriccriterion. This problem is a formalization of one applied problem from data mining that consistsin finding a subset of typical representatives of a dataset based on the rival similarity function. Weprove that the problem under consideration is NP-hard by polynomially reducing the well-knownNP-hard 3D-Matching problem to this one.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Computational Complexity of the Choice Problem for Typical Representatives of a Finite Point Set in a Metric Space

  • 期刊论文

  • 发表日期：

    2025年11月2日

查看全文
  • I. A. Borisova

摘要

Abstract

We analyze the complexity of one extremal problem of choosing a subset of \(p\) points in a given finite set in a metric space. The chosen subset of points isrequired to describe given clusters in the best way from the point of view of some geometriccriterion. This problem is a formalization of one applied problem from data mining that consistsin finding a subset of typical representatives of a dataset based on the rival similarity function. Weprove that the problem under consideration is NP-hard by polynomially reducing the well-knownNP-hard 3D-Matching problem to this one.