New approximations and hardness results for submodular partitioning problems

DOI10.1007/978-3-030-79987-8_36OpenAlexW3183634933MaRDI QIDQ2115890

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on formulations for the \(A\)-partition problem on hypergraphs
• Greedy splitting algorithms for approximating multiway partition problems
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Detecting high log-densities
• Submodular Cost Allocation Problem and Applications
• Maximizing Non-monotone Submodular Functions
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Finding k Cuts within Twice the Optimal
• A new approach to the minimum cut problem
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Submodular Function Minimization under Covering Constraints
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• Approximation Algorithms for Submodular Multiway Partition
• Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
• Facility location with hierarchical facility costs

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