A Dynamic Programming Algorithm for Covering Problems with (Greedy) Totally Balanced Constraint Matrices

DOI10.1137/0607039MaRDI QIDQ3725872zbMATH OpenOpenAlexFDO

Authors Martin W. Broin, Timothy J. Lowe

Publication date 1986

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0607039

zbMATH Keywords

Minimum Cost Maximal Covering ProblemTotally balanced matricestree network location

Mathematics Subject Classification ID

Dynamic programming (90C39) Integer programming (90C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Inventory, storage, reservoirs (90B05)

Recommendations

• Totally-Balanced and Greedy Matrices
• scientific article; zbMATH DE number 1253069
• scientific article; zbMATH DE number 1285628
• Totally balanced and totally unimodular matrices defined by center location problems
• scientific article; zbMATH DE number 30950

Cites work

• scientific article; zbMATH DE number 9246 (Why is no real title available?)
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 3634298 (Why is no real title available?)
• A Class of Balanced Matrices Arising from Location Problems
• A general algorithm for the optimal distribution of effort
• Balanced matrices
• Solving covering problems and the uncapacitated plant location problem on trees
• The Maximum Coverage Location Problem
• The distance-domination numbers of trees
• Totally-Balanced and Greedy Matrices

Cited in

(7)

• Totally-Balanced and Greedy Matrices
• Characterising \((k,\ell )\)-leaf powers
• Totally balanced and totally unimodular matrices defined by center location problems
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Worst-case incremental analysis for a class ofp-facility location problems
• Improved complexity bounds for location problems on the real line
• Neighborhood subtree tolerance graphs

This page was built for publication: A Dynamic Programming Algorithm for Covering Problems with (Greedy) Totally Balanced Constraint Matrices

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