scientific article; zbMATH DE number 2000148
In this paper a generalized minimum covering problem for a 0,1-matrix is investigated: Let \(B=\{b_{ij}\}\) be a\ 0,1-matrix of \((m\times n)\)-type. We say that the row \(i\) of the matrix \(B\) covers the column \(j\), if \(b_{ij}=1.\) The set \(\pi \) of rows of \(B\) covers the matrix \(B\) if each column of \(B\) is covered by at least one row from \(\pi .\) Let \(c=(c_{1},c_{2},...,c_{n})\) be a given vector, each \(c_{i}\) be an integer. The concept of covering is generalized as follows: The set \(\pi ^{\prime }\) of rows of \(B\) is a \(c\)-covering of the matrix \(B\) if \(j\)-th column of \(B\) is covered by at least \(c_{j}\) rows from \(\pi ^{\prime },\) \(j\in \{1,2,...,n\}.\) A new algorithm for solving a problem of finding \(c\)-covering with minimal number of rows is described. Such an algorithm is based on the special concepts of syndrome columns and cutting planes. A statistical optimality of the algorithm is proven and discussed.
- An approximation algorithm for the total covering problem
- An exact algorithm for the maximal covering problem
- An approach to the solution of the set-covering problem
- scientific article; zbMATH DE number 800301
- Some algorithms for solving the covering problem, and their experimental study on a computer
- The generalized maximum coverage problem
- An algorithm for set covering problem
- An algorithmic framework for solving geometric covering problems -- with applications
- scientific article; zbMATH DE number 3863198
- The generalized covering salesman problem
- Resolution principle for the minimum covering problem of a 0-1 matrix
- Minimum ratio cover of matrix columns by extreme rays of its induced cone
- AE1: An extension matrix approximate method for the general covering problem
- A Generic Algorithm for Solving Inclusions
- Computer Solutions to Minimum-Cover Problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4433722)
