New approximations and hardness results for submodular partitioning problems
type: Item
instance of: scholarly article
title: New approximations and hardness results for submodular partitioning problems
DOI: 10.1007/978-3-030-79987-8_36
author: Richard Santiago
publication date: 2022-03-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/2006.14312
Mathematics Subject Classification ID: 68Rxx
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7495045
MaRDI profile type: Publication
OpenAlex ID: W3183634933
cites work: Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
cites work: Q4607983
cites work: Approximation Algorithms for Submodular Multiway Partition
cites work: Submodular Cost Allocation Problem and Applications
cites work: Q5140849
cites work: A note on formulations for the \(A\)-partition problem on hypergraphs
cites work: Q2969615
cites work: Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
cites work: Maximizing Non-monotone Submodular Functions
cites work: Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
cites work: Q4633864
cites work: A Polynomial Algorithm for the k-cut Problem for Fixed k
cites work: Network design for information networks
cites work: Submodular Function Minimization under Covering Constraints
cites work: A new approach to the minimum cut problem
cites work: Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
cites work: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
cites work: Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
cites work: Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
cites work: Q5009516
cites work: Finding k Cuts within Twice the Optimal
cites work: Submodular Approximation: Sampling-based Algorithms and Lower Bounds
cites work: Facility location with hierarchical facility costs
cites work: Greedy splitting algorithms for approximating multiway partition problems
description: scientific article; zbMATH DE number 7495045