Computing the spark: mixed-integer programming for the (vector) matroid girth problem
From MaRDI portal
Publication:2007824
DOI10.1007/s10589-019-00114-9zbMath1425.90073OpenAlexW2950978955MaRDI QIDQ2007824
Publication date: 22 November 2019
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10589-019-00114-9
Integer programming (90C10) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Information theory (general) (94A15)
Related Items
A survey on compressive sensing: classical results and recent advancements ⋮ Star DGT: a robust Gabor transform for speech denoising ⋮ Sparse recovery with integrality constraints ⋮ Optimal arrangements of classical and quantum states with limited purity
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tensor Decompositions and Applications
- Algorithms for the minimum weight of linear codes
- Matrix sparsification and the sparse null space problem
- A mathematical introduction to compressive sensing
- Testing the nullspace property using semidefinite programming
- On verifiable sufficient conditions for sparse signal recovery via \(\ell_{1}\) minimization
- Making sparse matrices sparser: Computational results
- An algorithm to compute a sparse basis of the null space
- Computational experience with general cutting planes for the set covering problem
- The complexity of determining a shortest cycle of even length
- A decomposition theory for matroids. V: Testing of matrix total unimodularity
- On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
- Decomposition of regular matroids
- Enhancing an algorithm for set covering problems
- A hierarchical algorithm for making sparse matrices sparser
- Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
- Sparsification of rectangular matrices
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- Geometric algorithms and combinatorial optimization.
- A note on hyperplane generation
- Recovering an optimal LP basis from an interior point solution
- Algebraic graph theory without orientation
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Vandermonde matrices, NP-completeness and transversal subspaces
- On the minors of an incidence matrix and Smith normal form
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Full spark frames
- Implementation of a unimodularity test
- Sparse recovery with integrality constraints
- On the (co)girth of a connected matroid
- Deterministic constructions of compressed sensing matrices
- Fast and Near-Optimal Matrix Completion via Randomized Basis Pursuit
- Hidden Cliques and the Certification of the Restricted Isometry Property
- Decoding by Linear Programming
- Sparse representations in unions of bases
- Sparse and Redundant Representations
- Computing a Sparse Basis for the Null Space
- The computational complexity of matroid properties
- Cutting planes from conditional bounds: A new approach to set covering
- Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
- Complexity of Matroid Property Algorithms
- Finding the circuits of a matroid
- Finding a Minimum Circuit in a Graph
- Atomic Decomposition by Basis Pursuit
- The intractability of computing the minimum distance of a code
- Deterministic Compressed Sensing Matrices: Construction via Euler Squares and Applications
- Permuting Sparse Rectangular Matrices into Block-Diagonal Form
- Fixed-Parameter Tractability of Error Correction in Graphical Linear Systems
- Exact and Approximate Sparse Solutions of Underdetermined Linear Equations
- Mathematical Programming Decoding of Binary Linear Codes: Theory and Algorithms
- LDPC Codes for Compressed Sensing
- A Separation Algorithm for Improved LP-Decoding of Linear Block Codes
- The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
- Matrix Analysis and Applications
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
- On the Complexity of Some Enumeration Problems for Matroids
- Canonical Cuts on the Unit Hypercube
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- Compressed sensing
- Algorithms for the set covering problem
