scientific article; zbMATH DE number 1953104

MaRDI QIDQ4414508zbMATH OpenFDO

Authors Diana Poensgen, S. S. Ravi, Sven O. Krumke, Madhav V. Marathe, H.-C. Wirth

Publication date 25 July 2003

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2573/25730321.htm

zbMATH Keywords

approximation algorithmbudgeted maximum coverageinteger linear programmingmaximum weight matchingtreewidth

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• The budgeted maximum coverage problem
• Maximal covering tree problems
• An approximation algorithm for maximum weight budgeted connected set cover
• scientific article; zbMATH DE number 6851883
• Partial vertex cover and budgeted maximum coverage in bipartite graphs

Cited in

(7)

• The budgeted maximum coverage problem
• Approximations for restrictions of the budgeted and generalized maximum coverage problems
• An approximation algorithm for maximum weight budgeted connected set cover
• Maximum weighted independent sets with a budget
• Phylogenetic diversity and the maximum coverage problem
• The generalized maximum coverage problem
• An \(O(n(\log n)^{2}/\log \log n)\) algorithm for the single maximum coverage location or the \((1,X_p)\)-medianoid problem on trees

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 Q4414508)