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

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)

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

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

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)