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

DOI10.1137/0607039zbMath0594.90062OpenAlexW2053658161MaRDI QIDQ3725872

Timothy J. Lowe, Martin W. Broin

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

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

Related Items (7)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The distance-domination numbers of trees
• Solving covering problems and the uncapacitated plant location problem on trees
• A General Algorithm for the Optimal Distribution of Effort
• A Class of Balanced Matrices Arising from Location Problems
• The Maximum Coverage Location Problem
• Totally-Balanced and Greedy Matrices
• Balanced matrices

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