Computing the spark: mixed-integer programming for the (vector) matroid girth problem
type: Item
instance of: scholarly article
title: Computing the spark: mixed-integer programming for the (vector) matroid girth problem
zbMATH Open document ID: 1425.90073
author: Andreas M. Tillmann
published in: Computational Optimization and Applications
publication date: 2019-11-22T00:00:00Z
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 94A15
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 7135240
zbMATH Keywords: matroid girth
zbMATH Keywords: spark
zbMATH Keywords: sparse recovery
zbMATH Keywords: compressed sensing
zbMATH Keywords: branch-and-cut
zbMATH Keywords: mixed-integer programming
describes a project that uses: Unimodularity Test
describes a project that uses: SCIP
describes a project that uses: PDCO
describes a project that uses: Unimodularity
MaRDI profile type: Publication
full work available at URL: s10589-019-00114-9
OpenAlex ID: W2950978955
cites work: Full spark frames
cites work: The complexity and approximability of finding maximum feasible subsystems of linear relations
cites work: On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: Computational experience with general cutting planes for the set covering problem
cites work: Permuting Sparse Rectangular Matrices into Block-Diagonal Form
cites work: Cutting planes from conditional bounds: A new approach to set covering
cites work: Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
cites work: Canonical Cuts on the Unit Hypercube
cites work: On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
cites work: Enhancing an algorithm for set covering problems
cites work: An algorithm to compute a sparse basis of the null space
cites work: Recovering an optimal LP basis from an interior point solution
cites work: Q4313087
cites work: Decoding by Linear Programming
cites work: Algorithms for the set covering problem
cites work: A hierarchical algorithm for making sparse matrices sparser
cites work: Atomic Decomposition by Basis Pursuit
cites work: Vandermonde matrices, NP-completeness and transversal subspaces
cites work: On the (co)girth of a connected matroid
cites work: Fixed-Parameter Tractability of Error Correction in Graphical Linear Systems
cites work: Q3096150
cites work: Testing the nullspace property using semidefinite programming
cites work: A Direct Formulation for Sparse PCA Using Semidefinite Programming
cites work: Deterministic constructions of compressed sensing matrices
cites work: LDPC Codes for Compressed Sensing
cites work: Compressed sensing
cites work: Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
cites work: Sparsification of rectangular matrices
cites work: Sparse and Redundant Representations
cites work: A mathematical introduction to compressive sensing
cites work: Q4198056
cites work: Computing a Sparse Basis for the Null Space
cites work: Matrix sparsification and the sparse null space problem
cites work: Sparse representations in unions of bases
cites work: Algebraic graph theory without orientation
cites work: On the minors of an incidence matrix and Smith normal form
cites work: Geometric algorithms and combinatorial optimization.
cites work: Mathematical Programming Decoding of Binary Linear Codes: Theory and Algorithms
cites work: Q3683420
cites work: Finding a Minimum Circuit in a Graph
cites work: Complexity of Matroid Property Algorithms
cites work: Exact and Approximate Sparse Solutions of Underdetermined Linear Equations
cites work: On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
cites work: On the Complexity of Some Enumeration Problems for Matroids
cites work: Hidden Cliques and the Certification of the Restricted Isometry Property
cites work: Tensor Decompositions and Applications
cites work: Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
cites work: Sparse recovery with integrality constraints
cites work: Algorithms for the minimum weight of linear codes
cites work: Making sparse matrices sparser: Computational results
cites work: Finding the circuits of a matroid

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: The complexity of determining a shortest cycle of even length

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: Deterministic Compressed Sensing Matrices: Construction via Euler Squares and Applications

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: Q5390304

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: The computational complexity of matroid properties

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: Decomposition of regular matroids

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: A note on hyperplane generation

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: A Separation Algorithm for Improved LP-Decoding of Linear Block Codes

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: A decomposition theory for matroids. V: Testing of matrix total unimodularity

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: The intractability of computing the minimum distance of a code

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: Implementation of a unimodularity test

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: Matrix Analysis and Applications

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (cites work)
cites work: Fast and near-optimal matrix completion via randomized basis pursuit

Computing the spark: mixed-integer programming for the (vector) matroid girth problem (DOI)
DOI: 10.1007/S10589-019-00114-9