Approximation algorithms for the maximum connected submodular functions

DOI10.1007/978-981-95-0215-8_2MaRDI QIDQ6867295zbMATH OpenFDO

Authors Qinqin Gong, Zixuan Wang, Yang Lv, Ruiqi Yang

Publication date 28 January 2026

Full work available at URL https://doi.org/10.1007/978-981-95-0215-8_2

zbMATH Keywords

approximation algorithmscardinalityconnectivitysubmodular optimization

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A General Approximation Technique for Constrained Forest Problems
• A note on maximizing a submodular set function subject to a knapsack constraint
• An analysis of approximations for maximizing submodular set functions—I
• Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
• Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Approximation algorithms for the connected sensor cover problem
• Bicriteria approximation tradeoff for the node-cost budget problem
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• Saving an epsilon: a 2-approximation for the k-MST problem in graphs
• The design of approximation algorithms

This page was built for publication: Approximation algorithms for the maximum connected submodular functions

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