New approximations and hardness results for submodular partitioning problems
From MaRDI portal
Publication:2115890
DOI10.1007/978-3-030-79987-8_36OpenAlexW3183634933MaRDI QIDQ2115890
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2006.14312
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
