New approximations and hardness results for submodular partitioning problems

DOI10.1007/978-3-030-79987-8_36MaRDI QIDQ2115890zbMATH OpenOpenAlexFDO

Authors Richard Santiago

Publication date 22 March 2022

Full work available at URL https://arxiv.org/abs/2006.14312

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites work

• scientific article; zbMATH DE number 6850403 (Why is no real title available?)
• scientific article; zbMATH DE number 7051222 (Why is no real title available?)
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A new approach to the minimum cut problem
• A note on formulations for the A-partition problem on hypergraphs
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• Approximation Algorithms for Submodular Multiway Partition
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Facility location with hierarchical facility costs
• Finding k Cuts within Twice the Optimal
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• Greedy splitting algorithms for approximating multiway partition problems
• Hardness of submodular cost allocation: lattice matching and a simplex coloring conjecture
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Local distribution and the symmetry gap: approximability of multiway partitioning problems
• Maximizing Non-monotone Submodular Functions
• Multi-agent submodular optimization
• Network design for information networks
• On the hardness of approximating the \(k\)-\textsc{Way Hypergraph Cut} problem
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Submodular Cost Allocation Problem and Applications
• Submodular Function Minimization under Covering Constraints

Cited in

(3)

• New algorithms for the intersection problem of submodular systems
• Computability of width of submodular partition functions
• Approximating submodular \(k\)-partition via principal partition sequence

This page was built for publication: New approximations and hardness results for submodular partitioning problems

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