Monotonic decompositions of submodular set functions

DOI10.1137/24M1675357MaRDI QIDQ6834007zbMATH OpenFDO

Authors Kristóf Bérczi, Boglárka Gehér, András Imolay, László Lovász, Tamás Schwarcz

Publication date 1 April 2026

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

maximum cutsubmodular functionscoverage functionsinfinite-alternating functions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Cites work

• scientific article; zbMATH DE number 3816010 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3689710 (Why is no real title available?)
• scientific article; zbMATH DE number 3706475 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3307332 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A THEOREM ON INDEPENDENCE RELATIONS
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• An analysis of approximations for maximizing submodular set functions—I
• Bipartite subgraphs of triangle-free subcubic graphs
• Combinatorial auctions with decreasing marginal utilities
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Core-based criterion for extreme supermodular functions
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Maximumk-colorable subgraphs
• Non-additive measure and integral
• On a conjecture of Tuza about packing and covering of triangles
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Packing and covering triangles in graphs
• Packing triangles in weighted graphs
• Recognizing coverage functions
• Reducibility among combinatorial problems
• Submodular functions and optimization.
• Submodular functions: from discrete to continuous domains
• Testing coverage functions
• The Complexity of Partial Function Extension for Coverage Functions
• The theory of regular graphs
• Theory of capacities

This page was built for publication: Monotonic decompositions of submodular set functions

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