On the complexity of polyhedral separability
From MaRDI portal
Publication:1119020
DOI10.1007/BF02187916zbMath0669.68035MaRDI QIDQ1119020
Publication date: 1988
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131054
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Other problems of combinatorial convexity (52A37)
Related Items
On the problem polyhedral separability: a numerical solution ⋮ Geometric separability using orthogonal objects ⋮ Counterexample-guided predicate abstraction of hybrid systems ⋮ A characterization of 2-threshold functions via pairs of prime segments ⋮ On the complexity of approximating and illuminating three-dimensional convex polyhedra ⋮ Data separation via a finite number of discriminant functions: a global optimization approach ⋮ On the complexity of some geometric problems in unbounded dimension ⋮ Complexity of linear relaxations in integer programming ⋮ Separation and approximation of polyhedral objects ⋮ Supervised classification and mathematical optimization ⋮ On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees ⋮ About the decidability of polyhedral separability in the lattice \(\mathbb {Z}^d\). Recognizing digital polyhedra with a prescribed number of faces ⋮ Combinatorial characterizations of \(K\)-matrices ⋮ Complexity of training ReLU neural network ⋮ Committee polyhedral separability: complexity and polynomial approximation ⋮ Monochromatic partitioning of colored points by lines ⋮ On the difficulty of designing good classifiers ⋮ Computational aspects of relaxation complexity: possibilities and limitations ⋮ On learning a union of half spaces ⋮ Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ Approximation algorithms for hitting objects with straight lines ⋮ Lower bounds for the number of hyperplanes separating two finite sets of points ⋮ A LAD-based method for selecting short oligo probes for genotyping applications ⋮ A constraint generation algorithm for large scale linear programs using multiple-points separation ⋮ Training a Single Sigmoidal Neuron Is Hard ⋮ Nonlinear separation of data via mixed 0-1 integer and linear programming ⋮ Polyhedral separability through successive LP ⋮ Combinatorial optimization problems related to the committee polyhedral separability of finite sets ⋮ New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries ⋮ Computational aspects of relaxation complexity ⋮ Separation via polyhedral conic functions ⋮ On the Parameterized Complexity of Red-Blue Points Separation ⋮ Support vector machine polyhedral separability in semisupervised learning ⋮ Polyhedral separation via difference of convex (DC) programming ⋮ On approximate learning by multi-layered feedforward circuits ⋮ Bilinear separation of two sets in \(n\)-space ⋮ Hardness results for neural network approximation problems ⋮ The computational complexity of densest region detection ⋮ Hybrid extreme point tabu search
Cites Work
