On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems

DOI10.1016/S0304-3975(97)00115-1zbMath0915.68072OpenAlexW2075779886MaRDI QIDQ1274926

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00115-1

zbMATH Keywords

linear systems approximability bounds designing linear classifiers nonzero variables unsatisfied relations

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (63)

Sparse high-dimensional fractional-norm support vector machine via DC programming ⋮ A fixed-point proximity algorithm for recovering low-rank components from incomplete observation data with application to motion capture data refinement ⋮ Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints ⋮ Deep Learning--Based Dictionary Learning and Tomographic Image Reconstruction ⋮ MAGMA: Multilevel Accelerated Gradient Mirror Descent Algorithm for Large-Scale Convex Composite Minimization ⋮ Unnamed Item ⋮ Supervised classification and mathematical optimization ⋮ The use of grossone in elastic net regularization and sparse support vector machines ⋮ Polarization in cooperative networks through optimal placement of informed agents ⋮ Using zero-norm constraint for sparse probability density function estimation ⋮ On the complexity of deriving position specific score matrices from positive and negative sequences ⋮ A concave optimization-based approach for sparse multiobjective programming ⋮ Complexity and approximability of parameterized MAX-CSPs ⋮ Objective Selection for Cancer Treatment: An Inverse Optimization Approach ⋮ Unsupervised robust discriminative manifold embedding with self-expressiveness ⋮ FEATURE TRANSFORMATION: A GENETIC-BASED FEATURE CONSTRUCTION METHOD FOR DATA SUMMARIZATION ⋮ Inverse max + sum spanning tree problem under Hamming distance by modifying the sum-cost vector ⋮ Feature selection in machine learning: an exact penalty approach using a difference of convex function algorithm ⋮ Sparse optimization via vector \(k\)-norm and DC programming with an application to feature selection for support vector machines ⋮ Dimensional reduction of nonlinear finite element dynamic models with finite rotations and energy-based mesh sampling and weighting for computational efficiency ⋮ Structure-preserving, stability, and accuracy properties of the energy-conserving sampling and weighting method for the hyper reduction of nonlinear finite element dynamic models ⋮ A nonlinear kernel SVM Classifier via \(L_{0/1}\) soft-margin loss with classification performance ⋮ Multi-objective optimization algorithm based on clustering guided binary equilibrium optimizer and NSGA-III to solve high-dimensional feature selection problem ⋮ Unnamed Item ⋮ A Subgradient-Based Approach for Finding the Maximum Feasible Subsystem with Respect to a Set ⋮ Feature Selection for Heterogeneous Ensembles of Nearest-neighbour Classifiers Using Hybrid Tabu Search ⋮ A majorization penalty method for SVM with sparse constraint ⋮ Representation recovery via \(L_1\)-norm minimization with corrupted data ⋮ A new hybrid \(l_p\)-\(l_2\) model for sparse solutions with applications to image processing ⋮ Sparse weighted voting classifier selection and its linear programming relaxations ⋮ Sparse regression with exact clustering ⋮ Constructing New Weighted ℓ₁-Algorithms for the Sparsest Points of Polyhedral Sets ⋮ A DC programming approach for feature selection in support vector machines learning ⋮ Beyond sparsity: the role of \(L_{1}\)-optimizer in pattern classification ⋮ Non-Negative Sparse Regression and Column Subset Selection with L1 Error ⋮ Convex Optimization for Group Feature Selection in Networked Data ⋮ A two-phase relaxation-based heuristic for the maximum feasible subsystem problem ⋮ A Hybrid Feature Selection Algorithm Based on Large Neighborhood Search ⋮ Complexity of minimum irreducible infeasible subsystem covers for flow networks ⋮ Bidirectional heuristic attribute reduction based on conflict region ⋮ Sparse optimization in feature selection: application in neuroimaging ⋮ A generalized eigenvalues classifier with embedded feature selection ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Iterative reweighted noninteger norm regularizing SVM for gene expression data classification ⋮ On the approximability of minmax (regret) network optimization problems ⋮ A discrete particle swarm optimization method for feature selection in binary classification problems ⋮ Sparse regularization for semi-supervised classification ⋮ Concave programming for minimizing the zero-norm over polyhedral sets ⋮ Simultaneous feature selection and clustering based on square root optimization ⋮ Fast algorithms for robust principal component analysis with an upper bound on the rank ⋮ Gene selection via a new hybrid ant colony optimization algorithm for cancer classification in high-dimensional data ⋮ Hybrid feature selection algorithm using symmetrical uncertainty and a harmony search algorithm ⋮ Stochastic DCA for Sparse Multiclass Logistic Regression ⋮ DC Programming Approach for a Class of Nonconvex Programs Involving l 0 Norm ⋮ Feature selection in SVM via polyhedral \(k\)-norm ⋮ Feature selection with dynamic mutual information ⋮ An alternating minimization method for robust principal component analysis ⋮ Robust sparse recovery via a novel convex model ⋮ On the hardness of approximating max-satisfy ⋮ Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

Cites Work

This page was built for publication: On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems