On the minimum consistent subset problem

DOI10.1007/S00453-021-00825-8MaRDI QIDQ5918312zbMATH OpenOpenAlexFDO

Authors Ahmad Biniaz, S. Cabello, Paz Carmi, Jean-Lou De Carufel, Anil Maheshwari, Saeed Mehrabi, Michiel Smid

Publication date 30 June 2021

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.09232

zbMATH Keywords

additively-weighted Voronoi diagramsconsistent subsetfarthest-point Voronoi diagramsparaboloid liftingplanar separatorspoint locationrange trees

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• On the minimum consistent subset problem
• Minimum consistent subset problem for trees
• On the minimum satisfiability problem
• On the solution of min-sum-min problems
• Algorithms for computing minimal unsatisfiable subsets of constraints
• On the complexity of the minimum independent set partition problem
• On the minimum hitting set of bundles problem
• On the Minimum Hitting Set of Bundles Problem
• The minimum entropy submodular set cover problem
• Minimum consistent subset of simple graph classes

Cites work

• A compact piecewise-linear Voronoi diagram for convex sites in the plane
• Algorithms and hardness results for nearest neighbor problems in bicolored point sets
• An algorithm for a selective nearest neighbor decision rule (Corresp.)
• Computation of non-dominated points using compact Voronoi diagrams
• Consistent subset problem with two labels
• Finding small simple cycle separators for 2-connected planar graphs
• scientific article; zbMATH DE number 741008 (Why is no real title available?)
• Linear Programming in Linear Time When the Dimension Is Fixed
• Near-Optimal Sample Compression for Nearest Neighbors
• NEAREST NEIGHBOR PROBLEMS
• Optimal binary space partitions for segments in the plane
• The slab dividing approach to solve the Euclidean \(P\)-center problem

Cited in

(9)

• Minimum consistent subset problem for trees
• Algorithms and hardness results for nearest neighbor problems in bicolored point sets
• A Generic Program for Minimal Subsets with Applications
• Consistent subsets: computationally feasible methods to compute the Houtman-Maks-index
• On the minimum consistent subset problem
• Minimum consistent subset of simple graph classes
• The minimum consistent spanning subset problem on trees
• Minimum consistent subset in trees and interval graphs
• Minimum selective subset on unit disk graphs and circle graphs

This page was built for publication: On the minimum consistent subset problem

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