Solving some vector subset problems by Voronoi diagrams

DOI10.1134/S199047891604013XzbMath1374.90327MaRDI QIDQ2959192

V. V. Shenmaier

Publication date: 9 February 2017

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

zbMATH Keywords

Euclidean spacepolynomial-time algorithmVoronoi diagramcomputational geometryvector subset problem

Mathematics Subject Classification ID

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

Related Items (11)

Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems ⋮ Selecting a subset of diverse points based on the squared Euclidean distance ⋮ Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster ⋮ 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 approximation of finding the longest vector sum ⋮ Complexity and algorithms for finding a subset of vectors with the longest sum ⋮ Easy NP-hardness Proofs of Some Subset Choice Problems ⋮ Approximability of the Problem of Finding a Vector Subset with the Longest Sum ⋮ Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space ⋮ Approximation and complexity of the capacitated geometric median problem

Cites Work

• The densest hemisphere problem
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Finding k points with minimum diameter and related problems
• On Approximating the Depth and Related Problems
• Constructing Arrangements of Lines and Hyperplanes with Applications
• An approximation scheme for a problem of search for a vector subset
• An FPTAS for a vector subset search problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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