Two-stage BP maximization under \(p\)-matroid constraint

DOI10.1016/j.tcs.2024.114469MaRDI QIDQ6204535

Dong-lei Du, Jing Jin, Hong Chang, Xiaoyan Zhang, Zhi-cheng Liu

Publication date: 28 March 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

curvaturesubmodular termsupermodular term\(p\)-matroid constrainttwo-stage BP maximization

Mathematics Subject Classification ID

Parametric inference under constraints (62F30) Quantum computation (81P68) Maximum principles in context of PDEs (35B50) Algorithms for approximation of functions (65D15) Methods of global Riemannian geometry, including PDE methods; curvature restrictions (53C21) Moduli, classification: analytic theory; relations with modular forms (14J15)

Cites Work

• Unnamed Item
• Unnamed Item
• New performance guarantees for the greedy maximization of submodular set functions
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• A constrained two-stage submodular maximization
• Approximating the least core value and least core of cooperative games with supermodular costs
• Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
• An analysis of approximations for maximizing submodular set functions—I