The maximum matrix contraction problem

DOI10.1007/978-3-319-45587-7_37MaRDI QIDQ2835698zbMATH OpenOpenAlexFDO

Authors Dimitri Watel, Pierre-Louis Poirion

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-45587-7_37

zbMATH Keywords

approximation algorithmcomplexitylinear programming

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 2104735
• Approximation algorithms for the consecutive ones submatrix problem on sparse matrices
• Approximation of the Consecutive Ones Matrix Augmentation Problem
• The consecutive ones submatrix problem for sparse matrices
• Minimising the number of gap-zeros in binary matrices

Cites work

• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Computing in operations research using Julia
• The maximum matrix contraction problem

Cited in

(3)

• Monge matrices make maximization manageable
• A general framework for computing maximal contractions
• The maximum matrix contraction problem

Describes a project that uses

Uses Software

• Julia

This page was built for publication: The maximum matrix contraction problem

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