New approximations and hardness results for submodular partitioning problems

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

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

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

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)