Solving some vector subset problems by Voronoi diagrams

DOI10.1134/S199047891604013XMaRDI QIDQ2959192zbMATH OpenFDO

Authors V. V. Shenmaier

Publication date 9 February 2017

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S199047891604013X

zbMATH Keywords

computational geometryEuclidean spacepolynomial-time algorithmvector subset problemVoronoi diagram

Mathematics Subject Classification ID

Elementary problems in Euclidean geometries (51M04) Approximation algorithms (68W25) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 6004969
• scientific article; zbMATH DE number 6004955
• An exact algorithm for finding a vector subset with the longest sum
• Theory of continuous optimal set partitioning problems as a universal mathematical formalism for constructing Voronoi diagrams and their generalizations. II: Algorithms for constructing Voronoi diagrams based on the theory of optimal set partitioning
• Approximability of the problem of finding a vector subset with the longest sum

Cites work

• A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence
• An approximation algorithm for a problem of cluster analysis
• An approximation scheme for a problem of search for a vector subset
• An FPTAS for a vector subset search problem
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Finding k points with minimum diameter and related problems
• scientific article; zbMATH DE number 6004969 (Why is no real title available?)
• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• NP-completeness of some problems of a vectors subset choice
• On a variant of the problem of choosing a vector subset
• On Approximating the Depth and Related Problems
• Polynomial algorithms for solving the vector sum problem
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• The densest hemisphere problem
• The problem of finding a subset of vectors with maximal total weight

Cited in

(11)

• Complexity and approximation of finding the longest vector sum
• Approximation and complexity of the capacitated geometric median problem
• Selecting a subset of diverse points based on the squared Euclidean distance
• Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space
• Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster
• Easy NP-hardness Proofs of Some Subset Choice Problems
• Approximability of the problem of finding a vector subset with the longest sum
• Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
• Polynomial-Time Approximation Scheme for a Problem of Searching for the Largest Subset with the Constraint on Quadratic Variation
• An exact algorithm for finding a vector subset with the longest sum
• Complexity and algorithms for finding a subset of vectors with the longest sum

This page was built for publication: Solving some vector subset problems by Voronoi diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959192)