The maximum matrix contraction problem

DOI10.1007/978-3-319-45587-7_37zbMATH Open1445.68114OpenAlexW2514546884MaRDI QIDQ2835698FDOQ2835698

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

Recommendations

• scientific article; zbMATH DE number 2104735
• Algorithms and Computation
• 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

zbMATH Keywords

linear programmingcomplexityapproximation algorithm

Mathematics Subject Classification ID

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

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
• The maximum matrix contraction problem
• A general framework for computing maximal contractions

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)