Standard

Pseudo-polynomial Algorithms for Some Problems of Searching for the Largest Subsets. / Khandeev, Vladimir; Neshchadim, Sergey.

Communications in Computer and Information Science. Springer Science and Business Media Deutschland GmbH, 2024. p. 319-333 22 (Communications in Computer and Information Science; Vol. 2239 CCIS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Khandeev, V & Neshchadim, S 2024, Pseudo-polynomial Algorithms for Some Problems of Searching for the Largest Subsets. in Communications in Computer and Information Science., 22, Communications in Computer and Information Science, vol. 2239 CCIS, Springer Science and Business Media Deutschland GmbH, pp. 319-333, 23rd International Conference on Mathematical Optimization Theory and Operations Research, Омск, Russian Federation, 30.06.2024. https://doi.org/10.1007/978-3-031-73365-9_22

APA

Khandeev, V., & Neshchadim, S. (2024). Pseudo-polynomial Algorithms for Some Problems of Searching for the Largest Subsets. In Communications in Computer and Information Science (pp. 319-333). [22] (Communications in Computer and Information Science; Vol. 2239 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-73365-9_22

Vancouver

Khandeev V, Neshchadim S. Pseudo-polynomial Algorithms for Some Problems of Searching for the Largest Subsets. In Communications in Computer and Information Science. Springer Science and Business Media Deutschland GmbH. 2024. p. 319-333. 22. (Communications in Computer and Information Science). doi: 10.1007/978-3-031-73365-9_22

Author

Khandeev, Vladimir ; Neshchadim, Sergey. / Pseudo-polynomial Algorithms for Some Problems of Searching for the Largest Subsets. Communications in Computer and Information Science. Springer Science and Business Media Deutschland GmbH, 2024. pp. 319-333 (Communications in Computer and Information Science).

BibTeX

@inproceedings{0fc0272e48bc4c3c9576904cb78d22ae,
title = "Pseudo-polynomial Algorithms for Some Problems of Searching for the Largest Subsets",
abstract = "We consider several problems of finding the subsets with the largest minimal cardinality and limited scatter in a finite set of points in Euclidean space. For each cluster, the scatter is the sum of the distances (raised to a power) between the elements and the center of the cluster. Depending on the problem, the center can be defined in different ways—as a fixed point, as the centroid of the cluster, etc. We propose a general scheme for a pseudo-polynomial algorithm to solve such problems, and we also show how and in what time this scheme can be implemented for several types of centers.",
keywords = "Bounded scatter, Clustering, Euclidean space, Max-min problem, NP-hardness, Pseudo-polynomial algorithm",
author = "Vladimir Khandeev and Sergey Neshchadim",
year = "2024",
month = dec,
day = "20",
doi = "10.1007/978-3-031-73365-9_22",
language = "English",
isbn = "978-303173364-2",
series = "Communications in Computer and Information Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "319--333",
booktitle = "Communications in Computer and Information Science",
address = "Germany",
note = "23rd International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2024 ; Conference date: 30-06-2024 Through 06-07-2024",

}

RIS

TY - GEN

T1 - Pseudo-polynomial Algorithms for Some Problems of Searching for the Largest Subsets

AU - Khandeev, Vladimir

AU - Neshchadim, Sergey

N1 - Conference code: 23

PY - 2024/12/20

Y1 - 2024/12/20

N2 - We consider several problems of finding the subsets with the largest minimal cardinality and limited scatter in a finite set of points in Euclidean space. For each cluster, the scatter is the sum of the distances (raised to a power) between the elements and the center of the cluster. Depending on the problem, the center can be defined in different ways—as a fixed point, as the centroid of the cluster, etc. We propose a general scheme for a pseudo-polynomial algorithm to solve such problems, and we also show how and in what time this scheme can be implemented for several types of centers.

AB - We consider several problems of finding the subsets with the largest minimal cardinality and limited scatter in a finite set of points in Euclidean space. For each cluster, the scatter is the sum of the distances (raised to a power) between the elements and the center of the cluster. Depending on the problem, the center can be defined in different ways—as a fixed point, as the centroid of the cluster, etc. We propose a general scheme for a pseudo-polynomial algorithm to solve such problems, and we also show how and in what time this scheme can be implemented for several types of centers.

KW - Bounded scatter

KW - Clustering

KW - Euclidean space

KW - Max-min problem

KW - NP-hardness

KW - Pseudo-polynomial algorithm

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85214256736&origin=inward&txGid=04da1540db6c4dc2a5b067facdad494b

UR - https://www.mendeley.com/catalogue/09f22b7b-6695-337e-af73-b5cff5cf9a51/

U2 - 10.1007/978-3-031-73365-9_22

DO - 10.1007/978-3-031-73365-9_22

M3 - Conference contribution

SN - 978-303173364-2

T3 - Communications in Computer and Information Science

SP - 319

EP - 333

BT - Communications in Computer and Information Science

PB - Springer Science and Business Media Deutschland GmbH

T2 - 23rd International Conference on Mathematical Optimization Theory and Operations Research

Y2 - 30 June 2024 through 6 July 2024

ER -

ID: 61412560