Journal article
A Dynamic Programming Algorithm for Covering Problems with (Greedy) Totally Balanced Constraint Matrices
SIAM journal on matrix analysis and applications, Vol.7(3), pp.348-357
07/01/1986
DOI: 10.1137/0607039
Abstract
Given an mxn (0, 1) matrix A possessing special structure, we consider the Minimum Cost Maximal Covering Problem (MCP):
Min {cx + dylAx + y >- m, l"x<= p; x {0, 1}", y {0, 1}m}.
We give an O(p2n min {m 2, n2}) dynamic programming algorithm for solving (MCP) when the matrix A is totally balanced. Totally balanced matrices arise naturally in tree network location problems; however, the class of totally balanced matrices is not equivalent to the class of covering matrices arising from tree network location problems: we give an example of a totally balanced matrix for which there exists no corresponding tree network covering problem.
Details
- Title: Subtitle
- A Dynamic Programming Algorithm for Covering Problems with (Greedy) Totally Balanced Constraint Matrices
- Creators
- Martin W BroinTimothy J Lowe
- Resource Type
- Journal article
- Publication Details
- SIAM journal on matrix analysis and applications, Vol.7(3), pp.348-357
- DOI
- 10.1137/0607039
- ISSN
- 0895-4798
- eISSN
- 1095-7162
- Publisher
- Society for Industrial and Applied Mathematics
- Language
- English
- Date published
- 07/01/1986
- Academic Unit
- Business Analytics
- Record Identifier
- 9984963192602771
Metrics
1 Record Views